3

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?

JKHA
  • 679
  • 4
  • 10
  • 2
    Check here: https://or.stackexchange.com/questions/1278/how-does-a-warm-start-work-in-lp-mip/1326#1326, https://www.ibm.com/docs/en/icos/22.1.0?topic=mip-starting-from-solution-starts, https://www.ibm.com/docs/en/icos/20.1.0?topic=heuristics-relaxation-induced-neighborhood-search-rins-heuristic. – Matheus Diógenes Andrade Feb 13 '24 at 20:17

1 Answers1

3

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.

prubin
  • 39,078
  • 3
  • 37
  • 104
  • I suppose the technical names for these two uses are Relaxation induced neighborhood search (RINS) heuristic, and Feasibility Pump, respectively. – Matheus Diógenes Andrade Feb 13 '24 at 20:43
  • 2
    Those are specific examples of the two types of heuristics. I would not be surprised if there are others implemented in some solvers. – prubin Feb 13 '24 at 23:14