Talk:Linear programming

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.

Methods to convert nonlinear problems to linear programming problems

Hello,

I am not sure where this should go, but I believe there should be examples that convert: absolute value, min, and max into their linear counterparts.

Forgive me I make a mistake in the following examples, I do not know them by heart and am just quickly deriving them as I go.

e.g., min sum abs(x_i)

--- into ---

min sum e_i,

s.t.

e_i >= -x_i, for all i

e_i >= +x_i, for all i

e.g., min max(x_i)

--- into ---

min e,

s.t.

e >= x_i, for all i

e.g., Minimize the minimum of a finite collection min min(x_i)

--- into ---

min e,

s.t.

e <= x_i, for all i

NOTE - This has the degenerate solution of e --> negative infinity. Some software will ignore this degeneracy. Microsoft Excel's simplex solver appears to (in at least some cases) to return the correct answer for problems of the form min_x min_i(f_i(x)), where f_i(x) is linear.

e.g., Converting equality (not really converting nonlinear problem to an LP problem, but still should be mentioned IMHO)

min x_i,

s.t.

x_i = g_i

--- into ---

min x_i,

s.t.

x_i <= g_i

x_i >= g_i

Edit: improved the readability

Error in "Integral linear programs" section

This may be more of an oversight, but in the section, it says (or at the very least, implies) that if there is at least one integral solution to a linear program, it can be solved in polynomial time. However, this almost certainly is not true --- otherwise, 3-SAT would be solvable in polynomial time. I think what should it should say is that it is polynomially solvable if the number of variables are taken to be fixed (for example, Barvinok's algorithm can find integral points in O(N^(d log d)), where d is the dimension/number of variables). PlanetFall456 (talk) 17:17, 7 January 2025 (UTC)

I'm not an expert on this material, but here is my attempt at a response. Are you sure that you're appreciating the distinction between integer linear programs and integral linear programs? It seems plausible to me that integral linear programs can be solved more quickly than integer linear programs (perhaps even by finding a real solution and tweaking it). Maybe someone with more knowledge will chime in. Regards, Mgnbar (talk) 20:37, 7 January 2025 (UTC)

That's what I thought at first, that I missed something --- however, with the standard reduction of 3-SAT, any integral optimal solution to the program can be converted into an assignment in polynomial time. Therefore, if any program with at least one integral solution can be solved in polynomial time, then 3-SAT can be solved in polynomial time. PlanetFall456 (talk) 22:44, 7 January 2025 (UTC)

When you express 3-SAT as a linear program, is it possible that that (real) linear program has non-integral optima (that are better than any integral feasible solutions)? Because that would break your argument, wouldn't it? (I don't know the answer. I'm just trying to help you nail your argument.)

Meanwhile, have you read the last paragraph of the section? The Schrijver text cited there seems like it might resolve this seeming contradiction. Mgnbar (talk) 00:01, 8 January 2025 (UTC)

To put my first question more succinctly: Is the real linear program, that you get by expressing 3-SAT as a linear program, an integral linear program? Mgnbar (talk) 00:15, 8 January 2025 (UTC)

The reformulation used has an objective function of f(X)=0, so any X is optimal --- this means that any integral solution is also an optimal integral solution. PlanetFall456 (talk) 00:43, 8 January 2025 (UTC)

I see. Well, I'm out of ideas then (beyond checking Schrijver). Cheers, Mgnbar (talk) 03:05, 8 January 2025 (UTC)

Solver software categorisation

The section listing software in the article is grouped by kind of license, which is traditional for software on Wikipedia, but in this case becomes misleading.

Taking license as a primary concern means you care about deployment, i.e., enabling someone else to do this, rather than just being able to do it yourself. However, the majority of items in the two open source categories turn out to not themselves be LP solvers, but rather front-ends for or wrappers around underlying solvers, which may turn out to be closed-source commercial! The common pattern for these front-end systems seems to be that they, for each kind of optimisation or constraint satisfaction problem they cover, may support a dozen or so different underlying solvers, whose license conditions can be just about anything; if you're lucky there is a free one that you can run, but unless the installation scripts automagically select such a configuration for you, then deployment can become a nightmare.

I understand the rationale for an open source system to support a commercial backend — you can begin getting work done using a free system, and if it down the line turns out that you need to handle problems that are very large then you can just switch out the solver component with a more high-performance one (even if that means you had to pay for it) without having to rewrite all your custom code — but listing them without context in an article that goes from discussing properties of different algorithms to giving links to software implementations is more confusing than helpful. If viewing an optimisation problem as an isolated issue, then a toolbox with a domain-specific scripting language may be just the thing, but if instead you need that optimisation as a step in a larger algorithm, then you don't want the overhead of a scripting front-end, no matter how nifty its interface may be.

I'm putting in a maintenance tag because I'm not sure how to best solve this. One approach could be to separate underlying solvers in these lists from the front-end wrappers, but working out which is what does not seem entirely easy; often the true nature of one of these items is buried several levels down in their documentation sites. ~2026-41802-80 (talk) 12:56, 7 August 2026 (UTC)