2
$\begingroup$

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.

Thanks in advance!

$\endgroup$
1
$\begingroup$

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:

enter image description here

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$.

P.S. I think there are some typos in your definition.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – titusAdam Jan 20 '18 at 13:07
  • $\begingroup$ @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. $\endgroup$ – KittyL Jan 21 '18 at 0:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.