Is ObjBoundC ensured to be a valid bound?

回答済み

Daisy Wang

2025年06月23日 18:09

• 
• 

Is ObjBoundC ensured to be a valid bound (i.e., an upper bound in a maximization problem and a lower bound in a minimization problem) throughout the computation?

My understanding is that, in a maximization problem, ObjBoundC provides a potentially “loose” upper bound at the beginning of the solve, and this bound should only improve (i.e., decrease) as the computation progresses. I haven’t found any documentation suggesting that the bound could move in the opposite direction.

However, I encountered unexpected behavior while solving an s–t orienteering problem (maximizing collected prize). Specifically, Gurobi initially returned a bound that was lower than the value computed by a heuristic algorithm. When I inserted the heuristic solution into Gurobi, it accepted the solution and updated the bound, suggesting that the previous bound was not a valid upper bound.

• Without plugging in the heuristic solution, Gurobi returned an upper bound of 0.765637.
• After inserting the heuristic solution, the bound increased to 0.766293, which matches the objective value of the heustric solution.

I’ve attached the Gurobi log snippet for this case. From what I can tell, the inserted solution was loaded and accepted successfully. There were no infeasibility errors, and Gurobi returned that solution as the optimal one.

...
H    0     0                       0.6638678    0.76564  15.3%     - 2864s
H    0     0                       0.7006985    0.76564  9.27%     - 3239s
H    0     0                       0.7011054    0.76564  9.20%     - 3383s

Gurobi 12.0.1 (linux64, C++) logging started Sat Jun 21 17:10:12 2025

Set parameter Username
Set parameter LicenseID to value 2620120
Set parameter LogFile to value "gurobi_tsp.log"
Academic license - for non-commercial use only - expires 2026-02-10
Set parameter TimeLimit to value 108000
Gurobi Optimizer version 12.0.1 build v12.0.1rc0 (linux64 - "Rocky Linux 8.10 (Green Obsidian)")

CPU model: Intel(R) Xeon(R) Gold 5118 CPU @ 2.30GHz, instruction set [SSE2|AVX|AVX2|AVX512]
Thread count: 24 physical cores, 48 logical processors, using up to 24 threads

Non-default parameters:
TimeLimit  108000

Optimize a model with 806404 rows, 805505 columns and 6424320 nonzeros
Model fingerprint: 0x28e4b6d0
Variable types: 0 continuous, 805505 integer (804609 binary)
Coefficient statistics:
  Matrix range     [5e-01, 2e+03]
  Objective range  [2e-05, 1e-02]
  Bounds range     [1e+00, 9e+02]
  RHS range        [1e+00, 1e+03]

Warning: Completing partial solution with 803761 unfixed non-continuous variables out of 805505
User MIP start produced solution with objective 0.766293 (1.95s)
Loaded user MIP start with objective 0.766293
Processed MIP start in 1.94 seconds (1.11 work units)

Presolve removed 2697 rows and 2695 columns (presolve time = 5s)...
Presolve removed 2697 rows and 3591 columns (presolve time = 10s)...
Presolve removed 4488 rows and 4485 columns (presolve time = 15s)...
Presolve removed 7170 rows and 5379 columns (presolve time = 20s)...
Presolve removed 7170 rows and 5379 columns (presolve time = 25s)...
Presolve removed 7170 rows and 5379 columns (presolve time = 30s)...
Presolve removed 8955 rows and 7165 columns (presolve time = 35s)...
Presolve removed 7167 rows and 5377 columns
Presolve time: 38.39s
Presolved: 799237 rows, 800128 columns, 4787370 nonzeros
Variable types: 0 continuous, 800128 integer (799235 binary)
Deterministic concurrent LP optimizer: primal simplex, dual simplex, and barrier
Showing barrier log only...

Root barrier log...

Ordering time: 0.92s

Barrier statistics:
 Dense cols : 893
 AA' NZ     : 4.787e+06
 Factor NZ  : 8.379e+06 (roughly 700 MB of memory)
 Factor Ops : 6.457e+09 (less than 1 second per iteration)
 Threads    : 22

                  Objective                Residual
Iter       Primal          Dual         Primal    Dual     Compl     Time
   0   4.80710024e+04  2.55225935e+06  8.62e+06 1.02e-02  2.17e+02    52s
   1   4.39496981e+04  2.86287085e+06  7.98e+06 4.91e-02  2.01e+02    52s
   2   2.37128911e+04  3.92503735e+06  4.32e+06 3.63e-02  1.15e+02    53s
   3   2.36011250e+03  4.61040657e+06  4.28e+05 9.03e-14  1.31e+01    54s
   4   6.49912992e+02  4.33772762e+06  1.17e+05 8.01e-14  4.71e+00    55s
   5   4.35889266e+02  2.66962917e+06  7.69e+04 7.44e-14  2.59e+00    55s
   6   1.53111640e+02  4.66441671e+05  2.67e+04 5.33e-14  5.19e-01    56s
   7   3.61764962e+01  2.28541523e+04  6.21e+03 1.07e-14  7.52e-02    56s
   8   2.17058120e+01  1.63662162e+04  3.68e+03 8.88e-15  4.52e-02    57s
   9   1.53031463e+01  1.48074570e+04  2.55e+03 1.11e-14  3.26e-02    57s
  10   1.15174749e+01  8.74384885e+03  1.89e+03 1.39e-14  2.25e-02    58s
  11   7.58753121e+00  6.78365292e+03  1.20e+03 5.89e-14  1.42e-02    58s
  12   4.91023848e+00  5.74962494e+03  7.32e+02 3.67e-14  9.12e-03    59s
  13   3.46818739e+00  4.61120115e+03  4.79e+02 1.61e-14  6.07e-03    59s
  14   2.09985987e+00  3.52718631e+03  2.40e+02 4.22e-14  3.36e-03    60s
  15   9.82586715e-01  2.29774621e+03  4.60e+01 7.57e-14  1.25e-03    60s
  16   7.25689530e-01  2.09957707e+03  4.26e+00 2.39e-14  9.01e-04    61s
  17   6.99126727e-01  1.49303513e+03  2.02e-01 2.37e-14  6.23e-04    61s
  18   6.92217277e-01  1.06887837e+03  4.10e-02 6.96e-14  4.46e-04    62s
  19   6.91819795e-01  8.53326929e+02  2.12e-02 1.82e-14  3.56e-04    63s
  20   6.91856867e-01  7.43513420e+02  1.59e-02 1.21e-14  3.10e-04    63s
  21   6.91919476e-01  6.68326042e+02  1.01e-02 1.10e-14  2.78e-04    64s
  22   6.92059255e-01  6.22662099e+02  4.70e-03 9.89e-15  2.59e-04    64s
  23   6.91713035e-01  3.36379259e+02  1.38e-06 1.13e-14  1.40e-04    65s
  24   6.93895102e-01  2.49734121e+00  1.31e-14 4.13e-15  7.52e-07    65s
  25   7.22633489e-01  1.92593068e+00  7.24e-14 2.85e-15  5.02e-07    66s
  26   7.37249422e-01  1.32653261e+00  1.30e-13 1.35e-15  2.46e-07    66s

Barrier performed 26 iterations in 66.17 seconds (51.34 work units)
Barrier solve interrupted - model solved by another algorithm

Concurrent spin time: 8.79s (can be avoided by choosing Method=3)

Solved with primal simplex

Root relaxation: cutoff, 64173 iterations, 20.36 seconds (11.29 work units)

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

     0     0     cutoff    0         0.76629    0.76629  0.00%     -   66s

Explored 1 nodes (64173 simplex iterations) in 66.34 seconds (51.39 work units)
Thread count was 24 (of 48 available processors)

Solution count 1: 0.766293 
No other solutions better than 0.766293

Optimal solution found (tolerance 1.00e-04)
Best objective 7.662928900157e-01, best bound 7.662928900157e-01, gap 0.0000%

User-callback calls 7522, time in user-callback 0.00 sec

Could you please help clarify whether there is anything incorrect in my interpretation above? If my understanding is correct, I would also appreciate a better explanation of what the "best bound" (i.e., ObjBoundC) actually represents during the MIP solve.

We are hoping to use this bound to roughly quantify the performance of our heuristic algorithm in large problem sizes.

関連

• C++
• Best Bound

0

• 

  Riley Clement

  • Gurobi Staff

  2025年06月25日 00:10

  Hi Daisy,

  Is ObjBoundC ensured to be a valid bound (i.e., an upper bound in a maximization problem and a lower bound in a minimization problem) throughout the computation?

  In the absence of bugs, yes.

  My understanding is that, in a maximization problem, ObjBoundC provides a potentially “loose” upper bound at the beginning of the solve

  It is potentially loose, it is potentially tight - this depends on the model.  In most cases ObjBoundC is going to be the same as ObjBound.

  When I inserted the heuristic solution into Gurobi, it accepted the solution and updated the bound, suggesting that the previous bound was not a valid upper bound.

  This could be buggy, although perhaps there are small violations (constraint or bound or integer) within tolerances that allow the heuristic solution to be accepted.

  I would also appreciate a better explanation of what the "best bound" (i.e., ObjBoundC) actually represents during the MIP solve

  The best bound is coming from LP relaxations.  For a minimization problem it's going to be the minimum value of the LP relaxation at all unexplored nodes.  Typically though you would just use ObjBound, which uses integrality information - i.e. if you know the objective should be integer and the value of an LP relaxation is fractional, you can round it up (for a minimization).

  If you'd like me to take a look at the issue regarding the heuristic solution and lower bound contradicting then please share a model file (MPS) and solution file (SOL) using a service such as Google Drive, Dropbox, Github etc.

  - Riley

  0
• 

  Daisy Wang

  2025年07月07日 20:23

  • 
  • 

  Hi Riley,

  Thank you very much for your prompt and helpful response.

  I’ve isolated and cleaned up the code, and uploaded it to GitHub [https://github.com/Daisy0419/Orienteering-Problem-with-Gurobi-Solver.git]. It would be greatly appreciated if you could take a closer look.

  The problematic case is for data file GW191127_050227 with a time budget of 1400. I’ve also included the heuristic solution we generated (as init_solution) for this instance. If you run the code with and without the init solution, you’ll see the behavior I described:

  - Without the heuristic solution, Gurobi returns a best bound (ObjBoundC) of 0.765767
  - With the solution provided, Gurobi accepts it as a feasible solution and updates the bound to 0.766293

  This behavior seems inconsistent with the expectation that ObjBoundC should always remain a valid upper bound in a maximization problem.

  The original code is in cpp. I also translated the instance into AMPL format (located in the AMPL_formation directory) in case that’s more convenient for you to review.

  Additionally, we tested the same case using CPLEX under identical constraints. The results were:

  - GCP(our heuristic) solution: 0.766293
  - CPLEX upper bound (without plugging in GCP solution): 0.766367
  - CPLEX upper bound (after plugging in GCP solution): 0.766367
  which suggests that the bound of CPLEX is well above the solution from our heuristic, and remains unchanged after inserting the init_solution.

  This somehow contrasts with Gurobi's behaviour, where the bound improves after inserting the known feasible solution.

  We've identified a few other similar cases as well. I’d be happy to share them if it would help with debugging or further investigation.

  Thanks again, and I look forward to hearing your thoughts.

  Best regards,
  Daisy

  0
• 

  Riley Clement

  • Gurobi Staff

  2025年07月07日 22:52

  Thanks Daisy, I'll take a look and see if I can replicate the issue.

  - Riley

  0
• 

  Riley Clement

  • Gurobi Staff

  2025年07月08日 09:58

  Hi Daisy,

  The issue is coming from the very small objective coefficients:

  Coefficient statistics:
   Matrix range     [5e-01, 2e+03]
   Objective range  [2e-05, 1e-02]
   Bounds range     [1e+00, 9e+02]
   RHS range        [1e+00, 1e+03]

  Our machines use floating point arithmetic and the limitations of this must be navigated by using tolerances.  The tolerances are an absolute, not relative, value and the default value of OptimalityTol (1e-6) is not much smaller than these objective coefficients meaning it is relatively loose in comparison.

  There are a couple of things you can do to fix the issue:

  • Tighten OptimalityTol  - 1e-7 looks to be enough
  • Scale the objective function, either manually, or with ObjScale - I tried ObjScale=0.01 and it also seemed to resolve the issue.

  You can read more about tolerances and numerics in this section of our Guidelines for Numerical Issues.

  - Riley

   

  1
• 

  Daisy Wang

  2025年07月09日 19:41

  • 
  • 

  Hi Riley,

  Thank you again for your explanation and suggestions.

  I followed your recommendations and experimented with tightening OptimalityTol and adjusting ObjScale:

  model.set(GRB_DoubleParam_OptimalityTol, 1e-7);
  model.set(GRB_DoubleParam_ObjScale, 0.01);

  With OptimalityTol <= 1e-7 or ObjScale <= 0.01, the reported objBound becomes consistent (up to 7 digits) before and after I plug in the GCP heuristic solution. In these cases, the bound remains well above the GCP solution, so the earlier inconsistency is resolved.

  But I’m still unsure whether the reported bound in these cases should be considered a reliable UPPER bound, since the bound value shifts depending on the specific tolerance or scaling value:

  ObjScale vs. objBound:
  ObjScale = 0.01   → objBound = 0.7663953617142  
  ObjScale = 0.001  → objBound = 0.7664111072815  
  ObjScale = 0.0001 → objBound = 0.7664127461065  

  OptimalityTol vs. objBound:
  OptimalityTol = 1e-7 → objBound = 0.7663133514886  
  OptimalityTol = 1e-8 → objBound = 0.7663991915745  
  OptimalityTol = 1e-9 → objBound = 0.7664121034737  

  For comparison, I tried a similar setting in CPLEX:

  cplex.setParam(IloCplex::Param::MIP::Tolerances::AbsMIPGap, 1e-7);

  And changing this value (from the default 1e-6 to 1e-9) did not seem to change the reported bound, which remained fixed at:
  objBound = 0.766367

  I'm not sure whether this value is more reliable or if it’s simply because of different numerical handling in CPLEX.

  I understand this is fundamentally a numerical issue. Does this mean that relying on Gurobi's BestBound to estimate the performance of other algorithms may be unreliable when objective coefficients are very small?

  Thanks again for your help.

  Best regards,
  Daisy
   

   

   

  0
• 

  Daisy Wang

  2025年07月09日 20:20

  • 
  • 

  Actually, the differences in the reported bounds under different tolerance settings are small enough to be ignored in practice. Just to double confirm, would you say it's safer to set OptimalityTol to a smaller value (e.g., 1e-9) to ensure that the reported BestBound is a reliable upper bound on the true optimal value?

  0
• 

  Riley Clement

  • Gurobi Staff

  2025年07月09日 23:43

  Hi Daisy,

  But I’m still unsure whether the reported bound in these cases should be considered a reliable UPPER bound, since the bound value shifts depending on the specific tolerance or scaling value

  This is not Gurobi specific, unfortunately we must take numerics into consideration when building a model and setting tolerances.  

  Ask your computer if the following is true 0.2 + 0.1 == 0.3 , e.g. in Python print(0.1 + 0.2 == 0.3).  The answer will be false, because the result of 0.2 + 0.1 is 0.30000000000000004, so this comparison needs to be done with a tolerance involved and the answer will be dependent on the tolerance.  Does this mean the result is unreliable?  If your answer is yes, then in general you can consider all computation on digital machines unreliable. 

  For comparison, I tried a similar setting in CPLEX:

  cplex.setParam(IloCplex::Param::MIP::Tolerances::AbsMIPGap, 1e-7);

  This is not a similar parameter and would not affect the bound in the same way.  (Our MIPGapAbs parameter is the equivalent).  The equivalent in CPLEX would be IloCplex::Param::Simplex::Tolerances::Optimality.

  Just to double confirm, would you say it's safer to set OptimalityTol to a smaller value (e.g., 1e-9) to ensure that the reported BestBound is a reliable upper bound on the true optimal value?

  If tolerances are loose the solver can accept solutions which are theoretically not feasible.  If they are too tight the solver can reject solutions which are theoretically feasible.  This sounds like a balancing game but for the vast majority of models there is no issue assuming it has been constructed in accordance with best practice.

  So yes, setting OptimalityTol=1e-9 will get you a more reliable upper bound, but it may make the “optimality” of the best solution unreliable.

  In your case I would solve the issue by manually scaling the objective up by multiplying it by 1000, but this is a personal preference.

  - Riley

   

  1
• 

  Daisy Wang

  2025年07月10日 04:03

  • 
  • 

  Hi Riley,

  I see. Thanks a million for your patience and clear explanation, it’s been very helpful. I really appreciate your time and support!

  Best regards, 
  Daisy

  0
• 

  Riley Clement

  • Gurobi Staff

  2025年07月10日 07:01

  No problem at all Daisy, best of luck!

  0

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