Lazy constraints seem to be ignored in the final solution

回答済み

Zvonimir Haramustek

2023年03月07日 20:55 編集済み

• 
• 

Hi,

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?

関連

• QP
• Lazy Constraints

0

• 

  Eli Towle

  • Gurobi Staff

  2023年03月10日 11:54 編集済み

  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

サインインしてコメントを残してください。