linear-programmingmixed-integer-programminginteger-programming

Use min/max operator inside integer linear programming constraint


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

Solution

  • 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.