I am writing a new book about Operations Research. Though I do not have a title yet, it will be something like, Operations Research using very good tools that you don’t have to pay for. The tools include R, Octave, LPSolve and Scilab (I have written about all of these except LPSolve).

Today I want to talk about Linear Programming with LPSolve. Since I wrote about linear programming recently (“What is Linear Programming?”), I will not bore you with the details for problem formulation, instead going straight into the use of LPSolve to get an optimal solution.  I am using the IDE version of LPSolve, but it can be called from MATLAB, Octave, Scilab and R. As an example I will use a traveling salesman-like problem.

The emphasis here is the tool, not the problem. The Traveling Salesman Problem (TSP) and solution can be found in numerous articles, books and so on. To add the topping to the cake, LPSolve is open-source.

Traveling Salesman Problem

MILPs can be used to model and solve many combinatorial problems. Arguably, the most famous, or notorious, combinatorial problem is the traveling salesman problem.  Many ways of solving it are known. Here we present the MILP way. Unfortunately, no-one knows any fast ways to solve the traveling salesman problem. Figure 1 demonstrates a search for an optimal solution to a 7 city TSP using the branch and bound algorithm.

Figure 1.Solution of a TSP with 7 cities using a simple Branch and bound algorithm.

In the traveling salesman problem one has to find a tour around N points so that the total distance traveled is as short as possible.

An example of the traveling salesman problem is: Brigette [1] the Traveler wants to take a Kyiv–Paris–Rome–Vaasa tour (in some order). The distances (in kilometers) between the cities are:

In which order should Brigette take her tour?

An obvious brute force method to solve the traveling salesman problem is to check all the possible routes and pick the shortest one. The obvious problem with this obvious method is that with  cities we have to check  routes. For example, with 20 cities we would have 20! = 2,432,902,008,176,640,000 routes to check. So we should check over 2 quintillion routes if we are Americans. The Europeans have to check over 2 trillion routes G.  This is our old Nemesis, the combinatorial curse.

With the IDE, we can enter the LPs like we would write them, except each statement is followed by a semicolon. This can be done in an editor, like Notepad++ (see Figure 2), saved as ASCII with an .lp, and read in the LP_SOLVE IDE (File | Open) or written in the IDE Source (see Figure 3) or Matrix windows. You might want to copy–paste it to your editor and save it as Brigette_travels.lp (the text is at the end of this article).  For LP problem formulation, refer to Operations Research: Applications and Algorithms, by Wayne Winston.

Figure 2. Brigette’s Travel LP in Notepad++

To start with, I am assuming we do not know which constraints are binding:

Figure 3. LPSolve IDE showing Source window

The solution is found in the Result tab, and then the Variables, MILP Feasible and results tabs. The variable results are shown in Figure 3, giving the total tour cost of $6243. So, the optimal tour is Kyiv → Vaasa → Paris → Rome ( → Kyiv ). For solution details, see here (or wait for my book to be published).

Figure 4.LPSolve Results window

A nice feature in LPSolve is the Matrix tab. When you enter (or read-in) you LP, LPSoleve converts it to matrix form. Under the File menu, you can Export the Matrix to Excel (for example). I like to do this and run the LP in Excel to validate my results. You can also do this with MATLAB, Octave and Scilab.

We can also view the constraints (Constraints tab) to see which one are binding. Additionally, we can do sensitivity analysis using the results in the Sensitivity tab, which is also where we will find the Dual LP. Dual variables are sometimes referred to a shadow costs or marginal cost.

Conclusion

There are many open-source tools available for solving Operations Research and Analytics customers. LPSolve is one of several built to solve LP problems.

Code to Copy

The text for the LP I entered is provided below. I wrote this in Notepad++, saved it as model.lp (ASCII), and read it in the LPSolve IDE, e.g., File | Open | drive/path/model.lp.

/* model.lp */

min: 10000×1+2023×2+1674×3+1497×4+2023×5+10000×6+1105×7+1967×8+1674×9+1105×10+10000×11+2429×12+1497×13+1967×14+2429×15+10000×16+0x17+0x18+0x19;

x1+x5+x9+x13=1;
x2+x6+x10+x14=1;
x3+x7+x11+x15=1;
x4+x8+x12+x16=1;
x1+x2+x3+x4=1;
x5+x6+x7+x8=1;
x9+x10+x11+x12=1;
x13+x14+x15+x16=1;
4×7+x17-x18<=3;
4×8+x17-x19<=3;
4×10-x17+x18<=3;
4×12+x18-x19<=3;
4×14-x17+x19<=3;
4×15-x18+x19<=3;
0<=x1<=1;
0<=x2<=1;
0<=x3<=1;
0<=x4<=1;
0<=x5<=1;
0<=x6<=1;
0<=x7<=1;
0<=x8<=1;
0<=x9<=1;
0<=x10<=1;
0<=x11<=1;
0<=x12<=1;
0<=x13<=1;
0<=x14<=1;
0<=x15<=1;
0<=x16<=1;
0<=x17<=50;
0<=x18<=50;
0<=x19<=50;
int x1;
int x2;
int x3;
int x4;
int x5;
int x6;
int x7;
int x8;
int x9;
int x10;
int x11;
int x12;
int x13;
int x14;
int x15;
int x16;

References

“Branchbound” by Saurabh.harsh – Own work. Licensed under CC BY-SA 3.0 via Wikimedia Commons – http://commons.wikimedia.org/wiki/File:Branchbound.gif#mediaviewer/File:Branchbound.gif
Winston, W.L. (2004). Operations Research: Applications and Algorithms. Belmont, CA: Brooks/Cole

Endnotes

[1] Named in honor of my friend Brigette Hyacinth.

Authored by:
Jeffrey Strickland, Ph.D.

Jeffrey Strickland, Ph.D., is the Author of “Predictive Analytics Using R” and a Senior Analytics Scientist with Clarity Solution Group. He has performed predictive modeling, simulation and analysis for the Department of Defense, NASA, the Missile Defense Agency, and the Financial and Insurance Industries for over 20 years. Jeff is a Certified Modeling and Simulation professional (CMSP) and an Associate Systems Engineering Professional. He has published nearly 200 blogs on LinkedIn, is also a frequently invited guest speaker and the author of 20 books including:

• Discrete Event simulation using ExtendSim
• Crime Analysis and Mapping
• Missile Flight Simulation
• Mathematical modeling of Warfare and Combat Phenomenon
• Predictive Modeling and Analytics
• Using Math to Defeat the Enemy
• Verification and Validation for Modeling and Simulation
• Simulation Conceptual Modeling
• System Engineering Process and Practices
• Weird Scientist: the Creators of Quantum Physics
• Albert Einstein: No one expected me to lay a golden eggs
• The Men of Manhattan: the Creators of the Nuclear Era
• Fundamentals of Combat Modeling

Connect with Jeffrey Strickland
Contact Jeffrey Strickland