StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p><strong>GLPK</strong></p> <p>I'm offering an answer using <a href="http://www.gnu.org/software/glpk/" rel="nofollow noreferrer">GLPK's glpsol</a>, but I hope there are much better ways to do this (it seems like GLPK is overly powerful/general for this kind of simple special case of a linear programming problem):</p> <p>In order to generate the .mps file given below you've got to split up your matrices row-wise into a system of equations, so the problem description becomes:</p> <pre><code>minimize cost = 1 x_1 + 2 x_2 + 3 x_3 s.t. constraints: S1 = 1 x_1 + 0 x_2 + 0 x_3 S2 = 0 x_1 + 1 x_2 + 0 x_3 S3 = 1 x_1 + 0 x_2 + 1 x_3 S1 >= 1 S2 >= 1 S3 >= 1 0 <= x1 <= 1 0 <= x2 <= 1 0 <= x3 <= 1 </code></pre> <p><a href="http://www.cs.unb.ca/~bremner//docs/glpk/" rel="nofollow noreferrer">GLPK documentation</a> has detailed info on the .mps format, but you specify the rows, columns, rhs, and bounds. In the ROWS section the 'N' and 'G' specify the type of constraint (number, and greater than respectively). In the BOUNDS section the 'UI' specifies that the bounds are <em>upper integer</em> type, forcing the solution to be integer.</p> <p>To run the solver on the problem specification:</p> <pre><code>> glpsol --freemps example.mps -o example.out </code></pre> <p>example.mps file:</p> <pre><code>NAME VM ROWS N cost G S1 G S2 G S3 COLUMNS x_1 cost 1.0 x_1 S1 1.0 x_1 S3 1.0 x_2 cost 2.0 x_2 S2 1.0 x_3 cost 3.0 x_3 S3 1.0 RHS RHS1 cost 0.0 RHS1 S1 1.0 RHS1 S2 1.0 RHS1 S3 1.0 BOUNDS UI BND1 x_1 1.0 UI BND1 x_2 1.0 UI BND1 x_3 1.0 ENDATA </code></pre> <p>outputs:</p> <pre><code>Problem: VM Rows: 4 Columns: 3 (3 integer, 3 binary) Non-zeros: 7 Status: INTEGER OPTIMAL Objective: cost = 3 (MINimum) No. Row name Activity Lower bound Upper bound ------ ------------ ------------- ------------- ------------- 1 cost 3 2 S1 1 1 3 S2 1 1 4 S3 1 1 No. Column name Activity Lower bound Upper bound ------ ------------ ------------- ------------- ------------- 1 x_1 * 1 0 1 2 x_2 * 1 0 1 3 x_3 * 0 0 1 Integer feasibility conditions: INT.PE: max.abs.err. = 0.00e+00 on row 0 max.rel.err. = 0.00e+00 on row 0 High quality INT.PB: max.abs.err. = 0.00e+00 on row 0 max.rel.err. = 0.00e+00 on row 0 High quality End of output </code></pre> <p>Also, I'm not clear on how to directly get the x vector that solves the problem, though it is encoded in the output above in this section:</p> <pre><code> No. Column name Activity ------ ------------ ------------- 1 x_1 * 1 2 x_2 * 1 3 x_3 * 0 </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload