Simplex method does not stop at optimal solution.
Answered
I'm solving a large-scale LP problem, and I use the known optimal solution as warm start of primal simplex method. (using PStart attribute, as I am unable to provide feasible primal and dual basis). I compare the solution without warm start, and I provided, they are the same. However, the primal simplex method did not stop immediately and even report objective decreasing after few iterations. I'm not sure it is because of degeneracy or numerical issue. Also, I am curious about other possible way to warm start the LP, as I am able to provide a near optimal feasible solution and hoping to speed up the simplex method.
Here is part of the log, as it runs almost forever without stopping.
Set parameter Method to value 0
Set parameter OptimalityTol to value 0.0001
Gurobi Optimizer version 10.0.1 build v10.0.1rc0 (win64)
CPU model: 11th Gen Intel(R) Core(TM) i9-11900H @ 2.50GHz, instruction set [SSE2|AVX|AVX2|AVX512]
Thread count: 8 physical cores, 16 logical processors, using up to 16 threads
Optimize a model with 1654051 rows, 11325 columns and 6638250 nonzeros
Coefficient statistics:
Matrix range [1e+00, 1e+00]
Objective range [1e-02, 5e+01]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 3e+00]
Primal warm-start: 3969 superbasic variables.
Iteration Objective Primal Inf. Dual Inf. Time
0 7.8940841e+01 0.000000e+00 4.138340e+03 1s
560 7.8940841e+01 0.000000e+00 4.562719e+03 5s
960 7.8940841e+01 0.000000e+00 4.085929e+03 11s
1260 7.8940841e+01 0.000000e+00 4.567979e+03 16s
1540 7.8940841e+01 0.000000e+00 5.229463e+03 22s
1710 7.8940841e+01 0.000000e+00 5.240513e+03 26s
1870 7.8940841e+01 0.000000e+00 5.199733e+03 30s
2190 7.8940841e+01 0.000000e+00 6.402724e+03 39s
2350 7.8940841e+01 0.000000e+00 6.981566e+03 44s
2490 7.8940841e+01 0.000000e+00 7.202362e+03 49s
2590 7.8940841e+01 0.000000e+00 8.369070e+03 51s
2760 7.8940841e+01 0.000000e+00 8.372506e+03 56s
3030 7.8940841e+01 0.000000e+00 8.502437e+03 65s
3190 7.8940841e+01 0.000000e+00 8.634612e+03 70s
3340 7.8940841e+01 0.000000e+00 8.400007e+03 75s
3490 7.8940841e+01 0.000000e+00 8.956763e+03 81s
3630 7.8940841e+01 0.000000e+00 8.659808e+03 86s
3770 7.8940841e+01 0.000000e+00 8.586710e+03 92s
3910 7.8940841e+01 0.000000e+00 8.902573e+03 98s
4040 7.8940841e+01 0.000000e+00 7.167271e+03 103s
4140 7.8940841e+01 0.000000e+00 5.779735e+03 108s
4240 7.8940841e+01 0.000000e+00 7.522040e+03 114s
4360 7.8913966e+01 0.000000e+00 6.312472e+04 118s
4460 7.8909749e+01 0.000000e+00 3.349087e+04 122s
-
You could try the following things:
- Update to the latest Gurobi version 11
- Fix all variables to the optimal solution point you have found via equality constraints and check whether the model is declared optimal or infeasible
- Decrease the value of OptimalityTol. Is there a good reason why you increased it? It is usually not a good idea to increase this value as it may lead to unnecessary/bad iterations.
Also, I am curious about other possible way to warm start the LP, as I am able to provide a near optimal feasible solution and hoping to speed up the simplex method.
If you only have a feasible point without basis information, then setting the PStart attribute is the correct and currently only way to warmstart the Simplex method.
If you still run into the described issue, could you please share the model? Note that uploading files in the Community Forum is not possible but we discuss an alternative in Posting to the Community Forum.
Best regards,
Jaromił0 -
Hi Jaromił,
Thanks for your response,
I tried the following things:
- Update to the version 11.
- Set the optimality tolerance to 1e-9.
Same problem still happened.
I also tried fixing all variable to the warm start solution I provided through equality constraints. The model is feasible.
Optimize a model with 1665376 rows, 11325 columns and 6649575 nonzeros
Model fingerprint: 0x85a74491
Coefficient statistics:
Matrix range [1e+00, 1e+00]
Objective range [1e-02, 5e+01]
Bounds range [1e+00, 1e+00]
RHS range [2e-02, 3e+00]
Presolve removed 1665376 rows and 11325 columns
Presolve time: 0.72s
Presolve: All rows and columns removed
Iteration Objective Primal Inf. Dual Inf. Time
0 7.8940841e+01 0.000000e+00 0.000000e+00 1s
Solved in 0 iterations and 1.34 seconds (1.38 work units)
Optimal objective 7.894084143e+01I shared the model through google drive: https://drive.google.com/file/d/18sT7V_TyCFXNzQC8ZEu4SZZ9-NQ9f5Td/view?usp=drive_link.
Thanks!
0 -
Thanks Yakun. Could you please also share an attr file with the PStart information to make the issue reproducible?
0 -
Here is the link for .attr file. https://drive.google.com/file/d/1LpqSDG3r81S8OymagFMpx93JIgXO-Hyr/view?usp=drive_link
0 -
Thank you Yakun. I can confirm that I can reproduce the issue. I will let you know once I have more information about the issue.
0 -
Hi Yakun,
The situation is that the provided optimal solution point has a big dual infeasibility. In such cases, primal Simplex may take a lot of time if the soint is primal degenerate to actually prove optimality despite having an optimal solution point from the start.
This paper by Megiddo shows that having an optimal primal or dual solution alone is asymptotically no better than having no solution at all. Often providing a feasible point as start vector helps but this is not always the case and you ran in one such case where it does not help. What would help is if you would provide basis information via the VBasis attribute.
A different workaround would be to not set Method=0 but just go with defaults. In that case, maybe the dual Simplex or the Barrier algorithm converge to an optimal solution quickly.
Best regards,
Jaromił0 -
Thank you for your response!
0 -
You need to set four properties simultaneously: GRB_DoubleAttr_PStart, GRB_DoubleAttr_DStart, GRB_IntAttr_VBasis, and GRB_IntAttr_CBasis (programming language is C++). In the experiment, only GRB_IntAttr_VBasis and GRB_IntAttr_CBasis also can be used to warm start the simplex algorithm.Only performing warm start on the primal problem will result in significant dual infeasibility, and the simplex algorithm needs to be adjusted on the dual problem. Only using solution values for warm start simplex algorithm requires calculation to verify the optimal solution.
The code is as follows:
GRBEnv env;
GRBModel modelSP19(env,"/home/daoio02/cg/sp19Int/supportcase19.mps");
GRBModel model = modelSP19.relax();
GRBModel modelRelax = modelSP19.relax();
modelRelax.optimize();
std::vector<GRBVar> vars;
for (int i = 0; i < model.get(GRB_IntAttr_NumVars); i++) {
vars.push_back(model.getVar(i));
vars.back().set(GRB_DoubleAttr_PStart, modelRelax.getVar(i).get(GRB_DoubleAttr_X));
vars.back().set(GRB_IntAttr_VBasis, modelRelax.getVar(i).get(GRB_IntAttr_VBasis));
}
std::vector<GRBConstr> conss;
for (int i = 0; i < model.get(GRB_IntAttr_NumConstrs); i++) {
conss.push_back(model.getConstr(i));
conss.back().set(GRB_DoubleAttr_DStart, modelRelax.getConstr(i).get(GRB_DoubleAttr_Pi));
conss.back().set(GRB_IntAttr_CBasis, modelRelax.getConstr(i).get(GRB_IntAttr_CBasis));
}
model.set(GRB_IntParam_Method, 0);
model.optimize();
The output is as follows:Read MPS format model from file /home/daoio02/cg/sp19Int/supportcase19.mps
Reading time = 1.39 seconds
supportcase19: 10713 rows, 1429098 columns, 4287094 nonzeros
Gurobi Optimizer version 11.0.0 build v11.0.0rc2 (linux64 - "Ubuntu 22.04.4 LTS")
CPU model: Intel(R) Xeon(R) Gold 6248R CPU @ 3.00GHz, instruction set [SSE2|AVX|AVX2|AVX512]
Thread count: 48 physical cores, 96 logical processors, using up to 32 threads
Optimize a model with 10713 rows, 1429098 columns and 4287094 nonzeros
Model fingerprint: 0x23ec2ddf
Coefficient statistics:
Matrix range [1e+00, 1e+00]
Objective range [3e+00, 2e+05]
Bounds range [1e+00, 3e+00]
RHS range [1e+00, 3e+00]
Presolve removed 2 rows and 98 columns
Presolve time: 2.49s
Presolved: 10711 rows, 1429000 columns, 4286997 nonzeros
Concurrent LP optimizer: primal simplex, dual simplex, and barrier
Showing barrier log only...
Ordering time: 0.16s
Barrier statistics:
AA' NZ : 2.124e+06
Factor NZ : 3.599e+06 (roughly 600 MB of memory)
Factor Ops : 1.334e+09 (less than 1 second per iteration)
Threads : 30
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 2.18365900e+11 -2.35539609e+11 5.42e+01 0.00e+00 7.44e+05 4s
1 3.29078219e+10 -1.77686295e+11 8.17e+00 3.07e+04 1.52e+05 4s
2 2.19982855e+10 -1.36665082e+11 5.46e+00 6.39e-08 1.03e+05 5s
3 1.04358649e+10 -9.66573182e+10 2.59e+00 1.09e+04 5.78e+04 5s
4 4.33515120e+09 -4.68458529e+10 1.07e+00 4.88e+03 2.53e+04 5s
5 2.69574782e+09 -2.62594627e+10 6.67e-01 7.16e+02 1.46e+04 6s
6 1.38071060e+09 -1.23984108e+10 3.40e-01 1.33e+02 7.03e+03 6s
7 8.90276191e+08 -7.15979373e+09 2.18e-01 2.07e+01 4.22e+03 6s
8 4.79468521e+08 -2.17583561e+09 1.16e-01 4.52e-08 1.67e+03 7s
9 1.22263424e+08 -5.49935905e+08 2.70e-02 5.81e-08 4.03e+02 7s
10 1.57803058e+07 -2.32128923e+08 5.24e-04 1.04e+01 8.97e+01 8s
11 1.36509650e+07 -1.75600152e+07 6.40e-11 1.92e-01 1.09e+01 8s
12 1.35512826e+07 -2.21402142e+06 3.69e-11 3.11e-08 5.52e+00 8s
13 1.35247495e+07 -9.24408892e+05 2.96e-11 2.86e-08 5.05e+00 9s
14 1.34567906e+07 5.10622088e+06 3.15e-11 1.44e-08 2.92e+00 9s
15 1.32778125e+07 1.07025112e+07 3.10e-11 4.56e-09 9.01e-01 9s
16 1.32379369e+07 1.20448861e+07 2.98e-11 1.99e-09 4.17e-01 9s
17 1.29085125e+07 1.24411520e+07 5.82e-11 1.70e-09 1.64e-01 10s
18 1.27594369e+07 1.25891585e+07 4.86e-11 1.55e-09 5.96e-02 10s
19 1.27039964e+07 1.26550557e+07 4.98e-11 1.72e-09 1.71e-02 11s
20 1.26923992e+07 1.26664416e+07 2.87e-11 1.83e-09 9.08e-03 11s
21 1.26790192e+07 1.26733056e+07 7.17e-11 1.56e-09 2.00e-03 11s
22 1.26778440e+07 1.26759482e+07 8.74e-11 1.65e-09 6.63e-04 12s
23 1.26773432e+07 1.26767129e+07 9.89e-11 1.76e-09 2.20e-04 12s
24 1.26772554e+07 1.26770259e+07 8.21e-11 1.51e-09 8.03e-05 12s
25 1.26772219e+07 1.26771413e+07 7.33e-11 1.58e-09 2.82e-05 13s
26 1.26772115e+07 1.26771903e+07 7.57e-11 1.56e-09 7.41e-06 13s
27 1.26772069e+07 1.26772030e+07 5.03e-12 1.58e-09 1.36e-06 13s
28 1.26772061e+07 1.26772059e+07 3.01e-11 1.36e-09 5.57e-08 14s
29 1.26772060e+07 1.26772060e+07 4.70e-11 1.49e-09 2.70e-10 14s
Barrier solved model in 29 iterations and 14.00 seconds (9.63 work units)
Optimal objective 1.26772060e+07
Crossover log...
6078 DPushes remaining with DInf 0.0000000e+00 14s
112 DPushes remaining with DInf 0.0000000e+00 16s
0 DPushes remaining with DInf 0.0000000e+00 18s
4055 PPushes remaining with PInf 9.4439797e-04 18s
0 PPushes remaining with PInf 0.0000000e+00 19s
Push phase complete: Pinf 0.0000000e+00, Dinf 9.3164272e-07 19s
Iteration Objective Primal Inf. Dual Inf. Time
10136 1.2677206e+07 0.000000e+00 3.104084e-06 19s
Solved with barrier
10140 1.2677206e+07 0.000000e+00 0.000000e+00 19s
Solved in 10140 iterations and 19.13 seconds (12.30 work units)
Optimal objective 1.267720600e+07
Set parameter Method to value 0
Gurobi Optimizer version 11.0.0 build v11.0.0rc2 (linux64 - "Ubuntu 22.04.4 LTS")
CPU model: Intel(R) Xeon(R) Gold 6248R CPU @ 3.00GHz, instruction set [SSE2|AVX|AVX2|AVX512]
Thread count: 48 physical cores, 96 logical processors, using up to 32 threads
Optimize a model with 10713 rows, 1429098 columns and 4287094 nonzeros
Coefficient statistics:
Matrix range [1e+00, 1e+00]
Objective range [3e+00, 2e+05]
Bounds range [1e+00, 3e+00]
RHS range [1e+00, 3e+00]
LP warm-start: discard start vectors, use basis
Iteration Objective Primal Inf. Dual Inf. Time
0 1.2677206e+07 0.000000e+00 0.000000e+00 0s
Solved in 0 iterations and 0.25 seconds (0.11 work units)
Optimal objective 1.267720600e+070
Please sign in to leave a comment.
Comments
8 comments