Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
Suppose I want to minimize a linear function $f$ over a convex set $K$ and I have only access to a separation oracle, that is, given a point, the oracle returns yes if the point is in $K$ and otherwise returns a hyperplane separating the point from the set. How can I use this to minimize $f$ in polynomial time?
I have read about cutting plane methods that return a point in the set unless the volume if the set is very small. But I don't see how it will help to get the minimizer of $f$.
The cutting plane algorithm is often used when one would like to derive the integer solution from the linear relaxation of the original space. (I assumed the original problem is an LP). The cutting plane method for solving MIPs can be viewed as an extension of the dual simplex method in which the separation procedure (for searching violated inequalities) is not limited to verifying the constraints of the current formulation, but can also generate new cuts.
Now, suppose there is a linear minimization (or maximization) problem that the solution space $\in \mathbb{R}^+$. By using the cutting plan algorithm one can invoke the integer solution set from the original solution space that $\in \mathbb{Z}^+$.
Some of its variants are, for example, Chvatal-Gomory or Mixed-integer rounding cut. It is known that this separation problem is NP-hard. But, on the other hand, there are a number of important special cases when it is solved efficiently. For more details please, check the separation procedure for C-G cuts.
