Crossover LP symmetric solution
回答済み
Hi,
I am trying to investigate the long runtime of crossover in a model I am working with, and I was wondering what is exactly happening in the crossover part. Regarding the logs below I have three questions:
- What is meant with LP symmetric solution?
- Why does crossover run twice after having found an optimal solution (no primal and dual infeasibilities) in the first part?
- What is the difference between the solutions of both parts of crossover (or can I output the solution after the first part)?
Logs (these are on a smaller version of the problem but still show a very large fraction of time spent in crossover):
Optimize a model with 213362 rows, 287389 columns and 934189 nonzeros
Model fingerprint: 0x2cf8aaef
Coefficient statistics:
Matrix range [1e-04, 7e+04]
Objective range [1e+00, 1e+00]
Bounds range [1e+02, 8e+03]
RHS range [4e+03, 4e+03]
Presolve removed 2 rows and 2 columns
Presolve time: 0.59s
Presolved: 213360 rows, 287387 columns, 720720 nonzeros
Ordering time: 0.00s
Barrier statistics:
AA' NZ : 1.600e+01
Factor NZ : 3.600e+01
Factor Ops : 2.040e+02 (less than 1 second per iteration)
Threads : 1
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 9.88879150e+06 6.40963732e+06 3.39e+03 2.27e-13 3.36e+02 1s
1 6.41344000e+06 6.41177308e+06 4.55e-13 1.03e-13 4.17e+01 1s
2 6.41344000e+06 6.41343833e+06 4.55e-13 7.50e-14 4.17e-02 1s
3 6.41344000e+06 6.41344000e+06 6.82e-13 1.02e-13 4.17e-05 1s
4 6.41344000e+06 6.41344000e+06 9.09e-13 7.78e-14 4.17e-08 1s
5 6.41344000e+06 6.41344000e+06 4.55e-13 5.65e-17 4.17e-14 1s
Barrier solved model in 5 iterations and 0.83 seconds (0.46 work units)
Optimal objective 6.41344000e+06
Crossover log...
1 DPushes remaining with DInf 0.0000000e+00 1s
17 PPushes remaining with PInf 0.0000000e+00 1s
0 PPushes remaining with PInf 0.0000000e+00 1s
Push phase complete: Pinf 0.0000000e+00, Dinf 0.0000000e+00 1s
Iteration Objective Primal Inf. Dual Inf. Time
20 6.4134400e+06 0.000000e+00 0.000000e+00 1s
Use crossover to convert LP symmetric solution to basic solution...
Crossover log...
129578 DPushes remaining with DInf 0.0000000e+00 5s
70808 DPushes remaining with DInf 0.0000000e+00 10s
49792 DPushes remaining with DInf 0.0000000e+00 15s
24864 DPushes remaining with DInf 0.0000000e+00 20s
8353 DPushes remaining with DInf 0.0000000e+00 25s
0 DPushes remaining with DInf 0.0000000e+00 28s
5055 PPushes remaining with PInf 0.0000000e+00 28s
0 PPushes remaining with PInf 0.0000000e+00 28s
Push phase complete: Pinf 0.0000000e+00, Dinf 2.1353757e-09 28s
Iteration Objective Primal Inf. Dual Inf. Time
130746 6.4134400e+06 0.000000e+00 0.000000e+00 28s
Solved in 130746 iterations and 28.09 seconds (64.82 work units)
Optimal objective 6.413440000e+06
User-callback calls 155281, time in user-callback 0.06 sec
-
正式なコメント
-
Gurobi Staff
This post is more than two years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support. -
-
-
Hi Matthijs,
The barrier algorithm itself rarely ends up with a basic solution (in a corner of the polytope). The first crossover phase (basically simplex) tries to accomplish this, i.e., move the solution towards a corner.
If symmetry is detected in the model in the presolving phase, the model is first converted to a usually much smaller model avoiding symmetry. But after a solution has been found to the converted model, the solution needs to be unfolded to the original model space. To do that, a few further simplex iterations are needed in this second crossover phase.
If you are happy with a non-basic solution, you can switch off the first crossover phase via the parameter Crossover=0.
In some cases, the second crossover phase can be avoided by deactivating symmetry via parameter Symmetry=0, potentially decreasing performance.
Best regards,
Mario1 -
投稿コメントは受け付けていません。
コメント
2件のコメント