How to linearize a minmax constraint

Question

Currently I have this linear programming model:

Max X

such that:

Max_a(Min_b(F(a,b,X))) <= some constant

*Max_a meaning to maximize the following equation by just changing a, and the same applies to Min_b

Now, the problem becomes how to linearize the constraint part. Most of the current Minmax linearization papers talks about Minmax as an objective. But how to linearize it if it was an constraint??

Thanks

Answer 1

Preliminary remark: the problem you describe is not a "linear programming model", and there is no way to transform it into a linear model directly (which doesn't mean it can't be solved).

First, note that the Max in the constraint is not necessary, i.e. your problem can be reformulated as:

 Max X
 subject to: Min_b F(a, b, X) <= K  forall a

Now, since you are speaking of 'linear model', I assume that at least F is linear, i.e.:

 F(a, b, X) = Fa.a + Fb.b + FX.X

And the constraint can obviously be written:

 Fa.a + Min_b Fb.b + FX.X <= k forall a

The interesting point is that the minimum on b does not depend on the value of a and X. Hence, it can be solved beforehand: first find u = Min_b Fb.b, and then solve

 Max X
 subject to Fa.a + FX.X <= k - u   forall a

This assume, of course, that the domain of a and b are independant (of the form AxB): if there are other constraints coupling a and b, it is a different problem (in that case please write the complete problem in the question).