0

Is "Branch and cut" method guaranteed to obtain an optimal solution? if not, under what conditions it would be guaranteed. is there a reference that I could refer to (a paper would be great)? thanks

Sean Roberson
  • 9,110
A. Shokair
  • 35
  • It should - it's better than branch and bound if I recall correctly. – Sean Roberson Jul 07 '17 at 15:43
  • @SeanRoberson Branch and cut seems to be the specialization of branch and bound for integer programming. Cut means throwing away a part of the search tree and of the feasible set with linear inequalities, usable in the linear programming relaxation used to bound the optimal solution of a given subtree (subset of solutions). – reuns Jul 08 '17 at 00:12

1 Answers1

1

Properly implemented (meaning that it correctly detects infeasible and suboptimal nodes, and correctly partitions non-terminal nodes), given a feasible and bounded problem with a finite integer search space, and given enough time and memory, yes, branch and cut guarantees finding an optimal solution. The logic is the same as for branch and bound: the search tree has a finite number of nodes, so eventually you run out of nodes, at which point the best detected feasible solution is the winner.

prubin
  • 4,923
  • Thank you, prubin. Is there a refference paper that you can think off which states this fact? A book could do it. I need to properly reference this. Thanks. – A. Shokair Jul 08 '17 at 20:07
  • I'm afraid I can't help there. The books in my library are too old to even mention branch and cut. – prubin Jul 08 '17 at 23:50