Efficient way to avoid quadratic constraints
AnsweredTo solve a specific problem, I have created a set of integer decisions variables S[i,k] with lb=0 and ub=640, with a size of approximately 1000 indices, but in some instances it can reach tens of thousands or even millions.
The problem requires that S[i,k] != S[j,k] for every j different from i, except when both S[i,k] and S[j,k] are equal to zero, for every k in K.
I am trying to improve my Python implementation or reformulate these constraints. What would be an efficient approach to achieve this? In order to avoid quadratic constraints, so many additional linear constraints were created that I am not sure if it will actually result in any performance improvements.
Are indicator constraints more efficient in this case? More generally, are indicator constraints efficient or should they be avoided in quantity?
I would greatly appreciate any suggestions for a robust formulation or implementation approach.
Thanks in advance,
Fabio
-
-
Gurobi Staff
I am not sure whether it is the most efficient way of formulating \(S_{i,k} \neq S_{j,k}\) but you could use the addGenConstrAbs method to formulate
\[\begin{align*}
\text{auxvar} &= | S_{i,k} - S_{j,k}|\\
\text{auxvar} &\geq 0.5
\end{align*}\]Now, you also have to model the part "except when both S[i,k] and S[j,k] are equal to zero, for every k in K."
You can add 2 binary variables \(b_i, b_j\) and model
\[\begin{align*}
S_{i,k} &\leq 640 \cdot (1-b_i)\\
S_{j,k} &\leq 640 \cdot (1-b_j) \\
S_{i,k} &\geq (1-b_i)\\
S_{j,k} &\geq (1-b_j)
\end{align*}\]So \(b_i=1\) if \(S_{i,k} = 0\) and \(b_i=0\) otherwise. The same holds for \(b_j\) and \(S_{j,k}\)
You can then add another auxiliary binary \(b_{aux}\) and use Gurobi's addGenConstrAnd method to formulate\[\begin{align*}
b_{aux} = b_i \wedge b_j
\end{align*}\]Now, you can use \(b_{aux}\) to take effect of the previously introduced \(\text{auxvar}\)
\[\begin{align*}
\text{auxvar} &\geq 0.5 - b_{aux}
\end{align*}\]Please note that I am not claiming any efficiency with the above formulation. There may be a more compact and performant formulation for your issue.
Best regards,
Jaromił0 -
-
Thanks for the quick reply (as always)!
I know there is no magic formula for this, I understand that it is necessary to implement and test to see which is the best option for each case. I made some implementations, but different from your suggestion. I'll try it and then I'll report back.
Thank you again
Fabio0 -
-
Thank you, Jaromił. Your suggestion had a slightly better performance than my best implementation, probably because it had fewer restrictions.
Just a question: Is it more efficient or correct to use 0.5 instead of 1, considering that all variables are integers?
Regards,
Fabio0 -
-
-
Hi Fabio,
Good to hear that you are making progress.
Just a question: Is it more efficient or correct to use 0.5 instead of 1, considering that all variables are integers?
It is not more efficient and in theory using 0.5 or 1 has the same effect. However, in practice integer/binary variables often don't attain discrete values but rather something like 0.99999 or 1.00001. Using 1 in such cases may lead to numerical difficulties in some troublesome cases. It may be possible that at some point the solver will have to make a decision based on tolerances and not on the actual (variable) value. Using 0.5 sets you usually on the numerically safer side. I am not aware of a case where using 0.5 over 1 in a similar formulation would have a negative effect on the performance, but of course this is something one would have to thoroughly test.
Best regards,
Jaromił0 -
Please sign in to leave a comment.
Comments
4 comments