The role of crossover in linear programming

Answered

Tim Tröndle

• April 30, 2019 15:11

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?

0

• 

  Jakob Schelbert

  • May 02, 2019 14:46

  

  

  Hi Tim,

  you could try using the simplex which always stays at a vertex of the polyhedron, but looking at your problem size barrier is probably faster (you can play around with the Method parameter, see http://www.gurobi.com/documentation/8.1/refman/method.html). In contrast to the simplex algorithm(s - primal & dual variant), barrier starts from within the polyhedron and follows the central path to the optimal solution. This must not necessarily be a vertex but could also be a facet of the polyhedron, so essentially any point on that facet. The crossover step ensures that the solution is a vertex. Note that the value of the objective function does not change for all points on the optimal facet. Crossover is necessary if you want to use the solution in a branch-and-bound procedure that usually uses the dual simplex to solve problems at each node of the bnb-tree.

  To your questions:

  1. Maybe http://www.gurobi.com/documentation/8.1/refman/crossover.html#parameter:Crossover is sufficient?
  2. The solution computed is optimal within the given tolerances (see http://www.gurobi.com/documentation/8.1/refman/barconvtol.html). Note that the barrier internally works with the dual and the primal version of your model and computed both objective values. If the two values are within the given tolerance, the algorithm terminates.
  3. No, as stated above, crossover does not change the objective value of the point given to you. I only ensures that the solution is a vertex.

  Maybe also this is helpful https://stackoverflow.com/questions/38052754/drawbacks-of-avoiding-crossover-after-barrier-solve-in-linear-program

  1
• 

  Tim Tröndle

  • May 03, 2019 17:59
  • Edited

  

  

  

  Thank you Jakob. From what you say I understand that I need crossover only if I want to make sure the result is a vertex of the polyhedron. For what I do, that shouldn't be important and thus I'll switch it off and save the computation time.

  0

Please sign in to leave a comment.