Monday, May 18, 2009

CSP: indexing by a variable

A table lookup construct y=value[x] where x is an integer variable can be implemented in a MIP model as follows:

Parameters[Sets[Integers],I],
Parameters[Reals,value[I]],
Decisions[Integers[0,1],b[I]],
Constraints[
    Sum[{i,I},b[i]]==1,
    x == Sum[{i,I},i*b[i]],
    y == Sum[{i,I},value[i]*b[i]],
    ....

Here x and y are variables (they can be relaxed to be continuous as they are automatically integer – that is depending on value[] for y). Some experienced MIP users may recognize a SOS1 structure here. In a CSP model this can sometimes be expressed more succinctly as:

y == value[x]

This is also (and more coherently) discussed in the AMPL extensions document: http://www.ampl.com/NEW/FUTURE/logic.html#varsub. More info here: http://users.iems.northwestern.edu/~4er/WRITINGS/extmodcp.pdf. These references contain some motivating examples.

The Microsoft Solver Foundation group will add this to their OML language: http://code.msdn.microsoft.com/solverfoundation/Thread/View.aspx?ThreadId=1739. This will allow for very natural and intuitive formulations for some models.