Root relaxation solution
AnsweredHi Gurobi Community,
I am solving a large MILP. Can the root relaxation result in a slightly different objective (1.2% difference) when formulating the problem in a different way?
What I mean by formulating is to refram the problem without any relaxation, which means both formulations are supposed to yield the same solution.
Why is the number of nonzeros differernt? Is it becasue some of the bounds are no longer zeros?
first solution:
Optimize a model with 93556 rows, 84873 columns and 305536 nonzeros
Model fingerprint: 0x841cd513
Model has 18 general constraints
Variable types: 73641 continuous, 11232 integer (11232 binary)
Coefficient statistics:
Matrix range [3e06, 1e+06]
Objective range [1e+00, 1e+00]
Bounds range [8e05, 2e+03]
RHS range [3e06, 2e+02]
Presolve removed 67699 rows and 56301 columns
Presolve time: 1.53s
Presolved: 25857 rows, 28572 columns, 100341 nonzeros
Variable types: 18586 continuous, 9986 integer (9982 binary)
Deterministic concurrent LP optimizer: primal and dual simplex
Showing primal log only...
Concurrent spin time: 0.00s
Solved with dual simplex
Use crossover to convert LP symmetric solution to basic solution...
Root relaxation: objective 8.718869e+06, 13580 iterations, 1.36 seconds (0.55 work units)
Nodes  Current Node  Objective Bounds  Work
Expl Unexpl  Obj Depth IntInf  Incumbent BestBd Gap  It/Node Time
* 0 0 0 8718869.0423 8718869.04 0.00%  3s
Explored 1 nodes (14636 simplex iterations) in 3.32 seconds (1.55 work units)
Thread count was 8 (of 8 available processors)
Solution count 1: 8.71887e+06
Optimal solution found (tolerance 1.00e04)
Best objective 8.718869042270e+06, best bound 8.718869042270e+06, gap 0.0000%
Second solution:
Optimize a model with 93556 rows, 84873 columns and 306454 nonzeros
Model fingerprint: 0x0dc9fb34
Model has 18 general constraints
Variable types: 73641 continuous, 11232 integer (11232 binary)
Coefficient statistics:
Matrix range [3e06, 1e+06]
Objective range [1e+00, 1e+00]
Bounds range [8e05, 2e+03]
RHS range [3e06, 2e+02]
Presolve removed 67699 rows and 58086 columns
Presolve time: 1.27s
Presolved: 25857 rows, 26787 columns, 98683 nonzeros
Variable types: 16801 continuous, 9986 integer (9982 binary)
Found heuristic solution: objective 6060340.8037
Found heuristic solution: objective 8024900.0865
Root relaxation: objective 8.830787e+06, 14567 iterations, 0.89 seconds (0.51 work units)
Nodes  Current Node  Objective Bounds  Work
Expl Unexpl  Obj Depth IntInf  Incumbent BestBd Gap  It/Node Time
* 0 0 0 8830786.9635 8830786.96 0.00%  3s
Explored 1 nodes (15784 simplex iterations) in 3.79 seconds (2.25 work units)
Thread count was 8 (of 8 available processors)
Solution count 3: 8.83079e+06 8.0249e+06 6.06034e+06
Optimal solution found (tolerance 1.00e04)
Best objective 8.830786963523e+06, best bound 8.830786963523e+06, gap 0.0000%

Hi Hussein,
The first difference I see in the files is between these two lines:
Presolve removed 67699 rows and 56301 columns
Presolve removed 67699 rows and 58086 columns
There is a class of presolve reductions called "Dual Reductions" which use the objective function to infer ways that the model can be made simplified. These reductions aim to reduce the feasible region while ensuring at least one optimal solution exists. Changing the objective function is likely affecting the dual reductions which are applied. Try setting Presolve=0 and solving, then setting DualReductions=0 and solving, and see how it affects the LP solution.
 Riley
0
Please sign in to leave a comment.
Comments
1 comment