# Understanding cutting plane proofs

I am trying to understand the following definition:

Def: A cutting plane proof from the system $Ax\leq b$ for an inequality $c^Tx\leq d$ is a sequence of inequalities $c_i^T\leq d_i$, $(i = 1,\ldots, k)$ with the following properties

i) every $c_i$ is integral,

ii) $c_k = c$ and $d_k = d$,

iii) for every $i$ there is a number $d_i'$ satisfying $\lfloor d_i'\rfloor \leq d_i$, such that $c_i^T x\leq d_i'$ is a nonnegative combination of the inequalities $Ax\leq b$ and $c_1^Tx\leq d_1,\ldots, c_{i-1}^Tx\leq d_{i-1}$.

Question: Could someone explain to me how the number $k$ is specified, and give an example of a cutting plane proof? I have tried to find examples that match this definition, but I haven't found any.

Suppose $Ax\le b$ is the following system: $$(1): -x_1-3x_2\le -3\\ (2): 8x_1+3x_2\le 24\\ (3): -2x_1+x_2\le 1$$ The solution set is represented by the following graph: Suppose we want to derive $c^Tx\le b$ where $c^T=(0,1),b=3$, i.e., $x_2\le 3$ from $Ax\le b$.
From the picture, the problematic point is the intersection of (2) and (3). So we proceed as follows. First we obtain $c_1^Tx\le d_1$ by performing: $$\frac{1}{2}\cdot((2)+(3)): 3x_1+2x_2\le 12.5.$$ Note that this is a nonnegative combination of the inequalities in $Ax\le b$. Now we set $d_1'=12$ which is the floor of $d_1=12.5$. This is $c_1^Tx\le d_1'$. We name it (4). Next we obtain $c_2^Tx\le d_2$ by performing: $$\frac{1}{7}(3\cdot (3)+2\cdot(4)): x_2\le \frac{27}{7}.$$ Note that this is again a nonnegative combination of the inequalities in $Ax\le b$ and $c_1^Tx\le d_1'$. Making $d_2'=\lfloor d_2\rfloor=3$ gives the desired result. So $k=2$ and $c_2^Tx\le d_2'$ is exactly $c^Tx\le d$.
• Thanks for you reply! I have a final question left. Why don't you just do: $\frac{1}{7}((2) + 4\cdot (3)): x_2 \leq 4$. If $x_2\leq 4$ then surely $x_2\leq 3$, right? – titusAdam Jan 20 '18 at 13:07
• @titusAdam: No, if $x_2=4$, then it is $\le 4$, but not $\le 3$. :) Remember the key point here is to throw away that point where $x_2=4$ since it is not an integral point. – KittyL Jan 21 '18 at 0:20