LP1, LP3, LP4, LP5, F2, F3 (examples from the examples sheet)
lp_solve.zip (zipped file of all of the above, 59K)
LP_SOLVE.EXE solves linear programs. The version that you can download
here runs under DOS on a PC. It is extremely easy to use. You simply
construct a file containing the definition of the problem in an obvious way.
E.g., the file LP1 contains:
3x1 + x2 + 3x3;
row1: 2x1 + x2 + x3 < 2;
row2: x1 + 2x2 + 3x3 < 5;
row3: 2x1 + 2x2 + x3 < 6;
This is the definition of question LP1 on the examples sheet. The objective
function (stated in the first row) is always maximized by lp_solve. For
a minimization problem you just multiply the objective function by -1.
All variables are constrained to be non-negative. So if you have a problem
in which a variable is unconstrained in sign, say x1, you would replace
it throughout your equations by "y1 - z1", say. It is permissible to
have > or = in place of < in specifying any constraint. The labels,
"row1:".."row3:" are optional; you can omit them or use any other labels
you find convenient. Type at a DOS prompt
lp_solve -p < LP1
This tells lp_solve to take its input from the file LP1.
The -p flag tells lp_solve that we want to see the dual variables in the
final solution. The output is
Value of objective function: 5.4
This agrees with the answer x1=1/5, x2=0, x3=8/5 that you have found by
other means. ( If we had wanted the values of the slack variables we
would have written the problem as
3x1 + x2 + 3x3;
row1: 2x1 + x2 + x3 + z1 = 2;
row2: x1 + 2x2 + 3x3 + z2 = 5;
row3: 2x1 + 2x2 + x3 + z3 = 6; )
Type "lp_solve -h" and you will get a list of some other options:
Usage of LP_SOLVE.EXE version 2.0:
LP_SOLVE.EXE [options] < input_file
list of options:
-h prints this message
-v verbose mode, gives flow through the program
-d debug mode, all intermediate results are printed,
and the branch-and-bound decisions
-p print the values of the dual variables
-b bound specify a lower bound for the objective function
to the program. If close enough, may speed up the
-i print all intermediate valid solutions.
Can give you useful solutions even if the total run time
is too long
-e number specifies the epsilon which is used to determine whether a
floating point number is in fact an integer.
Should be < 0.5
-c during branch-and-bound, take the ceiling branch first
-s use automatic problem scaling.
-I print info after reinverting
-t trace pivot selection
-mps read from MPS file instead of lp file
-degen use perturbations to reduce degeneracy, can increase
lp_solve can impose the constraint that one or more variables must take
integer values. For example, with the input file:
3x1 + x2 + 3x3;
2x1 + x2 + x3 < 2;
x1 + 2x2 + 3x3 < 5;
2x1 + 2x2 + x3 < 6;
int x1, x2;
Value of objective function: 5
or if the final line is "int x1, x2, x2;" we get
Value of objective function: 4
In these cases lp_solve is not using only the simplex algorithm (which
has no method on its own to find the best integer solution), but also
a technique called branch-and-bound.
lp_solve was originally written for Unix machines. This port of
lp_solve version 2.0 to DOS was done by John P. Powers in September 1995.
Let me know if you have any problems getting this program to work for you.
It works successfully in a DOS window on my PC running Windows 95.
Richard Weber, 21 May 1996.