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:

    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: More info here: These references contain some motivating examples.

The Microsoft Solver Foundation group will add this to their OML language: This will allow for very natural and intuitive formulations for some models.