Wednesday, November 9, 2011

Automatic Reformulations

More and more we see that modeling systems apply automatic reformulations.

For instance I see that Cplex’s Concert accepts

model.add (IloMin (x, y) == 0)

for x≥0,y≥0. Essentially this is “x=0 or y=0”. This construct seems to get translated into

a+b≥1
a=1 ↔ x = 0
b=1 ↔ y = 0
x,y≥0, a,b∈{0,1}

Here the indicator constraints of Cplex are used, so no upper-bounds are needed. For other MIP solvers one would likely use something like:

x ≤ b * x.up
y ≤ (1-b) * y.up
x,y≥0, b∈{0,1} 

Similarly in the language CMPL we see that x*y is accepted and translated if x or y is a binary or integer variable (see http://www.coliop.org/download/cmpl/CMPL-1-5-2.pdf section 7.3).