CSE 190 - Using AMPL and LP solver packages to solve LP problems

AMPL

AMPL stands for "A Mathematical Programming Language". It is a language for modeling various kinds of mathematical and computational problems in an easy and compact way. You can check out the AMPL website and the wiki page to get more information on AMPL.

In this tutorial, we will learn to convert our LP problem formulations to AMPL format and use an LP solver to solve them.

Basic AMPL Example

We will show a simple example that would serve as a guide to convert programs to AMPL 

maximize      x_1 + 2*x_2
subject to    x_1 + 3*x_2 <= 20
            3*x_1 +   x_2 <= 20
                 x_1, x_2 >= 0

This program will convert to the following AMPL program 

#VARIABLE DEFINITIONS
var x_1;
var x_2;
#OBJECTIVE FUNCTION (maximize or minimize)
maximize value: x_1 + 2*x_2;
#CONSTRAINTS
subject to condition_1: x_1   + 3*x_2 <= 20;
subject to condition_2: 3*x_1 +   x_2 <= 20;
subject to condition_3: x_1 >= 0; 
subject to condition_4: x_2 >= 0;

The converted program is surprisingly clear. Here are the key points of the translation
  • Anything followed by a # sign is treated as comments.
  • All lines must end with a semi-colon. AMPL will not give very enlightening errors in case you miss these.
  • Each variable is declared following the var keyword.
  • The objective function is specified by a keyword (maximize, minimize), followed by a name, followed by a colon, followed by the function.
  • The constraints begin with the keyword subject to followed by a name, followed by a colon, followed by the condition.
  • The names of the variables, conditions, and the objective function have to be unique. AMPL is case sensitive so variables. x_1 and X_1 are treated as different.
Save this converted program to a file. This file will be called the model file. For clarity, give the extension .mod to your model files.

This simple example will help you get most of the problems formulated into AMPL. For more advanced problems you can consult Section 4 and 5 of this tutorial http://www.columbia.edu/~dano/courses/4600/lectures/6/AMPLTutorialV2.pdf. There are a number of other AMPL tutorials available on the net too.

LP Solver Package

AMPL by itself will not do anything. To actually solve the problem, you have to use an LP solver. A solver is a program that can take a problem specified in AMPL format and produce solutions. AMPL supports a large number of LP solvers, however, by default it uses the MINOS solver. It is also supported by Windows, Linux and Mac.

Another LP solver is BPMPD. It can be found at http://www.neos-server.org/neos/solvers/lp:bpmpd/AMPL.html. For this course, we will stick to BPMPD as the default LP solver package.

Finding Solutions

Now that you have your model file, there are two options to actually solve your LP formulation. You can download AMPL and MINOS for your system from the downloads section of AMPL website.

Alternatively, you can submit your problem formatted in AMPL data format to http://www.ampl.com/TRYAMPL/startup.html. You will need to upload your model file (and optionally a data file) and specify the commands to get solution information on the next page.

For using the BPMPD solver, you can upload your model file at http://www.neos-server.org/neos/solvers/lp:bpmpd/AMPL.html

Setting up the Standalone AMPL program

You will need the AMPL and MINOS program from the downloads section of the AMPL website. Get the version for your operation system. On Windows, these are standalone executable files. You need to put both of these executable in the same directory. We will refer to the standalone executable version of AMPL as ampl.

Once you have AMPL on your machine, the following commands will be useful.
  • model <filename> : loads the model file into ampl. No output will be shown. No semi-colon is needed. eg. (model ex1.mod).
  • solve; : will solve the current model that it loaded into ampl. The output will display the optimal value of the objective function. The semi-colon is required!
  • display <comma separated variable list>; : This will display the values of the variables specified. eg. (display x_1, x_2, value;)
  • reset; : clears the model in ampl. This is needed every time you load a model as ampl does not allow you to redeclare variables.