Sunday, June 6, 2010

Constraint programming

One of the advantages of CP is that some problems can be formulated in a much more natural form. For instance for this problem: http://yetanothermathprogrammingconsultant.blogspot.com/2010/04/miqp-vs-dynamic-programming.html is it quite useful to use a variable as an index in an array.

/*********************************************

 * OPL 6.3 Model

 * Author: erwin

 * Creation Date: Jun 6, 2010 at 5:31:28 PM

 *********************************************/

 using CP;

 int NC = 239;

{int} Chapters = asSet(1..NC);

 

/* int D = 128; solve smaller version: */

int D=20;

{int} Days = asSet(1..D);

                    

int Verses[Chapters] = [20,24,31,38,22,6,22,38,6,22,36,23,42,30,36,39,55,25,24,22,26,31,32,30,

                        25,35,34,18,11,25,54,25,8,22,26,6,30,13,25,22,21,34,16,6,22,32,30,33,

                        35,32,14,18,21,9,15,19,35,14,18,77,13,27,27,15,30,18,18,41,27,30,15,

                        7,33,21,19,22,29,37,35,12,31,15,20,35,29,26,36,16,39,25,24,39,37,20,

                        47,33,38,27,20,62,8,27,32,34,32,46,37,31,29,19,21,39,43,36,30,23,35,18,

                        30,17,37,30,14,17,60,38,43,23,41,16,30,47,15,19,26,15,31,54,24,24,41,36,

                        25,30,40,37,40,23,24,35,57,36,41,13,36,21,52,17,34,14,37,26,52,41,29,28,

                        41,19,38,26,39,31,17,25,30,19,26,33,26,30,26,25,22,19,41,48,34,27,24,20,

                        25,39,36,46,29,17,14,18,6,21,33,39,9,2,49,19,29,22,23,24,22,10,41,37,43,

                        25,28,19,6,30,27,26,35,34,23,41,31,31,34,4,3,4,3,2,9,48,30,26,34];

 

dvar int startch[Days] in 1..NC;

dvar int numch[Days] in 1..NC;

dvar int+ v[Days];

float avg = (sum(c in Chapters) Verses[c])/D;

 

int verses[1..card(Chapters),1..card(Chapters)];

execute{

   var i;

   var j;

   for(i=1; i<=NC; ++i) {

      verses[i][1] = Verses[i];

      for(j=2;i+j-1<=NC;++j)

          verses[i][j] = verses[i][j-1]+Verses[i+j-1];

   }        

}

 

minimize

  sum(d in Days) (v[d]-avg)*(v[d]-avg);

subject to {

  startch[1] == 1;

  forall(d in 2..D) startch[d] == startch[d-1] + numch[d-1];

  startch[D]+numch[D] == card(Chapters)+1;

  forall(d in Days) v[d] == verses[startch[d],numch[d]];

}

Notes:

  • This is written in IBM OPL
  • GAMS has nothing to offer in this area
  • AMPL has some facilities documented in some papers (http://users.iems.northwestern.edu/~4er/WRITINGS/cp.pdf) but I am unaware of this being actually available
  • Some of the newer systems (Comet, MS Solver Foundation) have constraint programming support
  • Some research codes out there have some support for a form of modeling language input (Minizinc, etc.).