2
$\begingroup$

I read in several sources that the use of Gomory's cuts exclusively in Integer Programming was shown to be inefficient in practice when Gomory had created them. But later down the line they were shown to quite effective for certain problems (especially when paired with another hueristic such as branch and bound).

Is there any literature out there that gives strong upper and lower bounds on the performance of the Cutting Plane Algorithm?

Wiki references, didn't lead to anything and I dug around a bit more but still couldn't find an answer. I think if I have Gomory's original paper, where he proves the algorithm must converge in a finite number of steps, that would naturally lead to a start for an upper bound on runtime

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ I know of specific cases where cutting plane algorithms run in polynomial time (notably for perfect matching). For general problems, here and here might be good places to start. $\endgroup$
    – Austin Buchanan
    Aug 7, 2015 at 23:08

0

Reset to default

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.