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
-
2The answer to your question depends on a number of factor which you haven't provided to include: the language you are writing in, the libraries you are using, and the objective of your problem. Please edit your question to include sufficient details to allow us to helpitprorh66– itprorh662024-02-24 20:11:50 +00:00Commented Feb 24, 2024 at 20:11
-
@itprorh66 Actually, the question is independent of the language and libraries and is a perfectly valid, self-contained integer programming questionAirSquid– AirSquid2024-02-24 22:13:11 +00:00Commented Feb 24, 2024 at 22:13
Add a comment
|
1 Answer
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.
3 Comments
sunlee
max(x1, x2, x3) + max(y1, y2, y3) <= 100 how could be done? the one you said would be simpler to implement.
AirSquid
As I mentioned in the explanation.... For
x, you'll need 1 variable, say max_x and use a set of constraints to constrain it to larger than each x value. Do same for y, add them together. What have you tried?sunlee
if i say max_x >= x1, x2, x3. Will max_x then strive to be as close as possible to x1,x2,x3?