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.
$ git clone git://github.com/vitaut/ampl.git
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
ampldirectory containing the source code.
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:Download the model
d gives the mapping between letters an digits. The
nonzeroM constraints state that
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
constraint which specifies that the all the variables
take different values.
Let's load the model into AMPL:
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:
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.