4
$\begingroup$

To derive problem-specific cutting planes for some given problem (think something like TSP problem), one common way is to study small examples. To this end, one can create small instances for the polytope and feed them to tools like https://polymake.org/doku.php or https://porta.zib.de, and they return the "perfect" linear description. Then one can try to generalize the found inequalities to yield general cutting planes for our problem.

How do you investigate if the structures become non-polyhedral? How to derive linear cutting planes for the convex hull of the feasible set?

Consider for example something like $S = \{x,y,z : xy + yz = 5, x \le 3, y \ge5\}$ and one wants to find linear cutting planes to come as close as possible to $\operatorname{conv}(S)$.

Improve this question
$\endgroup$
1
  • $\begingroup$ The outer approximation is typically used to solve problems with polynomial constraints, which btw tries to compute the convex hull of a non-convex feasible set by inserting cutting planes. A helpful resource for you may be to look at papers using the outer approximation algorithm to get a sense of the techniques people have developed for generating the cutting planes. $\endgroup$
    – batwing
    Commented Mar 17, 2021 at 23:25

0

Reset to default