Lazy constraints seem to be ignored in the final solution
AnsweredHi,
I've been trying to implement a model that removes positive cycles from the graph by augmenting it as little as possible using qp and lazy constraints.
Here is the code: https://pastebin.com/kLXA1Tnk
But for some reason it ignores my lazy constraints, no matter that debug shows they we're added to the model.
Output example:
['BNB', 'BTC', 'EUR', 'ETH']
('BNB', 'BTC') <= -0.25
('BTC', 'EUR') <= -0.25
('EUR', 'ETH') <= -0.25
('ETH', 'BNB') <= -0.25
Optimal value: -0.0
0.0
0.0
0.0
0.0
0.0
We can see that the model value has indeed changed, as without lazy constraints it would be 1. but those offset variables have not changed, no matter that there were constraints setting them exactly lower than -0.25.
Could this be some referencing problem in the lib?
-
Official comment
This post is more than two 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 try Gurobot, our chatbot interface offering instant, expert-level support. -
It's a bit easier to see what happens if you leave the OutputFlag parameter at its default value. First, Gurobi finds the \(0\)-solution (all variables have value \( 0 \)). The MIPSOL callback is called, yet no lazy constraints are added to the model to cut off this solution. Thus, the \(0\)-solution is accepted as feasible.
Next, Gurobi finds another solution:
$$\begin{align*}x_{\textrm{USD},\textrm{ETH}} &= 0 \\ x_{\textrm{ETH},\textrm{BNB}} &= 1 \\ x_{\textrm{BNB},\textrm{BTC}} &= 1 \\ x_{\textrm{BTC},\textrm{EUR}} &= 1 \\ x_{\textrm{EUR},\textrm{ETH}} &= 1 \\ \textrm{offsets}_{\textrm{USD},\textrm{ETH}} &= 0 \\ \textrm{offsets}_{\textrm{ETH},\textrm{BNB}} &= 0 \\ \textrm{offsets}_{\textrm{BNB},\textrm{BTC}} &= 0 \\ \textrm{offsets}_{\textrm{BTC},\textrm{EUR}} &= 0 \\ \textrm{offsets}_{\textrm{EUR},\textrm{ETH}} &= 0. \end{align*}$$
The MIPSOL callback is again called for this solution. Four lazy constraints are added to the model:
$$\begin{align*}\textrm{offsets}_{\textrm{EUR},\textrm{ETH}} &\leq -0.25 \\ \textrm{offsets}_{\textrm{ETH},\textrm{BNB}} &\leq -0.25 \\ \textrm{offsets}_{\textrm{BNB},\textrm{BTC}} &\leq -0.25 \\ \textrm{offsets}_{\textrm{BTC},\textrm{EUR}} &\leq -0.25.\end{align*}$$
These lazy constraints cut off the new candidate solution. Now, we have a strange situation. The above four lazy constraints are in the model, but the initial \(0\)-solution found and eventually returned by Gurobi does not satisfy them.
The issue is that lazy constraints must be globally valid, meaning they must be satisfied by all solutions to your problem. If the above four lazy constraints are globally valid, they should have been added as lazy constraints in the MIPSOL callback triggered by the \(0\)-solution. Is the \(0\)-solution meant to be feasible for this model?
One other comment: the default lower bound on variables added to the model via Model.addVar()/Model.addVars() is \( 0 \). Based on the lazy constraints, it looks the \(\texttt{offsets}\) variables should be allowed to take on negative values. You can remove the default lower bound of \( 0 \) by adding the keyword argument \(\texttt{lb=-GRB.INFINITY}\) to your call to Model.addVars().
1
Post is closed for comments.
Comments
2 comments