" /> My Constraint Programming Blog: November 2012 Archives

« October 2012 | Main | December 2012 »

November 23, 2012

A first look at AIMMS+CP (AIMMS with Constraint Programming)

In the Summer of 2011 I had the opportunity to test an early beta version of AIMMS+CP (AIMMS with Constraint Programming), and then did a second test round in September 2012 (with a late beta version). Here are some of my comments of my experiences with AIMMS+CP during these tests. A little later, in October 2012, Paragon released version 13.1 to the public including AIMMS+CP.

My AIMMS+CP page links to both .aim files (which shows the textual representation of parameters, variables and constraints) and the .aimmspack file (a binary file containing the full model project including the GUI part and other settings). As usual I have implemented many of my "starting/learning" models to be able to compare them with other CP systems. I would like to thank especially Chris Kuip and Gertjan de Lange from Paragon for great support, suggestions and inspirations during these tests.

First a little about Paragon and their commercial product AIMMS, from the Overview:
AIMMS offers an all-round development environment for the creation of high-performance decision support and advanced planning applications to optimize strategic operations. It allows organizations to rapidly improve the quality, service, profitability, and responsiveness of their operations. The AIMMS development environment possesses a unique combination of advanced features and design tools, such as the graphical model explorer, which allow you to build and maintain complex decision support applications and advanced planning systems in a fraction of the time required by conventional programming tools.
One distinct feature of AIMMS is the integrated GUI where one both define the parameters, variable and constraints as well as the graphical input/output of the model. I should note that this is the first time in my CP experience that I've worked with this kind of tight integrated tool, which might explain some of the comments below.

AIMMS GUI tool was (and still is AFAIK) only for Windows, so I used VirtualBox under my Linux Ubuntu 12.04 when testing. Also, before the test, I have not used AIMMS at all.

Documentation, examples

There is a lot of documentations of how AIMMS work (PDF files available from the Help menu):
  • AIMMS Getting Started
  • AIMMS User's Guide
  • AIMMS Language Reference
  • AIMMS Optimization Modeling
  • AIMMS Function Reference
  • AIMMS Tutorial
  • etc
The documentation of the CP related features has been incorporated in these documents, especially AIMMS Language Reference, chapter 21 ("Constraint Programming") including a short introduction to CP and a discussion of the different variables types (Variable, Element Variable) used in CP modeling.

For a person that knows AIMMS well and also know how CP works, the documentation is probably enough. But for someone like me that didn't know AIMMS before or someone who know AIMMS but not CP, the documentation is a little thin, especially since the examples are quite advanced to get started. I missed some of the standard CP examples such as N-queens, Send More Money, Sudoku, etc and examples of the basic stuff, such as how handle single variables, comparisons etc. Hopefully my AIMMS+CP implementations might be of some help.

The documentation don't say much about the CP solver and what options it has (and what they mean); though the is some documentation available with the Help button for the options. It is great that there are good support for scheduling and the example models are interesting, but - again - too complicated to start learning from.

I should mention that I have not read the complete documentation of AIMMS. Instead I started to code in AIMMS almost directly. This might have been a bad decision since I got stumped a couple of times with some of AIMMS basic concepts.

I later realized that AIMMS Blog contains tips and documentation regarding certain AIMMS features.

Modeling in AIMMS

Here I will focus on the modeling part. I have actually done very little extra with the graphics: it's just a Solve button, input fields and output fields/tables, i.e. nothing fancy at all. The models that is distributed with AIMMS is, on the other hand, much more elaborated and tasty and shows a huge number of general different possibilities in AIMMS; though - as mentioned above - there are not many CP specific models. In part, I wrote some of the detailed comments below with a hope to help newcomers in AIMMS+CP.

Below I will try to explain CP modeling in AIMMS+CP as well as some personal comments during my tests. So, let's start with the standard example: SEND+MORE=MONEY (or perhaps Sudoku is more standard nowadays?).

A word of caution: These models are tested with a beta version of AIMMS+CP (albeit a late beta), so some constraints/features might have been changed in the current version.

SEND + MORE = MONEY: Some concepts

Model: SendMoreMoney2.aim

Compared to other CP systems, AIMMS use a little different concepts and approach when modeling, and here I will show this using the SEND+MORE=MONEY problem, where the object - of course - is to assign each letter to an integer so that the equation holds.

In this problem we define the array x with the index domain i (defined as a subset of Integers with the values {1,2,3,4,5,6,7,8}. Then all the parameters (constants) S,E,N,D,M,O,R,Y are defined to be able to be index in x, e.g. such as 1000*x(S)+ 100*x(E)+ 10*x(N)+x(D) (defining SEND) etc.

All these definitions are done via AIMMS' GUI, the Model Explorer. Here is a picture how it looks like; the graphical I/O is shown to the right (the Page Manager):


AIMMS SEND+MORE=MONEY


Below is the full definition of the model except for the graphical part (compare with the .aim file SendMoreMoney2.aim). Note that one very important feature in AIMMS is that one define the set of the indices to be used in an array: here the index i is defined via the set ii (the name of the set is not so important except for documentation purposes). When defining the array (x) the size is defined by the range of the index. So we define the array x(i) (identifier: x, index domain: (i)) and makes it a Variable with the range of {0..9} (i.e. the domain of the values in x).

Then we define the traditional constraints:
  • The values of S and M must be > 0: x(S) > 0 and x(M) > 0
  • The main constraint SEND+MORE=MONEY is defined as usual:
    (1000*x(S) + 100*x(E)+ 10*x(N) + x(D) +
    1000*x(M) + 100*x(O)+ 10*x(R) + x(E)) =
    (10000*x(M) + 1000*x(O) + 100*x(N) + 10*x(E) + x(Y))
And here are most of the definitions (slightly edited). A text representation of the model is available via the GUI: View, Text Representation, All. 
DECLARATION SECTION 
    SET:
       identifier   :  ii
       subset of    :  Integers
       index        :  i
       definition   :  {1,2,3,4,5,6,7,8} ;

    CONSTRAINT:
       identifier   :  SendMoreMoney
       definition   :  (1000*x(S) + 100*x(E)+ 10*x(N) + x(D) +
                        1000*x(M) + 100*x(O)+ 10*x(R) + x(E)) =
            (10000*x(M) + 1000*x(O) + 100*x(N) + 10*x(E) + x(Y)) ;

    MATHEMATICAL PROGRAM:
       identifier   :  SendMoreMoney2Plan
       direction    :  minimize
       constraints  :  AllConstraints
       variables    :  AllVariables
       type         :  CSP ;

    CONSTRAINT:
       identifier   :  SM
       definition   :  x(S) > 0 and x(M) > 0  ;

    VARIABLE:
       identifier   :  x
       index domain :  (i)
       range        :  {0..9} ;

    PARAMETER:
       identifier   :  S
       definition   :  1 ;

    PARAMETER:
       identifier   :  E
       definition   :  2 ;

    PARAMETER:
       identifier   :  N
       definition   :  3 ;

    PARAMETER:
       identifier   :  D
       definition   :  4 ;

    PARAMETER:
       identifier   :  M
       definition   :  5 ;

    PARAMETER:
       identifier   :  O
       definition   :  6 ;

    PARAMETER:
       identifier   :  R
       definition   :  7 ;

    PARAMETER:
       identifier   :  Y
       definition   :  8 ;

    CONSTRAINT:
       identifier   :  AllDiff
       definition   :  cp::AllDifferent(i, x(i)) ;

  ENDSECTION  ;

  PROCEDURE
    identifier :  MainInitialization

  ENDPROCEDURE  ;

  PROCEDURE
    identifier :  MainExecution
    body       :  
      ShowProgressWindow;
      solve SendMoreMoney2Plan;

  ENDPROCEDURE  ;

ENDMODEL Main_SendMoreMoney2 ;
The call cp::AllDifferent(i, x(i)) works like this: The first parameter i is the "loop index" which is used to loop through the second argument x(i), i.e. it states that all the elements in x should be distinct. This is how for-loops are done in AIMMS and is a very common idiom.

The procedure MainExecution is where the program is started and is essential to get things working. Here we just do the following:
  • ShowProgressWindow: the Progress window shows how the model progress as well as the time, number of failures, etc.
  • solve SendMoreMoney2Plan which actuall start the solving process. This must be defined for all models. SendMoreMoney2Plan is of type mathematical program (select this type of identifier via type options labeled "..."). For Constraint Satisfaction models like this, select Type: CSP, and let Direction be whatever (minimize or maximize). For optimization models, the type should be COP (Constraint OPtimization), and state the objective variable, and the direction. (Note: The objective variable must be Free for some reason.)
In the Page Manager, the Solve button is then connected to the action running Main Execution (not shown in the listing above since it belongs to the GUI.)

NQueens

The first naive version of the N-queens problem is NQueens.aim, but is slow for larger N: 
CONSTRAINT:
   identifier   :  C1
   index domain :  (i,j)
   definition   :  (i < j) and x(i) <> x(j)   ;

CONSTRAINT:
   identifier   :  C2
   index domain :  (i,j)
   definition   :  (i < j) and x(i) + i <> x(j) + j ;

CONSTRAINT:
   identifier   :  C3
   index domain :  (i,j)
   definition   :  (i < j) and x(i) - i <> x(j) - j ;

CONSTRAINT:
   identifier   :  AllDiff
   definition   :  cp::AllDifferent(i, x(i)) ;
The more modern - and faster - version is shown in NQueens2.aim which use three alldifferent constraints: 
CONSTRAINT:
  identifier   :  alldiff1
  definition   :  cp::AllDifferent(i, x(i)) ;

CONSTRAINT:
  identifier   :  alldiff2
  definition   :  cp::AllDifferent(i, x(i)-i) ;

CONSTRAINT:
  identifier   :  alldiff3
  definition   :  cp::AllDifferent(i, x(i)+i) ;
To see the number of solutions of a model, just add this line last in MainExecution: 
DialogMessage(GMP::Solution::Count('ProjectPlan'));
together with a large enough value of Solution storage limit in Setting, Project Settings, Specific Solvers, CPoptimizer 12.4, General.

It would be nice to have an easy way to actually showing all solutions, but I'm often quite happy with this feature.

One could note that AIMMS - with CPoptimizer as solver - shows the first solution of N=1000 in 3 seconds (422 failures).
My system setup for this benchmark: Running AIMMS in a Virtual Box running Windows 7, allotted 2Gb RAM, under a Linux Ubuntu 12.04, 64-bit with 12Gb RAM and 8 core Intel 930@2.80GHz.

CoinsGrid

Model: CoinsGridCP.aim
Model: CoinsGridCPMIP.aim

This is originally a MIP problem but I use it to see how a CP solver handles the problem (often not very good so I'm yet to be surprised). I originally thought of doing two versions of this, one CP version and one MIP version. But it's so easy to change to MIP version so I first settled with just one project, hence the name CoinsGridCP.

Note: Chris Kuip was kind enought to later add a way to select between CP and MIP, see CoinsGridCPMIP.aim.

Map, Map2

Model: Map.aim
Model: Map2.aim

This is a simple Map coloring problem, with two variants: Map and Map2.

For the standard settings the model Map.aim shows this solution: 
   Country     Colors
   ------------------
   Belgium     2 
   Denmark     1 
   France      4 
   Germany     3 
   Netherlands 1 
   Luxembourg  1
which is perfectly fine. Without any symmetry breaking there are 144 solutions.

Symmetry breaking
Here is a simple symmetry breaking, where we state that Belgium has color 1 (whatever that color represents) with a restriction in the Index domain: 
     Index domain: c1 | c1 = "Belgium"
     Colors(c1) = 1
The solution is now: 
   Country     Colors
   ------------------
   Belgium     1
   Denmark     1 
   France      4 
   Germany     3 
   Netherlands 2 
   Luxembourg  2
which is also a correct solution.

Since that worked quite well, I also tried another version of Map (Map2.aim) that use real color names instead of integers, and also use another representation of the connections between the countries. This is perhaps more in the spirit of AIMMS.

The set Colors is defined as: 
data {red, blue, green, yellow}
It was also very easy to do the direct representation of the connections between the countries. AIMMS converts automatically to a boolean connection matrix (a nice feature): 

DATA { (Belgium, [France, Germany, Netherlands, Luxembourg]),
       (Denmark, [Germany]),
       (France, [Belgium, Germany, Netherlands, Luxembourg]),
       (Germany, [Belgium, Denmark, France, Netherlands, Luxembourg]),
       (Netherlands, [Belgium, France, Germany]),
       (Luxembourg, [Belgium, Germany]) }
However, it was a little bit harder to define the "DifferentColor" constraint using the color names, but after changing CountryColors to a ElementVariable and Range: Colors it worked as expected. 
SET:
   identifier   :  Countries
   indices      :  c1, c2
   definition   :  data {Belgium, Denmark, France, Germany, Netherlands, Luxembourg} ;

SET:
   identifier   :  Colors
   index        :  c
   initial data :  data {red, blue, green, yellow} ;

ELEMENT VARIABLE:
   identifier   :  CountryColor
   index domain :  (c1)
   range        :  Colors ;

CONSTRAINT:
   identifier   :  DifferentColors
   index domain :  (c1,c2)
   definition   :  if (c1 <> c2 and Connections(c1, c2) = 1) then
                       CountryColor(c1) <> CountryColor(c2)
                   endif  ;
And the solution: 
   Solution:
     Belgium     blue
     Denmark     red
     France      yellow
     Germany     gree
     Netherlands red
     Luxembourg  red

Minesweeper

Model: Minesweeper.aim

As I have mentioned before, I'm always amazed how easy it is to state this problem in a CP system (cudos to these high level programming languages). Here is the problem specification (from Gecode's Minesweeper model): 
A specification is a square matrix of characters. Alphanumeric 
characters represent the number of mines adjacent to that field. 
Dots represent fields with an unknown number of mines adjacent to 
it (or an actual mine).

E.g.
     ..2.3.
     2.....
     ..24.3
     1.34..
     .....3
     .3.3..
The main constraint states that the number in "this" cell (if > 0) is the sum of the number of mines surrounding this cell. The indices i and j are defined as sets 1..#rows and 1..#cols, respectively. The four ifs in the Sum constraint restricts the value of i+a and j+b to be inside the matrix. 
CONSTRAINT:
identifier   :  C1
index domain :  (i,j)
definition   :
   if (Problem(i,j) > 0) then
       Sum[(a,b), x(i+a, j+b) |
           (i+a > 0) and
           (j+b > 0) and
           (i+a <= R) and
           (j+b <= C)] =
       Problem(i,j)
   endif;
However, this constraint is not enough since it don't rule out that a hint cell can contain a mine (or if a cell contains a hint, it cannot contain a mine). So we must add either of these two constraints 
CONSTRAINT:
identifier   :  C2
index domain :  (i,j)
definition   :
   if (Problem(i,j) >= 0) then
       x(i,j) = 0
   endif
comment      :
   "If a cell contains a hint (>= 0) then there can be no mine.
    Either C2 or C3 must be active." ;

CONSTRAINT:
identifier   :  C3
index domain :  (i,j)
definition   :
   if (x(i,j) = 1) then
      Problem(i,j) = -1
   endif
comment      :
    "If this cell contains a mine, then there can be no hint
     (i.e. >= 0). Either C2 or C3 must be active." ;
I tend to prefer constraint C2.

Here's the solution to the problem shown above, where a "1" marks where the mines are. 
1 0 0 0 0 1
0 1 0 1 1 0
0 0 0 0 1 0
0 0 0 0 1 0
0 1 1 1 0 0
1 0 0 0 1 1
(A more artistic modeler than me would show the result in a nicer way.)

Sudoku

Model: Sudoku2.aim

Here is the way to fill the given hints: 
CONSTRAINT:
   identifier   :  FillData
   index domain :  (i,j)
   definition   :  if (Problem(i,j) > 0) then
                      x(i,j) = Problem(i,j)
                   endif  ;
Note that this can also be written without the if clause, which more show the advantage of AIMMS modeling principle: 
   index domain: (i,j) | Problem(i,j) > 0
   definition: x(i,j) = Problem(i,j)
The Latin Square requirements are very easy to state, using two alldifferent constraints: 
  index: i
  cp::alldifferent(i, x(i,j))
and 
  index: j
  cp::alldifferent(i, x(i,j))
However the block constraint is a little more tricky (as in all CP systems). In AIMMS one has (as I understand it) to define a special parameter, Blocks to be used in the constraint: 
PARAMETER:
   identifier   :  Blocks
   index domain :  (i,j)
   definition   :  1+N*Div(i-1,N)+Div(j-1,n) ;

CONSTRAINT:
   identifier   :  C3
   index domain :  k
   definition   :  cp::AllDifferent( (i,j) | Blocks(i,j) = k, x(i,j) ) ;
The unique solution to the problem instance is 
7 9 5 1 4 6 8 2 3 
6 4 3 8 2 5 7 9 1 
2 1 8 3 9 7 4 6 5 
5 2 7 9 6 1 3 8 4 
8 6 4 7 5 3 2 1 9 
1 3 9 2 8 4 6 5 7 
4 5 1 6 7 2 9 3 8 
9 7 6 5 3 8 1 4 2 
3 8 2 4 1 9 5 7 6
To ensure that this is a unique solution, simply counts the number of solutions: any value larger than 1 means that the model is wrong in some way. Here's to do it:
  • Increase the number of Solution storage limit in Setting, Project Settings, Specific Solvers, CPoptimizer 12.4, General to 2 (the default is 1).
  • Show the number of solutions with this code in MainExecution: DialogMessage(GMP::Solution::Count('Sudoku2Plan') + " solutions");
When running the model, it shows "1 solutions" which indicates a unique solution.

AllDifferentExcept0

Model: AllDifferentExcept0.aim

AIMMS has excellent support for reification and I'm (happily) surprised that it worked as I expected. This is the constraint CAllDifferentExcept0 which states that all values in x that are not 0 (zero) must be distinct (hence the name of the global constraint AllDifferentExcept0). 
   if (i < j and x(i) <> 0 and x(j) <> 0) then
     x(i) <> x(j)
   endif;
I also added an increasing constraint, CIncreasing: 
   if (ord(i) > 1) then
      x(i-1) <= x(i)
   endif;
Though it might be more clear to write it as: 
    index domain :  i | ord(i) > 1
    definition   :  x(i-1) <= x(i)

WhoKilledAgatha: reification and Element variables

Model:WhoKilledAgatha.aim

This is a standard benchmark for theorem proving and I use it for testing how well a CP system supports boolean decision variables and reifications. The way I usually model this problem yields 8 solutions, all indicating the same murder (guess who).

This AIMMS model also yields 8 solutions, and the tables for Hates and Richer are valid so I conclude that this model is correct (or rather: as correct as my other versions of this problem).
Here is the problem:
Someone in Dreadsbury Mansion killed Aunt Agatha. Agatha, the butler, and Charles live in Dreadsbury Mansion, and are the only ones to live there. A killer always hates, and is no richer than his victim. Charles hates noone that Agatha hates. Agatha hates everybody except the butler. The butler hates everyone not richer than Aunt Agatha. The butler hates everyone whom Agatha hates. Noone hates everyone. Who killed Agatha?
This was not as hard as I first thought it should be, though I had to experiment a little with Element Variables to get it to work.
Some comments:
  • The two decision variables Hates and Richer are set to Element Variables to be able to handle Element constraints such as 
      Hates(TheKiller, TheVictim) = 1
  Richer(TheKiller, TheVictim) = 0
    Note that TheKiller is a decision variable.

    It's great that AIMMS support these kind of "matrix element constraint", even though one have to declare the variable as a special type.

  • I like that AIMMS has the same syntax for if-then else whether or not decision variables or parameters are involved in the if clause. This makes creating constraints much easier.

  • When using other CP systems I will certainly miss AIMMS elegant ways of creating certain constraints.
The way the constraints are stated in AIMMS is shown below, where we also show how a matrix is defined. As usual the size and indices of the matrix (Hates) are are defined via the set (ij), defining the indices and their domains (i and j). 
PARAMETER:
       identifier   :  N
       definition   :  3 ;

SET:
       identifier   :  ij
       subset of    :  Integers
       indices      :  i, j
       definition   :  {1..N} ;

VARIABLE:
       identifier   :  Hates
       index domain :  (i,j)
       range        :  binary ;

CONSTRAINT:
       identifier   :  KillerHatesAVictim
       definition   :  hates(TheKiller, TheVictim) = 1 ;

CONSTRAINT:
       identifier   :  ButlerHaveEveryoneWhomAgataHates
       index domain :  i
       definition   :  if (Hates(Agatha, i) = 1) then
                         Hates(Butler, i) = 1
                       endif ;
(Sometimes I don't like to have to name all constraints in the model, but right now when writing about them it's is quite useful.)

DivisibleBy9Through1

Model: DivisibleBy9Through1.aim

This problem is mainly used to test a CP system regarding two things:
  • the modulo constraint, which is quite essential for some recreational mathematics problems. AIMMS has support for this (otherwise I would have tried to implement it).
  • how large integers can be handled
    AIMMS can manage up to base 10 (which is quite normal). I have seen solutions of this problem for base 12 and 14 (found by the ECLiPSe CP system). Here are the solutions for N <= 10 (the AIMMS model just show one of the alternative solutions): 
    2: [1]
4: [1, 2, 3] 
   [3, 2, 1]
6: [1, 4, 3, 2, 5] 
   [5, 4, 3, 2, 1]
8: [3, 2, 5, 4, 1, 6, 7]
   [5, 2, 3, 4, 7, 6, 1]
   [5, 6, 7, 4, 3, 2, 1]
10: [3, 8, 1, 6, 5, 4, 7, 2, 9]
Chris Kuip suggested the following addition to MainExecution procedure which saves the variables for the first solution to a file: 
write AllVariables to file "DivisibleBy9Through1.wrt";

FurnitureMoving: simple scheduling problem

File: FurnitureMoving.aim

This is a simple scheduling problem from Kim Marriott & Peter Stuckey: "Programming with constraints", page 112f, where the object is to optimize the tasks of moving some furnitures. In AIMMS the ParallelSchedule constraint is used, which is much like the traditional cumulative constraint: 
cp::ParallelSchedule(
       upperLimit,
       jobDomain,
       jobStart,
       jobDuration,
       jobEnd,
       jobHeight
    )
Here are the specific values used in the model: 
   UpperLimit: 4           (resources, i.e. persons)
   UpperLimit2: 120        (minutes)
   jobDomain: j            (index for domain Jobs: {1..UpperLimit2})
   jobStart: Start         (minutes, variable)
   jobDuration: Duration   (minutes, may involve variables)
   jobEnd:  End            (minutes, variable)
   jobHeight: Resources    (persons, may involve variables)
The only trouble I had here was how to define jobDomain, but after reading the definition a couple of times it's quite clear that UpperLimit, and jobHeight should have the same unit (i.e. resources), while the other are time (in minutes); that is, for this specific model.

It seems that we can assume that the End job requirement is automatically ensured by the cp::ParallelSchedule constraint, e.g. this constraint: 
jobEnd(i) = jobStart(i) + jobDuration(i)
(In many other CP systems one have to ensure this explicitly.)

This is a optimization model where MaxEndTime is to be minimized, stated in the mathematical program (here called FurnitureMovingPlan).

In some variants of cumulative (e.g. some of MiniZinc's solvers) I've seen that the total number of required resources can be a decision variable as well (and thus can be an objective variable), but this variant is not supported in AIMMS.

Later note: The AIMMS Blog's blog post Scheduling example: Narrowing time window for smaller jobs explains a little how to use scheduling with AIMMS+CP.

Langford number problem: indices

Langford.aim

Problem statement:
Langford's number problem (CSP lib problem 24)
Arrange 2 sets of positive integers 1..k to a sequence, such that, following the first occurence of an integer i, each subsequent occurrence of i, appears i+1 indices later than the last.
For example, for k=4, a solution would be 41312432
In this model I had some problems understanding how AIMMS' indices works, which emphasize that they don't work exactly as the "array based" indices that I'm used to from other CP systems.

In the constraints pos1 and pos3 shown below, it's important to restrict the index j so it don't go "over the edge" of the position array, which is interpreted by AIMMS as an error in the model, i.e. it throws an UNSAT when this happens. [Or perhaps it's the solver CPLEX CP Optimizer that does this interpretation.] Using the traditional "array based" for-loops this would have been easier, at least for me using a traditional for-loop. So beware of this gotcha. (Note: When writing this now much later, this behaviour actually makes much more sense than when I did the model.) 
CONSTRAINT:
  identifier   :  pos1
  index domain :  j |j <= k
  definition   :  position(j) + j+1 = position(j+k)
  comment      :  "Note the index domain." ;

CONSTRAINT:
  identifier   :  pos2
  index domain :  (i)
  definition   :  solution(position(i)) = i ;

CONSTRAINT:
  identifier   :  pos3
  index domain :  j |j <= k
  definition   :  solution(position(k+j)) = j
  comment      :  "Note the index domain." ;
A similar case is in the AllInterval where one of the constraints is to restrict the index i to not be the last value of the Set i1 set (defined as the range 1..N), so it restricts i in the DiffsK constraint to not be N. 
SET:
  identifier   :  i1
  subset of    :  Integers
  index        :  i
  definition   :  {1..N} ;

...

CONSTRAINT:
 identifier   :  DiffsK
 index domain :  i | i <> last( i1 )
 definition   :  diffs(i) = Abs(x(i)-x(i+1))
 comment      :  "Note the special handling of the index domain for this constraint." ;
These kind of behaviour (different to what I'm used to) have caused some long debugging sessions.

Fortunately Chris Kuip was kind enough to explain all this to me. And today he also wrote the blog post What is the element after the last? explaining this in some detail.

Magic Square and Magic Square Water Retention problem

Model: MagicSquare.aim
Model: MagicSquareWaterRetention.aim

The plain MagicSquare model is not so interesting, except perhaps that in the GUI one can select which symmetry breaking constraints to use. This is done via the four binary variables UseSymmetry1 ... UseSymmetry4.

Magic Square Water Retention problem
More interesting is MagicSquareWaterRetention.aim which is one of few model where I have tested with different search heuristics and other settings (see below for a little more about these). The object is to create a magic square where the numbers represents heights and retains as much water as possible in the "cavaties" that is created. More info about this problem is in Wikipedia article Water retention on mathematical surfaces. This AIMMS model also use the Frénicle standard form for symmetry breaking.

It seems that the big win is to use Search Type::Restart instead of Automatic. Using this option solves the problem for N=4 in about 3 seconds (with 168662 failures) compared to 20 seconds (663751 failures) when using Search Type: Automatic.

Trying with N=5, my small allotted 2Gb for the VirtualBox Windows 7 was probably not enough since AIMMS unfortunately crashed. (Chris Kuip mentioned that this crasch is not reproducible in the released version of AIMMS+CP.)

[My best shot of this problem has so far been with a MiniZinc model where Gecode/fz solves N=4 in 0.8 seconds (48619 failures) using the heuristics "most_constrained"/"indomain_random".]

In this model we see some of the benefits and drawbacks of the AIMMS approach (as I perceive them):
  • benefit: It's quite easy and descriptive to state the water retention constraint (first part). There is no explicit for-loop, just using the defined indices and adjust for the border cases (1 and N). 
       (i,j) | i > 1 and j > 1 and i < N and j < N
   water(i,j) = Max(x(i,j), Min(water(i-1,j), water(i,j-1),
                            water(i+1,j), water(i,j+1)))
  • drawback: When defining the ranges (domains) - which in this model are 1..N, 1..N*N, and 1..N*N*N, it must be done with two extra help parameters (N2, N*N, and N3, N*N*N) since the Range Wizard for the variable cannot calculate formulas for the upper bound.
  • drawback: Defining the optimization problem the objective (z) must be declared as a Free Range variable (-inf .. inf) and not using the Range domain (1..N3). Intuitively this seems to be a too large domain for the solver to handle, but perhaps the solver is intelligent in calculating the bounds.

Some other comments

Here are some more asorted comments about AIMMS+CP and my way of using it.

Number of solutions

One of the drawback in AIMMS is that it's not easy to generate all the solutions. It is possible but I have not done that. However, it's easy to count the number of solutions using the following:
  • Change Settings, Project Options... select Specific solvers, CPoptimizer 12.4, General and change Solution storage limit to a higher value, e.g. 1000.
  • Add this code to the MainExecution procedure: DialogMessage("It was " + GMP::Solution::Count('ProjectPlan') + " solution(s).");

Data instances, data files

Many of models contain some data (as a parameter that might be changed when running the project). There is in principle two approaches for using data files in AIMMS:
  • enter the data via the Parameter definition and keep it there.
  • define a couple of data files and load the appropriate via Data, Load Case, as active
I have used both principles in the models, though with the second approach one of the data instances is loaded automatically via Settings, Project, Startup & authorization, Startup case.

Automatically saving .aim files

Since I often want to look in other models when implementing a new (mostly done with the .aim files), I tend to set the projects to save the .aim file when closing the project: Settings, Autosave & Backups, Project, Create an AIM file at Project Close.
There seems to be no way to set this option globaly, i.e. for all new projects created.

Heuristics

I like that there is a lot of different heuristics, though I have not explored them as much. They are defined in Settings, Project Option, Specific solvers, CPoptimizer 12.4, Search
  • Variable selection:
    • Automatic
    • Random
    • Smallest domain size
    • Largest domain size
    • Smallest maximum domain value
    • Largest maximum domain value
    • Smallest minimum domain value
    • Largest minimum domain value
    • Smallest impact
    • Largest impact
    • Smallest impact last branch
    • Largest impact last branch
    • Smallest local impact
    • Largest local impact
    • Smallest success rate
    • Largest success rate
  • Value selection:
    • Automatic
    • Smallest impact
    • Largest success rate
    • Smallest value
    • Largest value
Note that these search heuristics are globally on the model. I have found no way to select the specific variable(s) to branch on.

Procedures

One drawback in AIMMS is that there is no way (I know of) to implement a user-defined "procedure" that is easy accessible in different models/projects. Instead one has to copy the constraint verbatim. I have mostly copied the definitions from the saved .aim files. There is also a way of viewing the textual representation in the current model (presented much like the .aim files). This is done via View, Text Representational, All when in the Model Explorer.

Later note: Guido Diepen (Paragon) blogged about this a year ago Exporting a section and importing it in another AIMMS project, though I didn't now that until very recently.

Some tips

Stop a calculation: Ctrl-Shift-S

Don't forget to set Set ii to a subset of integers.

Pros / Cons: A kind of summary

And finally, here is a subjective list of pros/cons about AIMMS (as I have understood it). Pros
  • AIMMS has a very nice GUI to create and checking constraints and the related data. The online checking of constraints, indices, lengths etc is very handy.
  • Certain constructs are nice and powerful, e.g. that there is no syntactic difference between "if" on plain boolean variables/conditions and on decision variables.
  • Another nice thing is that some loops can be written quite naturally without "for" just via the index (i,j etc).
  • Using a GUI makes it easy to connect different parts of the model, especially between data/variables and the output.
Cons
  • For an "integer array based" constraint programmer like me it took some time to get used to the "items based" approach that is AIMMS' forte. Example: Some intuitions from "integer index based" modelling don't apply directly to AIMMS; e.g. see the dicussion about the Langford model above.
  • Also, the focus on defining indices and their connection with arrays was a little uncommon for me, and took some time from the rest of the modeling.
  • It's not very easy to generate and show all solutions to a problem. Though it's very easy to generate the number of solutions (see NQueens etc).
  • Using a GUI as the main modeling is a bit strange to me since I'm almost always use a texteditor (Emacs) and then run via command line (under Linux). There are ways to use textfiles directly but since this is Windows I'm not very confortable which that.
  • I used Windows 7 in VirtualBox under Ubuntu 12.04 and some things didn't work, for example copying backup files from my Linux box to the Windows' AIMMS' directory. This was - of course - not AIMMS' fault, but it made my experience sometimes a little frustrating...

My AIMMS+CP models

Here are some of my AIMMS+CP models, many originally written in the Summer 2011. Around mid-September 2012, I re-checked (and re-modelled) these with AIMMS version 3.13 (beta) and also added a few new. Thanks to Chris Kuip (Paragon) for comments, suggestions and improvements on many of these models.

Posted by hakank at 09:00 PM |