Differance between MIPSOL and MIPNODE
回答済み
Hi,
I am currently working on an optimization problem using Gurobi and using callback functionality. I want to add cute (subtour elimination, benders, etc.) to my problem, and adding cuts in MIPSOL and MIPNODE have different CPU time performances.
Can there be instances where an MIPSOL callback might coincide with a MIPNODE callback? Is it accurate to consider that all MIPSOL solutions are also MIPNODE, or are these fundamentally different? As I understand, MIPSOL is a solution in a branch and bound tree where all solutions are integers. I have tried to check the fact by following MIPSOL_NODCNT and MIPNODE_NODCNT and it seems that they are counting the same thing.
Am I correct? If I am not, could you please explain how MIPSOL is generated?
I have observed that it is common practice to add lazy constraints in the MIPSOL callback but not user cuts, whereas user cuts are typically added in the MIPNODE callback. Could you explain the reasoning behind this distinction and why user cuts are generally not added in the MIPSOL callback?
Thank you
Farzad
-
Hi Farzad,
The MIPNODE callback is called whenever a node LP is solved - that is the linear relaxation of the problem where some variables may have been fixed.
The MIPSOL callback is called whenever a solution is discovered. There are many ways this may arise, including from a node LP being integer feasible, but also of course by heuristics.
Can there be instances where an MIPSOL callback might coincide with a MIPNODE callback?
Yes, when the node LP is integer feasible
Is it accurate to consider that all MIPSOL solutions are also MIPNODE
No, you could even have solutions found before the branch and bound tree even exists
As I understand, MIPSOL is a solution in a branch and bound tree where all solutions are integers
The solution will be integer feasible, but it does not necessarily come from the tree.
I have tried to check the fact by following MIPSOL_NODCNT and MIPNODE_NODCNT
They both count the number of nodes, but are used respectively with MIPSOL and MIPNODE callbacks. If the callbacks are called at the same time you would expect them to have the same value.
I have observed that it is common practice to add lazy constraints in the MIPSOL callback but not user cuts,
Lazy constraints are those which are required for the validity of a solution. Every solution must satisfy these lazy constraints so when we find a solution, we have to check it that it does. If a solution doesn't automatically satisfy a lazy constraint then the lazy constraint must be added to the model to remove this solution.
user cuts are typically added in the MIPNODE callback
User cuts are not needed for the validity of the model, but remove part of the solution space that belongs to the LP relaxation, but not the feasible region, i.e. cuts help the LP relaxation better approximate the feasible region. Typically cuts are constructed using the LP solution at the node, and are intended to remove that LP solution (and other neighboring LP-feasible solutions) from the linear relaxation. Since a cut cannot remove a integer feasible solution then it can't be used as a basis for a cut generation procedure.
- Riley
0 -
Thank you, Riley, for your detailed responses.
As my final question, I'm working on a Vehicle Routing Problem (VRP) and am attempting to incorporate subtour elimination constraints into the branch and bound nodes (where == GRB.Callback.MIPNODE) as cuts, following the separation algorithm. However, I'm facing inconsistency when using cbLazy and cbCut. Would you please clarify the reasoning behind this? I anticipated identical outcomes.And also, I was wondering if I want to add a Benders cut for a continuous solution (where == GRB.Callback.MIPNODE), which one should I use?
I was thinking that I should add both types of cuts using cbCut.
0 -
Hi Farzad,
In the terminology used at Gurobi lazy constraints and cuts are two different things, and shouldn't be used interchangeably.
Subtour elimination constraints are not cuts, since they are needed for validity. You can give cuts to Gurobi and it may not use them ---> big problem if they are needed for a solution to be valid.
For classical Benders, use MIPSOL, and use cbLazy - do not add benders "cuts" as cuts since they are necessary for validity.
- Riley
0 -
Hi, I'm working on a similar problem. Thank you for the detailed clarification of MIPSOL/MIPNODE in your first response.
In my case, I wish to do subtour elimination on fractional solutions (via a max-flow algorithm). Is the correct approach to declare the variables in the model as binary (as they should be) and then act within MIPNODE callbacks? In fact, it's not just subtour elimination, I wish to add other inequalities based on the LP relaxation too. They are needed to make the solution valid.However, I'm running into the issue that MIPNODE is never reached. The optimisation terminates with an "optimal" solution, which would be detected as infeasible if my code in the MIPNODE callback was reached.
0 -
Hi Taihao,
Yes MIPNODE callbacks sound like the correct approach for you.
Can you verify the MIPNODE callback is never reached with a simple print statement inside the callback? If so then can you post the beginning and end of your log file, and also your callback code?
- Riley
0 -
Hi Riley,
thanks for your quick response. It appears so that MIPNODE callback is not reached. I put a print statement at the beginning of the callback:
(my code is in Kotlin, it's using entirely the Java API of Gurobi though)
class MainCallback(val model: FischettiGTSPModel) : GRBCallback() {
override fun callback() {
if (where == GRB.CB_MIPNODE) {
println("In a MIPNODE callback right now")
val validIneq = FischettiGsec(model.x.getNodeRel(), model.y.getNodeRel(), this).calculateCallback()
validIneq.forEach { addCut(it.lhs, it.sense, it.rhs) }
}
}Log file:
(I'm not sure what you mean by "beginning and end". If you'd kindly explain to me what the "middle" part of the log file is, I'll know the next time around, thanks!)
Set parameter PreCrush to value 1
Set parameter LogFile to value "out/unit_F2_m5_C30_a3_0.log"
Set parameter TimeLimit to value 300
Set parameter DisplayInterval to value 10
Gurobi Optimizer version 11.0.0 build v11.0.0rc2 (win64 - Windows 10.0 (19045.2))
CPU model: 12th Gen Intel(R) Core(TM) i7-12700F, instruction set [SSE2|AVX|AVX2]
Thread count: 12 physical cores, 20 logical processors, using up to 20 threads
Optimize a model with 20 rows, 136 columns and 272 nonzeros
Model fingerprint: 0xa8081ab4
Variable types: 0 continuous, 136 integer (136 binary)
Coefficient statistics:
Matrix range [1e+00, 2e+00]
Objective range [1e+00, 4e+01]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 1e+00]
Found heuristic solution: objective 80.0000000
Presolve removed 2 rows and 2 columns
Presolve time: 0.00s
Presolved: 18 rows, 134 columns, 268 nonzeros
Variable types: 0 continuous, 134 integer (134 binary)
Root relaxation: objective 2.000000e+01, 6 iterations, 0.00 seconds (0.00 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 20.00000 0 4 80.00000 20.00000 75.0% - 0s
H 0 0 72.0000000 20.00000 72.2% - 0s
H 0 0 30.0000000 20.00000 33.3% - 0s
0 0 20.00000 0 4 30.00000 20.00000 33.3% - 0s
Explored 1 nodes (6 simplex iterations) in 0.00 seconds (0.00 work units)
Thread count was 20 (of 20 available processors)
Solution count 3: 30 72 80
Optimal solution found (tolerance 1.00e-04)
Best objective 3.000000000000e+01, best bound 3.000000000000e+01, gap 0.0000%
User-callback calls 163, time in user-callback 0.00 sec
Process finished with exit code 00 -
Hi Taihao,
The MIPNODE callback is triggered at the end of a cut pass and my guess is that the model is solved before the cut pass has concluded. This hypothesis is also supported by the fact there are no cutting planes reported at the end of the log file.
Can you try setting Heuristics=0 and see if this makes a difference?
- Riley
0 -
Hi Riley,
I'm afraid that doesn't change much. This is a fairly small instance, so I guess the model is solved before diverting to cutting planes (?). Of course, this process should (in theory) yield feasible solutions for instances of any size though.
Set parameter Heuristics to value 0
[...]
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 20.00000 0 4 - 20.00000 - - 0s
H 0 0 30.0000000 20.00000 33.3% - 0s
Explored 1 nodes (6 simplex iterations) in 0.00 seconds (0.00 work units)
Thread count was 20 (of 20 available processors)
Solution count 1: 30
Optimal solution found (tolerance 1.00e-04)0 -
I think this instance is just too small/too easy to get the behavior you want. You can see even with turning Heuristics off an optimal solution is found (likely due to probing) almost instantaneously.
Can you try with a larger instance?
0 -
Hi Riley,
you are right that a larger instance works as expected. Meanwhile, I have worked out a workaround where I use a strategy pattern to retrieve fractional solutions in MIPNODE and integer solutions from MIPSOL, feeding either one to my separation algorithm.
The individual strategies also mandate whether to addCut or addLazy at the end. This works for the couple of instances I have tested, although it feels weird to rely on such a workaround.
If you know of any better way I can handle this within Gurobi, please do let me know.
I appreciate your patience. -Taihao
0 -
Hi Taihao,
I might be missing something, but why does this approach feel like it's a workaround?
- Riley
0 -
Thank you, Riley, for your time and responses.
0
サインインしてコメントを残してください。
コメント
13件のコメント