What does "Root relaxation: interrupted" mean, and where does lower bound come from if root relaxation is interrupted?
Answered
I have a model where gurobi's root relaxation is reported as interrupted, but I get a solution within the suboptimality bound I wanted (the solution is found using a heuristic). See the log text pasted below. If the root relaxation was interrupted, where is the lower bound in the log file coming from?
Gurobi 11.0.2 (linux64) logging started Tue Jul 23 19:13:11 2024
Set parameter LogFile to value "/home/cobra/catkin_ws/src/mapf/data/07_23_24/sampled_points_arm_20240723-190027/20240723-191309//log.txt"
Gurobi Optimizer version 11.0.2 build v11.0.2rc0 (linux64 - "Ubuntu 20.04.6 LTS")
CPU model: Intel(R) Core(TM) i9-9820X CPU @ 3.30GHz, instruction set [SSE2|AVX|AVX2|AVX512]
Thread count: 10 physical cores, 20 logical processors, using up to 20 threads
Optimize a model with 1154 rows, 33487 columns and 200356 nonzeros
Model fingerprint: 0xd17851eb
Variable types: 1 continuous, 33486 integer (33486 binary)
Coefficient statistics:
Matrix range [1e+00, 1e+00]
Objective range [2e-01, 4e+01]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 2e+01]
Presolve removed 673 rows and 2099 columns
Presolve time: 0.22s
Presolved: 481 rows, 31388 columns, 63453 nonzeros
Variable types: 1 continuous, 31387 integer (31387 binary)
Found heuristic solution: objective 37.8155501
Root relaxation: interrupted, 1172 iterations, 0.13 seconds (0.33 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 - 0 37.81555 36.93217 2.34% - 0s
Explored 1 nodes (1172 simplex iterations) in 0.84 seconds (0.89 work units)
Thread count was 20 (of 20 available processors)
Solution count 1: 37.8156
Optimal solution found (tolerance 4.88e-02)
Best objective 3.781555007819e+01, best bound 3.693217059965e+01, gap 2.3360%
User-callback calls 637, time in user-callback 0.11 sec
-
Hi Anoop,
Gurobi keeps track of the current best bound while solving the root relaxation. Since the incumbent found by the heuristics was within approximately 2.5% of the current best bound before completing the root relaxation, the root relaxation was interrupted. The solution was then declared optimal with a ~2.5% gap.
If you leave the MIPGap parameter at its default value, the root relaxation will be solved to completion.
Best regards,
Maliheh
0 -
Does the bound come from the dual of the root relaxation?
0 -
Does the bound come from the dual of the root relaxation?
Yes, algorithms such as simplex and barrier are iterative approaches that improve the bound at each iteration. The root relaxation was interrupted because the incumbent was within 2.5% of the bound at a particular iteration, for example, t. There was no reason to continue solving it to completion because Gurobi had already found an incumbent that could prove it was within your predefined MIPGap value.
Maliheh
0 -
Thanks!
0
Please sign in to leave a comment.
Comments
4 comments