Skip to main content

The role of crossover in linear programming




  • Jakob Schelbert

    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 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 is sufficient?
    2. The solution computed is optimal within the given tolerances (see 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

  • Tim Tröndle
    First Comment
    First Question

    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.


Please sign in to leave a comment.