5
$\begingroup$

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

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

$\endgroup$

migrated from stats.stackexchange.com Jul 1 '12 at 10:11

This question came from our site for people interested in statistics, machine learning, data analysis, data mining, and data visualization.

  • $\begingroup$ A good place to ask is or-exchange. or-exchange.com . Why do you write it is an LP (it's not really clear what the parameters are...) $\endgroup$ – user189035 Jul 1 '12 at 8:27
  • 3
    $\begingroup$ It would help if you identified which are the free variables and which are coefficients with fixed values. Also it would help to know how many variables there are in total. $\endgroup$ – Wolfgang Bangerth Jul 1 '12 at 12:55
  • $\begingroup$ Great question and answers! how can someone convert the sigma notations to the Ax = b format? I tried looking this up but didn't find anything. Can someone point me to some resources, please? Thanks! $\endgroup$ – Researcher Feb 26 '17 at 15:52
2
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks, I do not need a professional program. I just need a program to solve this problem in easiest way $\endgroup$ – Reza Jul 1 '12 at 6:20
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

I would recommend using JuMP. You can see here that expressions and constraints can be written directly in terms of summations. The objective function can be written in terms of sums using standard Julia (i.e. use the sum function on arrays and things like that which make sense and is easily readable).

But what's even better than the fact that you can easily write the objective and constraints directly in the sum notation, but you can then use that model to solve the equation using a ton of other packages, standard commercial and open source solvers, all directly from within JuMP. This list right here is a list of the most widely used LP solvers, and you can just test them all in one go without changing your syntax using JuMP.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.