3
$\begingroup$

From what I understand, most solvers use a user provided solution by first detecting if it feasible.

If it is feasible, its objective value is used as a first bound for the branch and cut tree, this bound will be used to prune nodes.

I would like to know if the (commercial) solvers use this heuristic provided solution for other means? For instance, does it use the solution to help choosing a branching strategy? Is it not used at all appart from its objective value if feasible?

$\endgroup$
1

1 Answer 1

3
$\begingroup$

Besides getting the initial primal bound provided by the (feasible) starting solution, one possible use for a warm start is to seed a heuristic that looks for an even better feasible solution.

Given a warm start that is not feasible, some solvers will attempt to improve the starting solution to get a feasible incumbent.

$\endgroup$
2
  • $\begingroup$ I suppose the technical names for these two uses are Relaxation induced neighborhood search (RINS) heuristic, and Feasibility Pump, respectively. $\endgroup$ Commented Feb 13 at 20:43
  • 2
    $\begingroup$ Those are specific examples of the two types of heuristics. I would not be surprised if there are others implemented in some solvers. $\endgroup$
    – prubin
    Commented Feb 13 at 23:14

Your Answer

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

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