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

Standard Form

Some authors prefer a stricter standard form.

• https://www3.nd.edu/~dgalvin1/30210/30210_F07/presentations/converting.pdf
• https://people.math.carleton.ca/~kcheung/math/notes/MATH5801/04/4_1_standard_form.html

Berebi (talk) 10:07, 13 March 2024 (UTC)

Oh yeah, the present text doesn't actually show the standard form. Standard form should only use non-negativity constraints. The volume of the interior for standard form problems is always zero I think, and the solution is always in the positive orthant of the plane defined by Ax=b. KetchupSalt (talk) 15:58, 31 March 2024 (UTC)

Error in Augmented form example?

In the Augmented Form section, I believe the final matrix form is slightly incorrect. Should S_1 and S_2 be positive if that is a maximisation, or conversely is it not cast as a minimisation as written? 62.107.21.83 (talk) 06:19, 15 September 2024 (UTC)

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)