Use min/max operator inside integer linear programming constraint

Question

I have for example the following integer variables x1, x2, x3 and y1, y2, y3. Is there a way to constrain them in the following ways?

For example:

min(x1, x2, x3) + min(y1, y2, y3) <= 100

or

max(x1, x2, x3) / 5 + max(y1, y2, y3) / 5 >= 50

Answer 1

In your first scenario, you are putting "downward pressure" on minimum values. It would be much simpler if you were trying to say that

max(x1, x2, x3) + max(y1, y2, y3) <= 100

In that case, you would need 2 auxiliary variables to catch the max of x and y via constraints and then sum those 2 aux variables. You are going "the hard way" and you need to enforce the selection of 1 each of x and y. So, you'll need some binary variables to enforce that selection.

Consider the simplified case of just working with x:

min(x1, x2, x3) <= 25

Let:

select_x[j] ∈ {0, 1} represent the selection of x[j] as the minimum

Then we have

∑ select_x[j] * x[j] <= 25

And we need a constraint to enforce that at least 1 must be chosen:

∑ select_x[j] >= 1

Similarly for y and you get something like:

∑ select_x[j] * x[j] + ∑ select[k] * y[k] <= 100

Realize, this is now a non-linear integer program. If your problem is small, this might be OK, but these can be difficult to solve on larger scale. Fortunately, I think you can linearize this with a big-M constraint...

For the "just x" example, we can re-state as

x[j] <= select_x[j] * 25 + (1 - select_x[j]) * M  [for all j]

And with a little boolean logic, we can make the set of j x k constraints to get the min(x) + min(y) summation as:

x[j] + y[k] <= (select_x[j] + select_y[k])/2 * 100 + (2 - select_x[j] - select_y[k]) * M  [for all j, k]

In that case, M should be > max(x) + max(y)

You should be able to flip this logic, add another set of selection variables and do the same for your 2nd constraint.