Saturday, July 11, 2009

Formulation: c = Min(a,b) for binary a,b

> How to formulate c=min(a,b) where a,b are binary in a MIP.

This is like c = a×b. See: http://yetanothermathprogrammingconsultant.blogspot.com/2008/05/multiplication-of-binary-variables.html.

I.e.

c ≤ a
c ≤ b
c ≥ a + b − 1
c in [0,1] (continuous)
a,b in {0,1} (binary)
Similarly c = max(a,b) can be modeled via the constraints:
c ≥ a
c ≥ b
c ≤ a + b
c in [0,1] (continuous)
a,b in {0,1} (binary)