For my large and sparse LPs (1e6 rows/columns, 1e7 non zeros) crossover takes the largest fraction of the solve time: usually above 75%, sometimes more than 90% of the time. So I am wondering if this can be shortened.
However, I am not sure what crossover does exactly. So my first question is:
(1) Is there any documentation or any literature on crossover?
What I assume it does is the following: it improves the solution of barrier, whose solution is only close to the optimal one. Barrier finds a nearly optimal solution within the polyhedron, while the successive phase 1 and 2 of crossover (try to) push the solution to a vertex of the polyhedron, and phase 3 walks from this vertex to the “optimal” vertex. Considering this is correct, my follow-up questions are:
(2) Being an internal solution, is the barrier result before crossover generally feasible, but not optimal? Is it correct to say the found solution is less than `BarConvTol` larger than the optimum?
(3) Can it generally be said that the solution after crossover phase 1 and 2 is closer to the optimum than the result of barrier, but not necessarily feasible anymore?
Please sign in to leave a comment.