Skip to main content

same LP solution multiple times in root node, user cuts ignored

Mario Ruthmair
Gurobi-versary
First Comment
First Question

Dear support team,

I am working on a branch-and-cut algorithm using the C++ interface of Gurobi to add user cuts via callbacks. While I know that Gurobi heuristically decides which user cuts to accept based on recent dual bound improvements, amount of violation, numerics, etc., I still wonder whether there are possibilities to influence this behavior as a user. In particular, I observed the same LP solution in the root node in multiple subsequent iterations, repeatedly ignoring my user cuts. See for example the following log output:

GRB_IntParam_PreCrush = 1
GRB_DoubleParam_MIPGapAbs = 0.0
GRB_DoubleParam_MIPGap = 0.0
GRB_IntParam_Threads = 1
GRB_IntParam_CutPasses = GRB_MAXINT
GRB_DoubleParam_Heuristics = 0.0
GRB_IntParam_Presolve = 0
GRB_DoubleParam_NodeLimit = 1

Gurobi Optimizer version 9.1.2 build v9.1.2rc0 (linux64)
Thread count: 4 physical cores, 8 logical processors, using up to 1 threads
Optimize a model with 104 rows, 1377 columns and 2904 nonzeros
Model fingerprint: 0x5cc91332
Variable types: 0 continuous, 1377 integer (1276 binary)
Coefficient statistics:
  Matrix range     [1e+00, 2e+00]
  Objective range  [2e+00, 9e+01]
  Bounds range     [1e+00, 2e+01]
  RHS range        [9e+00, 5e+01]
Variable types: 0 continuous, 1377 integer (1276 binary)

Root relaxation: objective 5.275486e+02, 92 iterations, 0.00 seconds

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

     0     0  527.54858    0    8          -  527.54858      -     -    0s
	User cut callback 1: MIPNODE_OBJBND = 527.55, MIPNODE_STATUS = 2
	add User-YCAP violated by 6.74 (absolute)
	add User-RCAP violated by 3.00 (absolute)
	add User-RCAP violated by 6.00 (absolute)
	add User-YCAP violated by 5.90 (absolute)
	add User-YCAP violated by 4.90 (absolute)
	add User-YCAP violated by 6.74 (absolute)
	add User-RCAP violated by 3.00 (absolute)
	add User-YCAP violated by 5.74 (absolute)
	add User-YCAP violated by 5.74 (absolute)
	add User-YCAP violated by 5.74 (absolute)
	add User-YCAP violated by 5.74 (absolute)
     0     0  576.19050    0   23          -  576.19050      -     -    0s
	User cut callback 2: MIPNODE_OBJBND = 576.19, MIPNODE_STATUS = 2
	add User-RCAP violated by 5.45 (absolute)
	add User-YCAP violated by 5.32 (absolute)
	add User-RCAP violated by 1.28 (absolute)
	add User-YCAP violated by 1.04 (absolute)
     0     0  594.84696    0   32          -  594.84696      -     -    0s
	User cut callback 3: MIPNODE_OBJBND = 594.85, MIPNODE_STATUS = 2
	add User-RCAP violated by 6.39 (absolute)
	add User-YCAP violated by 5.68 (absolute)
	add User-RCAP violated by 2.00 (absolute)
	add User-YCAP violated by 1.39 (absolute)
     0     0  597.50508    0   28          -  597.50508      -     -    0s
	User cut callback 4: MIPNODE_OBJBND = 597.51, MIPNODE_STATUS = 2
	add User-RCAP violated by 6.16 (absolute)
	add User-YCAP violated by 5.71 (absolute)
	add User-RCAP violated by 6.50 (absolute)
	add User-YCAP violated by 5.56 (absolute)
     0     0  614.65124    0    6          -  614.65124      -     -    0s
	User cut callback 5: MIPNODE_OBJBND = 614.65, MIPNODE_STATUS = 2
	add User-RCAP violated by 5.00 (absolute)
	add User-YCAP violated by 4.53 (absolute)
	add User-RCAP violated by 3.50 (absolute)
	add User-YCAP violated by 3.29 (absolute)
	add User-RCAP violated by 4.00 (absolute)
	add User-YCAP violated by 3.14 (absolute)
     0     0  623.31833    0   38          -  623.31833      -     -    0s
	User cut callback 6: MIPNODE_OBJBND = 623.32, MIPNODE_STATUS = 2
	add User-RCAP violated by 4.20 (absolute)
	add User-YCAP violated by 3.31 (absolute)
	add User-RCAP violated by 2.35 (absolute)
	add User-YCAP violated by 1.66 (absolute)
	add User-RCAP violated by 1.40 (absolute)
	add User-RCAP violated by 1.95 (absolute)
	add User-YCAP violated by 1.37 (absolute)
	add User-RCAP violated by 2.05 (absolute)
	add User-YCAP violated by 1.09 (absolute)
	add User-RCAP violated by 2.85 (absolute)
	add User-YCAP violated by 2.62 (absolute)
	add User-RCAP violated by 3.10 (absolute)
	add User-YCAP violated by 2.22 (absolute)
	add User-RCAP violated by 3.15 (absolute)
	add User-YCAP violated by 2.18 (absolute)
	add User-RCAP violated by 4.10 (absolute)
	add User-YCAP violated by 3.13 (absolute)
	add User-RCAP violated by 4.20 (absolute)
	add User-YCAP violated by 3.31 (absolute)
	add User-RCAP violated by 1.20 (absolute)
	add User-YCAP violated by 1.18 (absolute)
	add User-RCAP violated by 1.40 (absolute)
	add User-YCAP violated by 1.20 (absolute)
     0     0  624.30329    0   39          -  624.30329      -     -    0s
	User cut callback 7: MIPNODE_OBJBND = 624.30, MIPNODE_STATUS = 2
	add User-RCAP violated by 4.53 (absolute)
	add User-YCAP violated by 3.74 (absolute)
	add User-RCAP violated by 4.53 (absolute)
	add User-YCAP violated by 3.74 (absolute)
     0     0  624.30329    0   39          -  624.30329      -     -    0s
	User cut callback 8: MIPNODE_OBJBND = 624.30, MIPNODE_STATUS = 2
	add User-RCAP violated by 4.53 (absolute)
	add User-YCAP violated by 3.74 (absolute)
	add User-RCAP violated by 4.53 (absolute)
	add User-YCAP violated by 3.74 (absolute)
	User cut callback 9: MIPNODE_OBJBND = 624.30, MIPNODE_STATUS = 2
	add User-RCAP violated by 4.53 (absolute)
	add User-YCAP violated by 3.74 (absolute)
	add User-RCAP violated by 4.53 (absolute)
	add User-YCAP violated by 3.74 (absolute)
     0     2  624.35432    0   39          -  624.35432      -     -    0s

Cutting planes:
  User: 11
  MIR: 8
  StrongCG: 1
  Zero half: 2

Explored 1 nodes (299 simplex iterations) in 0.11 seconds
Thread count was 1 (of 8 available processors)

Solution count 0

Node limit reached
Best objective -, best bound 6.243543232225e+02, gap -

User-callback calls 98, time in user-callback 0.06 sec
=====
My own counters:
Solver callback: total time: 0.06 sec., #calls = 9
  User-YCAP: 34 added
  User-RCAP: 30 added

Based on this, the following questions came up:

  1. The LP solutions in user cut callback 7, 8, and 9, are exactly the same (I compared all variable values with full double precision and there are not even epsilon differences). Clearly, my (deterministic) separation routines find the same violated user cuts and they seem to be repeatedly ignored. Why is the MIPNODE callback with status GRB_OPTIMAL called multiple times for the same LP solution?
  2. The found user cuts are violated by a significant amount, not only by epsilon, and most coefficients are 1 or -1, so they seem to be numerically quite safe. Is there some possibility to manually "force" user cut acceptance? I tried to set the parameter GRB_IntParam_Cuts to 3 (aggressive) but this only seems to influence the internal cut generation.
  3. If I disable internal cuts by setting Cuts=0, increasing the CutPasses parameter has no effect on the user cut rounds, right?
  4. At the end Gurobi says "User-callback calls 98". What does it mean? I only counted 9 calls.

I would be happy for all kinds of suggestions!
Best regards, Mario

1

Comments

1 comment

Date Votes
  • Mario Ruthmair
    Gurobi-versary
    First Comment
    First Question

    The answer to question 4 is in fact easy: It is the total number of callback calls, including POLLING, PRESOLVE, MIPSOL, MIPNODE, etc., not only the user-cut callbacks.

    Best regards, Mario

    0

Please sign in to leave a comment.

Didn't find what you were looking for?

New post