In a cutting plane algorithm for integer linear programming problems you would usually use an LP solver to get an extreme point of the polyhedron corresponding to the LP relaxation. Let's call that solution $x^1$. Then you would use some kind of oracle that would tell you that $x^1$ is in the convex hull of integer solutions or produce a cutting plane $\pi x\leq\pi_0$ with $\pi x^1>\pi_0$.

I was wondering what could be done if one has two LP solutions at hand? Say $x^1$ and $x^2$, with $x^1\neq x^2$. An obvious starting point is to separate a convex combination of the two points, $x_\lambda=\lambda x^1+(1-\lambda)x^2$. If $x_\lambda$ can be separated, at least one of the two original points will be separated by the same hyperplane. But can more be done? Has research been done on separating more than one point at a time using a single inequality?

  • $\begingroup$ I am not sure, but an LP with multiple optimal solutions might be the case. $\endgroup$
    – A.Omidi
    Aug 20, 2022 at 12:20
  • $\begingroup$ @A.Omidi That's one example, yes. But one could also pertube the objective function slightly and get another LP solution close to an optimal face. $\endgroup$
    – Sune
    Aug 20, 2022 at 14:05


Your Answer

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