The role of crossover in linear programming

Answered

Comments

2 comments

  • 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 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
    Comment actions Permalink
  • Tim Tröndle

    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
    Comment actions Permalink

Please sign in to leave a comment.

Powered by Zendesk