Talk:Linear programming

From Wikipedia, the free encyclopedia

This article is within the scope of the following WikiProjects:
This article has an assessment summary page.

Contents

[edit] The difference of notation

Although the mathematical formulas are accompanied by a key, I feel we need to distinguish scalar variables from vector variables by notation. The article uses the scalar notation to describe both a vector and a real-valued variable. For example, we can't differentiate between a vector 'b' and a scalar 'b' until we read the key and find out which type it is.

Does anyone have the notation for vectors that they would like to share for this article?

—Preceding unsigned comment added by 24.87.7.27 (talk) 02:55, 31 January 2008 (UTC)


I removed the bit about undecidability of certain ILP problems. It wasn't correct.

Cheers, Dave Peck Davekpeck 20:34, 25 January 2007 (UTC)

Can somebody please address the question of undecidability of Integer Linear Programming in "the worst case"? I believe that this statement is simply false. Can someone provide either (1) a reference demonstrating undecidability, or (2) instructions on how to remove this misleading piece of information?

If my understanding of this space is correct, the general ILP problem can be reduced to 3SAT in polynomial time. This makes it an NP-Complete problem.

If my understanding is incorrect, can someone clarify this point about undecidability with more detail and a reference?

Thanks!

-Dave Peck Davekpeck 02:01, 25 January 2007 (UTC)


Authors of this page, how about four-color problem, job-shop problem? Ortolan88

"Linear programming was used during WW2 in the planning of convoys to protect merchant shipping" - Can anyone confirm this? If so, is this worth mentioning? Lawsonsj

The Pleasures of Counting by Tom Körner (Cambridge University Press) talks about the planning of convoys during WW2. Unfortunately, I do not remember whether Linear Programming was used. This may be one of the first times that Linear Programming was actually used (Operational Research started in WW2), and therefore worth mentioning. -- Jitse Niesen 22:41, 14 Aug 2003 (UTC)
I read a local magazine about LP today and found that there is no history mentioning in wikipedia. The history of linear programming is everywhere on the web other than here. I added now on wikipedia also. Mlpkr 09:04, 23 December 2006 (UTC)

If people would like to mention in a clean way that a sufficient condition for an IP problem to be equivalent to its LP relaxation is to have its constraint matrix to be a totally unimodular matrix (see a Mathematical Programming Glossary), then write this and link to the new articles that I am creating: unimodular matrix and totally unimodular matrix. -- 02:00am PST, April 13, 2004 Simon Lacoste-Julien

[edit] About Some Minor Corrections Made

This was my first contribution to Wikipedia, so apologies if I have somehow mucked something up. I made a few changes. Partly, I just tried to add a small amount of material and improve the flow of the article, but there were a couple of more substantive changes.

1) The feasible region of the LP is, in general, a polyhedron, not a polytope (which would be bounded as it is the convex hull of a finite number of points). I tried to correct this throughout.

2) The simplex method does not necessarily converge to the optimal solution without special precautions that are not usually taken. "Cycling" can occur where the algorithm gets stuck traveling around a cycle of vertices all having the same (non-optimal) objective value. One method (among many) of avoiding this is "lexicographic resolution of degeneracy." In practice, such cycling in virtually unknown, even when no precautions are taken.

Another (possibly) minor correction: does not LP require the polytope where we search the solution to be a _convex_ polytope? Albmont 13:29, 27 February 2007 (UTC)

[edit] linear and nonlinear integer programming?

According to my friend, linear integer programming is in NP (complexity), not undecidable as the article claims. Can someone verify this? Now the article claims that "In contrast to linear programming...." so does it refer only to nonlinear integer programming or all integer programming? Now the chapter about integer problems is ambiguous.--Thv 07:30, 2005 May 6 (UTC)

Unbounded integer programming is undecidable. See Unsolvability of some optimization problems by Wenxing Zhu. Sciolizer 17:56, 21 September 2007 (UTC)

The decision version of linear programming (i.e. is there a feasible solution with value greater than k, etc) is of course in NP, linear or non-linear (you just plug in the numbers and check). The 0-1 linear integer program is NP-hard (decision version of course). Also note that the method is not NP-hard, since hardness in complexity deals with problems not methods.

If the domain defined by the relaxed ILP is non infinite. The decision problem is is NP. We just have to list all the possibility. the algorithm is exponential on a DTM but is polynomial on a NDTM.

I am not sure that the same proof work on infinite polyhedron since, the number of branch of execution on the NDTM could be infinite. It is possible that it make the execution non polynomial, but I'm not sure of it.

Delayed column generation works also for linear programming problems and is not practical in general unless the problem has some special structure. It would be better to list Branch&Bound, Branch&Cut and Branch&Price as advanced methods.--Palli 02:03, 22 Jun 2005 (UTC)

My first thought was that Matiyasevich's theorem implies that (nonlinear) integer programming is indeed undecidable (in the version: given a problem, does it have a feasible solution). However, your observation that the decision version is in NP sounds convincing. Is it possible that a problem is both undecidable and in NP?
I listed the algorithm you mentioned. Unfortunately, we have no aritcles on branch and cut and branch and price, and the little that I know about optimization is all continuous optimization. It would be grand if you could improve on Wikipedia's articles in this area. Jitse Niesen 21:29, 22 Jun 2005 (UTC)

[edit] Optimizing flow difficult or not?

"LP solvers are in widespread use for optimization of various problems in industry, such as optimization of flow in transportation networks, many of which can be transformed into linear programming problems only with some difficulty."

Is this saying that optimisation of flow problems are hard to formulate as linear programs? That they use linear program because it is hard to transform, despite being hard? I'm struggling with the wording. From memory there is a special class of linear programming called transportation and another one called maximal flow, is this referring to one of these problems, or something different or what? njh 03:59, 19 January 2006 (UTC)

I think the sentence should be interpreted as saying that real-world transportation problems do not quite fit within the framework of linear programming. I believe you are right that there is a class of LP problems called transportation problems, but my best guess is that the sentence does not refer to this. I hope somebody else is able to give a more definitive answer. -- Jitse Niesen (talk) 14:20, 19 January 2006 (UTC)

[edit] about open problem.

the article states "Does LP admit a strongly polynomial algorithm?" as an open problem.? I think that Karmarkar algorithm is strongly polynomial. I haven't seen any "big M" in its complexity!

Potra and Wright, "Interior-point methods", J. Comput. Appl. Math., vol. 124, 2000, state that Karmarkar's algorithm needs O(nL) iterations and O(n3.5L) bit operations, where n is number of variables and L is the length of the problem. Is there a more recent result? -- Jitse Niesen (talk) 10:32, 18 May 2006 (UTC)

[edit] Merging with Job-shop problem

I disagree with a merger. It would be a lot of work and may require big changes to this linear programming article. I would suggest either a redirect from Job-shop problem to here, or to expand that one. Oleg Alexandrov (talk) 05:09, 8 June 2006 (UTC)

The current article already has one example, and I think that suffices. Therefore, I removed the merge tags. There are many problems with job-shop problem, as I explained on the talk page (particularly, it is usually not a linear programming problem), so I tagged it with Template:Cleanup-rewrite. I wouldn't mind if the article were deleted. -- Jitse Niesen (talk) 06:25, 8 June 2006 (UTC)

[edit] not accessible

this is written from a specialists point of view. how about an encyclopedic type description, something anyone with a high school education could get a handle on in the intro?

Justforasecond 05:22, 18 August 2006 (UTC)

You are asking too much, some things are just complicated. Woud an easier to understand introduction make you happy enough? Oleg Alexandrov (talk) 05:26, 18 August 2006 (UTC)
An introduction that an average reader could understand is more in the spirit of an encyclopedia Justforasecond 05:34, 18 August 2006 (UTC)
Given that it is exactly one year on now, I had a go myself at trying to add a one line informal explanation.JohnFlux 22:43, 19 August 2007 (UTC)


Have to agree here. This is written in such a technical way that only those who understand Linear Programming can grasp the ideas of the article, however if you already understand Linear Programming then you wouldn't need to read the article in the first place. Even the section explaining the importance and use of Linear Programming is way too technical. I've read it and still have no idea how Linear Programming might be used. True some things are just complicated but they can be explained in an uncomplicated manner especially throught the use of examples. Saying that you're asking too much to explain it in a pedestrian manner is a copout and shows your lack of ability. This article seems to be for the initiated and to keep out those who don't understand. I may not be a mathmatician but I'm also no idiot as I have an MBA where I had to study logistics and economics but this article is beyond me.

Don't dumb down the article, it's very helpful as it is. Certainly more accessible than the notes I'm supposed to study from.

[edit] Regarding: Does LP admit apolynomial pivot algorithm

This paper gives a randomized polynomial-time simplex algorithm:

http://theory.csail.mit.edu/~kelner/PDFs/KelnerSpielmanSimplex.pdf

As Madhu Sudan pointed out in Jonathan Kelner's thesis defense, a 'trivial' way to acomplish this would be to first solve LP problem using any polynomial LP algorithm and then use the solution to LP problem to identify pivoting strategy.

That's a good point. I removed the following open questions for the moment.
  • Does LP admit a (strongly or weakly) polynomial pivot algorithm (may be a non-simplex pivot algorithm, e.g., a criss-cross or arrangement method)?
  • Does LP admit a (strongly or weakly) polynomial simplex pivot algorithm?
There might be a proper way to formulate this, but it needs to be more precise. -- Jitse Niesen (talk) 03:44, 25 November 2006 (UTC)

[edit] Linear Programming question

The newly opened New Star Bookshop wants to hire new staff as supervisors and general workers. A sum of S$12000 has been allocated for the monthly salaries of the staff. The monthly salary of a supervisor and a general worker are S$2000 and S$1000 respectively. The number of general workers can exceed the number of supervisors by 3 or more. The number of supervisors has to be at least 10% of the number of general workers. Let x represent the number of supervisors and y represent the number of general workers hired, (a) Write three inequalities, apart from x ³ 0 and y ³ 0 , which satisfy the above constraints. (b) Using grid paper, draw the graphs of the three inequalities. Hence, construct and shade the feasible region R that satisfies the above constraints. (c) Based on your graphs, answer the following questions: (i) Find the maximum number of staff that can be hired if the number of supervisors is 25% of the number of general workers. (ii) The bookshop pays overtime allowances of S$60 to a supervisor and S$40 to a general worker per month. Find the maximum total overtime allowance that has to be paid in a month.

Moon--Nightelves92 07:56, 29 April 2007 (UTC)

[edit] Introduction paragraph seems wrong

This seems wrong:

 Such points may not exist, but if they do, searching through the polytope vertices is guaranteed to find at least one of them.

Either the solution is inside or on the edges, but it always exists - continuous functions always have a maximum on a closed set.

Who wrote this, and did I misunderstand?

--Argav ۞ 10:32, 27 June 2007 (UTC)

Continuous functions have a maximum on closed and bounded sets. It may happen that that a continuous function has no maximum on a closed set which is not bounded. For eg: y=x on the reals. The polytope may be unbounded or empty--Shahab (talk) 17:50, 28 January 2008 (UTC)

[edit] Section 6 - Bad Syntax Hides Lines

If you look at section 6, the 4.1 "Example" section, you'll see that something is wrong at the top, and the Z = ... part is totally missing from the output (and should probably be surrounded by ...).

I'm just learning here, so I don't feel comfortable attempting a fix, but it's definitely not right as it is now.