For a polyhedron $P$ associated with an LP, find a polyhedral description of the integer polyhedron $P_{IP}$ using Gomory-Chvátal cuts.

Question

Consider the polyhedron $P=\left\{\left(x_{1}, x_{2}\right) \in \mathbb{R}_{+}^{2}: x_{1}+4 x_{2} \leq 8, x_{1}+x_{2} \leq 4\right\} .$ Find a polyhedral description of $P_{I P}$ using GC-cuts. What is the Chvátal-rank of $P_{I}$ (w.r.t. $P) ?$

I've found several valid cuts for this problem, such as $x_1+2x_2 \leq 5$, using some random GC multipliers. But I don't know how to approach this task in a systematic way.

Answer 1

Because this is two dimensions, a good place to start is to plot the feasible region, enumerate the integer feasible solutions, and determine which of these define the integer hull. Then you can see which cuts are needed.