maximizing the sum of max functions
AnsweredHi,
I would like to solve the following problem
max_{x \in X} sum_{i=1}^N max{ a_i^T x, b_i^T x}
where X is a polyhedral set in R^n, and a_i, b_i are given vectors. Essentially I am maximizing the sum of max functions.
I am wondering what is the most efficient way to model this. Currently I use two methods
1) reformulate the problem using big M constraints, i.e., for a continuous variable s_i and binary variable z_i we have
a_i^T x <= s_i <= a_i^T x + Mz_i
b_i^T x <= s_i <= b_i^T x + M(1-z_i)
Unfortunately, I don't have a good idea for the choice of M, and currently I am choosing it rather arbitrarily, i.e., M = 1000.
2) Use indicator constraints
z_i = 1 iff s_i = a_i^T x
z_i = 0 iff s_i = b_i^T x
Is there a better way to model this type of problem?
best wishes,
Angelos
-
Official comment
-
Gurobi Staff
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?. -
-
-
Hi Angelos,
regarding the big M, you can set a big M for variable \(s_i\) to \(\max\{|a_i|,|b_i|\}\cdot \max\{|x^L|,|x^U|\}\) where \(x^L, x^U\) are the lower and upper bound of \(x\), respectively. You can calculate an even more accurate big M in some cases by checking all combinations of \(a_i,b_i\) and the bounds of \(x\) individually. Moreover, you don't need the left hand side inequalities \(a_i x \leq s_i\) and \(b_i x \leq s_i\) as you want to maximize the objective.
A third way to model this type of problem would be to use the build in Gurobi max constraints. You would then have to introduce an auxiliary variable for each \(\max\) term as you already did with \(s_i\) and add a max constraint for it. You would also have to add auxiliary variables and equality constraints for each \(a_i x\) and \(b_i x\). However, it is not guaranteed that this approach will be faster than one of the two you presented.
Best regards,
Jaromił0 -
-
Thanks a lot Jaromił!
best wishes,
Angelos
0 -
Post is closed for comments.
Comments
3 comments