Is there a convenient solver for linear programming with many summations?

Question

How can I solve the following Linear Programming problem in the easiest way?

How can the summation terms be modeled in there?

From page 187 of Mathematical Programming Approaches by Charu Chandra and Janis Grabis.

Answer 1

I generally agree with Aron's answer.

Depending on the modeling software you use, the matrix notation $Ax = b$ may be more or less convenient than sigma notation. For instance, with the C++ interfaces to CPLEX, CLP, CBC, and the Open Solver Interface (OSI), the linear algebra notation is definitely easier to work with, since the interfaces specifically ask you to set up the problem in (more or less) the form of $Ax = b$ (these interfaces are slightly more flexible).

However, some software packages treat defining a linear program as a more declarative process. Examples include GAMS, and the Python packages PuLP and Coopr. These packages focus on making the process of defining the LP look much more like the summation (or sigma) notation used in many problems. It is, of course, possible to force a problem coded in one of these packages to look like $Ax = b$, but it's nice not to have to resort to that notation if you find it cumbersome. Furthermore, these packages are not set up as standalone solvers, and thus are much more likely to have interfaces to multiple solvers, allowing for increased flexibility in implementation (since solvers vary in speed) and distribution (not everyone has licenses for closed-source solvers).

For these reasons, I'd recommend, in decreasing order of preference:

• PuLP because it's easy-to-use, lightweight, open source, and in Python
• Coopr because it's open source and in Python (but more flexible than PuLP)
• OSI because it's open source, and is an interface to multiple (mixed-integer) linear programming solvers, but it requires that you work in a compiled language (C++), which is a usability drawback only necessary for large-scale problems where PuLP and Coopr might run out of memory or take too long
• GAMS because it's easy-to-use, and uses math-like notation, but is closed-source and the trial version can only solve smaller LPs

It took me only about a day or so to learn enough about PuLP to solve small research-scale problems. It took me a couple weeks to get the hang of OSI for research, because compiled languages require more time for development; first, there was the issue of installation, then making sure that I could compile the example files and set up Makefiles correctly, and finally, programs written in C++ are generally a few times longer than programs written in Python to accomplish the same task.

If you really must use MATLAB, Aron's recommendations are probably best. To those, I'd add the MATLAB interface to lpsolve, the MATLAB scripts accompanying the book Linear Programming with Matlab, the CPLEX for MATLAB toolbox, and the YALMIP toolbox.

Of these, the YALMIP toolbox looks most promising because it's free and open source, uses declarative syntax similar to GAMS, PuLP, and Coopr, and has interfaces to a wide variety of free and nonfree solvers for many types of problems (not just linear programming). I haven't used it yet, since I typically do most of my work in the other tools I've mentioned.

Answer 2

Any Linear Program (LP) can be solved by a variety of freely available software. The sigma notation can be converted to linear algebra notation $Ax=b$, which is what will be expected by the LP solver unless you are using a more advanced optimization design framework. You asked about MATLAB, which contains a Linear Programming solver in its Optimization Toolbox, which is available under separate license.

You might be interested in CVX, a freely available toolbox for MATLAB that can solve LPs amongst a more general class of optimization problems.

If you would like to pursue a completely open source route, the two best options I'm aware of are CLP and the GLPK. If you have MATLAB, I recommend starting with CVX.

Answer 3

The problem you have is more an OR problem. As I see, you have a target function and some constraints. IBM ILOG CPLEX Optimization Studio, also known as CPLEX, is a professional software to solve these types of questions. SAS also does optimization and simulation. Hope this answer helps.

Answer 4

Please take a look at lpsolve:

lp_solve is a free (see LGPL for the GNU lesser general public license) linear (integer) programming solver based on the revised simplex method and the Branch-and-bound method for the integers. It contains full source, examples and manuals. lp_solve solves pure linear, (mixed) integer/binary, semi-continuous and special ordered sets (SOS) models.