Download

lp_solve.exe (115K)

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 x1 0.2 x2 0 x3 1.6 Dual values: row1 1.2 row2 0.6 row3 0 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 calculations. -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 numerical instability 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; we get Value of objective function: 5 x1 0 x2 0 x3 1.6667 or if the final line is "int x1, x2, x2;" we get Value of objective function: 4 x1 0 x2 1 x3 1 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.