Linearize y = min(a, b)

When solving real-life optimization problems, sometimes we need a variable that is a minimum of some other variables. It might not be obvious how to express equations such as y = min(a, b) in linear programming, if a and b are to be variables and not parameters, and switching to nonlinear solvers is not always a (good) option. Quick Internet or literature search will tell you to use simple constrains like this:

y <= a
y <= b

and then to either make sure your objective function maximizes y on its own, or add to it a term for y with some positive weight. Sometimes, however, the objective function is dragging your y term down instead, or you don’t feel like littering it with additional technical terms and giving them correct weights. Fortunately, it is possible to express min (and max) relation in linear way without relying on objective function at all.

Reproducible example of GAMS code shows how to do this:

Parameters
pa example value of a,
pb example value of b,
M a large constant;

pa = 10;
pb = 50;
M = 10**9;

Variables x, a, b, obj;
binary variables a_bin, b_bin;

Equations
eA
eB
eUpBoundA
eUpBoundB
eLoBoundA
eLoBoundB
eAorB
eA_bin
eObj
;

* Equations for example values of a and b and obj. function
eA..             a =e= pa;
eB..             b =e= pb;
eObj..           obj =g= 0;

* Linearization of min happens here
eUpBoundA..      x =l= a;
eUpBoundB..      x =l= b;
eLoBoundA..      x =g= a - (1-a_bin) * M;
eLoBoundB..      x =g= b - (1-b_bin) * M;
eAorB..          a_bin + b_bin =e= 1;
eA_bin..         a_bin * M =g= b - a;

model xmin /all/;
solve xmin using MIP minimizing obj;

Maximization can be linearized in analogous way – it suffices to reverse the directions of bound inequalities and swap a and b in eA_bin equation.