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)