7
$\begingroup$

Idea

Sometimes I encounter problems where Simplex spends many iterations for final convergence to the optimal objective value. Let's suppose, this happens when solving branch and bound-tree nodes as well. Could it be worthwhile to solve the dual of the node instead and limit the number of simplex iterations?

Expected results

If my thinking is correct, this could give you some useful information and increase the node throughput in pathological cases. While the non-optimal objective could be used as bound, we'd end up with lots of primal-infeasible solutions to nodes. Perhaps it's possible to completely solve only a subset?

Question

Is this idea workable or did I miss something? Do you know of research in this direction?

Improve this question
$\endgroup$
1
  • $\begingroup$ AFAIK, it depends on the structure of the mathematical problem which is solved by a specific solver. In some problem, primal simplex has better performance but, in other, dual simplex has a better result. You could check it easily by setting the solving algorithm in many solvers. $\endgroup$
    – A.Omidi
    Apr 18, 2020 at 11:56

2 Answers 2

Reset to default
6
$\begingroup$

Yes, you can solve the dual and use that as a (weaker) bound than the optimal solution of the LP. This leads to the trade off between faster processing nodes vs processing more nodes. This approach is often exemplified in the choice between Lagrangean relaxation and Dantzig Wolfe decomposition. In its pure form you need to solve the DW to optimality in order to get a valid bound (as the solution is obtained in primal space). In Lagrangean relaxation you always have a valid bound at hand and you do thus not need to solve the dual to optimality to get a valid bound. Stopping prematurely might however lead to a weak bound.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Do you know any papers showing the effects of this approach in the context of MIP BB trees? I couldn't find any literature. $\endgroup$
    – Simon
    Apr 18, 2020 at 12:46
  • $\begingroup$ DW also yields a valid dual bound even if you stop early. $\endgroup$
    – RobPratt
    Apr 18, 2020 at 14:09
  • $\begingroup$ @RobPratt yes, that's the Lagrangean bound corresponding to the duals of the restricted master, right? $\endgroup$
    – Sune
    Apr 18, 2020 at 15:00
  • $\begingroup$ @Sune, yes. For a minimization problem, the restricted master objective value plus subproblem (minimize reduced cost) lower bound provides a valid lower bound for the original problem. $\endgroup$
    – RobPratt
    Apr 18, 2020 at 15:35
6
$\begingroup$

It is common practice for MIP solvers to solve node LPs (other than at the root node) via dual simplex. I can't say with certainty that they terminate dual simplex prematurely if the objective value becomes inferior to the current incumbent, but I would think it likely.

That does not address the question of stopping dual simplex early when the bound is weaker than the incumbent. If the node LPs are chewy, an alternative is to use some other algorithm (perhaps interior point) at nodes. Stopping dual simplex early not only would leave nodes lying around that could be pruned, but since you would be stopping with a primal-infeasible solution, it would leave unanswered the question of how the solver would make branching decisions at those nodes.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you for the answer! Answers to the open questions you mentioned (like branching decisions) are exactly what I'm interested in. $\endgroup$
    – Simon
    Apr 20, 2020 at 7:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.