Solving Large Linear Programs at Saint Olaf

 

Written by Steve McKelvey

February 8, 2012

 

There are two software packages you can use to solve linear programs and integer programs at Saint Olaf.  Which you choose depends on whether you bought your textbook new or used and whether you always use your personal computer when doing your Operations Research homework.

 

LINDO and lp_solve

 

The first option is the Student Version of LINDO that came with your copy of the textbook.  LINDO is commercial grade software widely used to solve linear programs in corporate environments.  The student version has a limit on the number of variables and constraints you can use in a linear program formulation.  For the weekly homework sets this limit will most likely not cause you any difficulties.  For the case study you may very well find yourself exceeding LINDO’s limitations, leaving you unable to use the software.

 

Another important limit on LINDO’s utility for this course is that the license for the software precludes its installation on a network.  This means you cannot install LINDO on your H: drive for use on PCs across campus.  Instead, you must install it on the C: drive of at most one computer and then use this computer exclusively for solving LPs via LINDO.

 

An advantage of using LINDO, and its cousin LINGO, is that both packages are thoroughly documented in the textbook.  I also find LINDO’s output a little easier to read.  Lastly, LINDO has a nice user interface and allows the user to type in an LP from scratch or save an LP in a file and have LINDO open that file.  It is nice to have this choice.

 

The other software choice, lp_solve, is a free open source linear programming solver that has no limit on the number of variables or constraints and has no installation restrictions in its license.  I have installed lp_solve on the course L: drive where anyone taking Operations Research can access the program from any Windows PC on the Saint Olaf network.  You are also welcome to download the software onto your own personal computer if you want.

 

The upside of using lp_solve is its ready availability on computers across campus and the lack of a predetermined limit on the size of problems it will solve.  The lp_solve problem definition syntax allows for the labeling of constraints which can be a big help in interpreting the results of large scale problems.

 

The downside is the lack of documentation and the less friendly user interface.  I will provide some documentation on the use of lp_solve at Saint Olaf, and I will provide links to documentation that exists on the web, but be warned this documentation is limited and not particularly well written.

 

LINDO Documentation

 

The textbook provides very thorough and readable documentation on the LINDO (and LINGO) programs.  I will limit my discussion of LINDO to how one enters a linear program into LINDO.  I will use the Saint Olaf Window Co. linear program as an example.

 

In LINDO the user has two ways of entering a linear program for solution.  The first is to use an editor, like NotePad, to create a file that contains the linear program.  You can then have LINDO open this text file and then solve the problem.  The other choice is to open LINDO and then type in the linear programming problem into the blank inner window opened by LINDO.  When you’re done with the problem, you can solve it in precisely the same fashion as the file-based approach.

 

In both cases the linear program must be entered in the format understood by LINDO.  This format is very simple.  Consider the Saint Olaf Window Co. problem.

 

The St. Olaf Window Company produces two products, aluminum doors and wooden windows.  The parts for aluminum doors are fabricated at SOWC’s plant number 1.  One hour of production time is required to produce the parts for 100 doors.  The parts for wooden windows are produced at plant number 2, which requires two hours of production time to produce the parts for 100 windows.  The final products are assembled at plant 3.  Final assembly requires 3 hours for every 100 doors produced, and 2 hours for every 100 windows produced.  Plants 1, 2 and 3 are available to SOWC for 4, 12 and 18 hours, respectively, each day.  The net profits for these products are 30 cents per door and 50 cents per window.  How many doors and windows should SOWC produce daily?

 

The text file that specifies this linear program for LINDO is shown below:

 

max 30x1 + 50x2

s.t.

x1 < 4

2x2 < 12

3x1 + 2x2 < 18

end

 

There are several things to note.  The objective appears on the top line.  The word “max” indicates the LP is a maximization problem.  The word “min” would be used to indicate a minimization problem.  Variable names must start with a letter, after which additional letters or digits may be used.  The name of a decision variable is limited to eight characters.

 

The objective function can span as many lines as necessary. The line with “s.t.” indicates the transition from the objective function to the structural constraints in the problem.

 

In this example each constraint uses a single line, but LINGO will allow constraints to span as many lines as necessary.  One important aspect of constraint formation is that all the terms involving variables must appear to the left of the inequality operator.  To the right of each constraint’s inequality operator exactly one entry is allowed and this entry must be a constant term.  This sometimes involves rearranging the terms of a constraint.  For example, if you had a constraint like x1+x2 = x3+x4+x5, in LINDO you would need to represent this constraint as:

 

x1 + x2 – x3 – x4 – x5 = 0

 

The word end on the last line signals to LINDO that the problem definition is over.  LINDO assumes that all variables are restricted to be nonnegative; requiring the usual transformation if an unrestricted variable appears in the original formulation.

 

LINDO is pretty flexible regarding the “inequality” operators in the structural constraints.  < and <= are both acceptable ways to indicate a “less-than-or-equal-to” constraint.  Both symbols mean exactly the same thing, a non-strict inequality.  Similarly, both > and >= work to indicate a “greater-than-or-equal-to” constraint.  Equality constraints must use the symbol = to indicate the strict equality.

 

For more detailed documentation on LINDO, check out the Winston text.

 

lp_solve Documentation

 

The lp_solve software has a nice, modern, user interface.  When the program is initially launched, the interface appears as below:

 

 

To solve a linear program you must first get the program loaded into the software.  This can be done two ways.  First, can you type the LP directly into this interface window.  The objective function should begin on line 2 of the interface.  The default is to solve a minimization linear program, to solve a maximization problem, just change “min” to “max” and you’ll be all set.  Beginning on line 3 you can enter any structural constraints you would like to add.  Just be careful to obey the syntax requirements for lp_solve, which are slightly different from the syntax for LINDO (see next section).

 

The second way to load an LP into lp_solve is to create a text file, using Notepad or your favorite text editor, that defines an LP using lp_solve syntax and then using the “Open” option under the “File” menu to load this text file directly into the software.  Such text files should always have the extension .lp to allow the program to fine your file.  You should also be aware that lp_solve can save sessions which can then be loaded using the same “Open” option.

 

Once the LP is loaded into lp_solve it is possible to solve the LP by selecting the “Solve” option under the “Action” menu, clicking on the green triangle in the window’s toolbar, or hitting the F9 key.  To see the optimal results, if any, click on the “Result” tab.  The top line of the “Objective” tab is the optimal objective function value, the remaining lines give the optimal value of the various decision variables.  The “Constraints” and “Sensitivity” tabs reveal other postoptimality results that we’ll discuss near the end of our study of linear programming.

 

 

lp_solve Linear Program Definition Syntax

 

In this section we discuss the description of linear programs in text files destined for use with lp_solve.  To start this discussion, here is the text file that defines our friend the Saint Olaf Window Company Problem:

 

max: 30x1 + 50x2;

Plant1: x1 <= 4;

Plant2: 2x2 <= 12;

Plant3: 3x1 + 2x2 <= 18;

 

While very similar to the LINDO syntax discussed above, there are some important differences to note.  First, note the semicolons at the end of the objective function line and the three constraint lines.  These are mandatory.  Also note that each line starts with a label that ends with a colon.  For the objective function this label will be either max: or min: to designate the program as a maximization or minimization problem.  The labels for the constraints can be anything you want as long as there are no blanks or other special characters.  A good use of these is to specify the scarce resource represented by each constraint.

 

As with LINDO, the inequality operators can be entered with or without the equal signs.  (Obviously, in the case of an equality constraint the equal sign is mandatory!)  The objective function can be spread over several lines of the text file, as can the constraints.  lp_solve uses the semicolons as the sign that the constraint of objective function is ended.

 

A nice feature of the lp_solve syntax is that variables and constants can appear on both sides of the inequality operator.  For example, the Plant3 constraint above could be written:

 

Plant3: 3x1 <= 18 – 2x2;

 

although it is doubtful there is a good reason to do so in this case.

 

The label on the objective function line is required.  The labels on the constraint lines are optional, but strongly recommended.

 

Once you are done working with lp_solve, you can close the DOS window by typing exit or clicking on the X in the upper right hand corner.

 

Final Comments:

 

When deciding which software to use in this course, keep in mind the relative advantages and disadvantages outlined at the top of this page.  My advice is to become experienced with both software packages and both syntaxes.