Talk:Linear programming

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)

---

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 (http://carbon.cudenver.edu/~hgreenbe/glossary/second.php?page=U.html)), 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

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.

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)

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.

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)