Talk:Linear programming
| This is the talk page for discussing improvements to the Linear programming article. This is not a forum for general discussion of the subject of the article. |
Article policies
|
| Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL |
Archives: 1Auto-archiving period: 12 months  |
 | This  level-4 vital article is rated B-class on Wikipedia's content assessment scale.It is of interest to the following WikiProjects: | ||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||
Section 6 - Bad Syntax Hides Lines
[edit]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
[edit]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
Notes
[edit]
Error in Augmented form example?
[edit]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
[edit]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)
- 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)
- 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)