AMPL has supported constraint programming since early 2000s when the paper Extending an Algebraic Modeling Language to Support Constraint Programming was published. This work has been recently resumed with an update to ilogcp, the AMPL driver for IBM ILOG CPLEX CP Optimizer (yes, that's how it is called), and more work in this direction is underway. In this post I will show how to build the ilogcp driver and use it with AMPL to solve constraint programming models.

Update: Now you can download the ilogcp driver from the AMPL website, so you don't have to build it yourself.

The source code is available in this AMPL GitHub repository which you can get using Git:

$ git clone git://github.com/vitaut/ampl.git

Alternatively you can download the source using one of these archives: tar.gz, zip.

Apart from the source code you'll also need a recent version of CPLEX Studio and development tools (a C/C++ compiler and make on Linux and Mac, Visual C++ on Windows) installed on your machine. The easiest way to build the source code is with CMake.

The build process is fairly straightforward especially if you have CPLEX Studio installed in the default location:

• Go to the ampl directory containing the source code.
• Run cmake . to generate native makefiles or build projects.
• If you use a Linux/UNIX system, you should now see a Makefile in the current directory. Now you can build the binaries by running make. If you use Windows and have Vistual Studio installed, an AMPL.sln file and several .vcproj files will be created. You can build them using Visual Studio.

Once the build is complete you should have the driver executable called ilogcp in the solvers/ilogcp folder. Just put it in the same folder with other ampl binaries and you are good to go.

As an example let's consider a classical verbal arithmetic puzzle SEND+MORE=MONEY by Henry Dudeney. As in other puzzles of this kind you need to find distinct digits to replace the letters such that the equation holds. In addition the most significant digit of each number shouldn't be zero. This can be easily modeled as a constraint programming problem in AMPL:

set Letters;
var d{Letters} >= 0 <= 9 integer;

s.t. nonzeroS: d['S'] != 0;
s.t. nonzeroM: d['M'] != 0;

s.t. equation:     1000 * d['S'] + 100 * d['E'] + 10 * d['N'] + d['D'] +
                   1000 * d['M'] + 100 * d['O'] + 10 * d['R'] + d['E'] =
  10000 * d['M'] + 1000 * d['O'] + 100 * d['N'] + 10 * d['E'] + d['Y'];

s.t. different: alldiff{l in Letters} d[l];

data;
set Letters := S E N D M O R Y;

Variable d gives the mapping between letters an digits. The nonzeroS and nonzeroM constraints state that S and M shouldn't be zero (as they represent the most significant digits). The equation constraint encodes the main equation that should hold. It might be a bit more compact if we used a separate variable for each letter. Finally the different constraint which specifies that the all the variables d should take different values.

Let's load the model into AMPL:

ampl: model money.mod;
money.mod, line 6 (offset 148):
 Caution: Treating strict inequality constraint as a logical constraint.
context:  s.t. nonzeroS: d['S'] !=  >>> 0; <<<

money.mod, line 7 (offset 176):
 Caution: Treating strict inequality constraint as a logical constraint.
context:  s.t. nonzeroM: d['M'] !=  >>> 0; <<<

AMPL gives you a couple of warnings about the logical constraints. These warnings might be useful since most of the solvers don't know how to deal with such constraints but in this case you can safely ignore them. Now let's change the solver to ilogcp, solve the problem and display the solution:

ampl: option solver ilogcp;
ampl: solve;
ilogcp 12.4.0: feasible solution
289 choice points, 309 fails
ampl: display d;
d [*] :=
D  7
E  5
M  1
N  6
O  0
R  8
S  9
Y  2
;

You can find additional information such as the solver options supported by the ilogcp driver in the README file. The AMPL's constraint programming constructs and their mapping to the corresponding Concert API elements are documented here.

Last modified on 2012-10-09