Crossover LP symmetric solution
AnsweredHi,
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
-
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,
Mario0
Please sign in to leave a comment.
Comments
1 comment