Skip to main content

Differance between MIPSOL and MIPNODE

Answered

Comments

13 comments

  • Riley Clement
    Gurobi Staff Gurobi Staff

    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
  • farzad avishan
    First Comment
    Gurobi-versary
    First Question

    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
  • Riley Clement
    Gurobi Staff Gurobi Staff

    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
  • Taihao Zhang
    Conversationalist

    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
  • Riley Clement
    Gurobi Staff Gurobi Staff

    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
  • Taihao Zhang
    Conversationalist

    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 0
    0
  • Riley Clement
    Gurobi Staff Gurobi Staff

    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
  • Taihao Zhang
    Conversationalist

    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
  • Riley Clement
    Gurobi Staff Gurobi Staff

    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
  • Taihao Zhang
    Conversationalist

    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
  • Riley Clement
    Gurobi Staff Gurobi Staff

    Hi Taihao,

    I might be missing something, but why does this approach feel like it's a workaround?

    - Riley

    0
  • farzad avishan
    First Comment
    Gurobi-versary
    First Question

    Thank you, Riley, for your time and responses.

    0

Please sign in to leave a comment.