Gomory-Chvátal Cut and Closure

Question

We're having the following definitions and example in our lecture.

I'm getting a bit confused. What is the first Chvátal closure of $P$ in this picture (please be specific)? Why is it not necessarily the integer polyhedron $P_I$, even though we've taken all possible values of $y$?

(Please skip to edit 2)

=====
Edit: using the multiplier $y^T = [\frac{7}{34} \ \frac{2}{34}]$, I manage to get the GC cut $-x_1 + 2x_2 \leq 7$, which is similar, but not quite, the red segment joining $(2,4)$ and $(4,5)$, i.e. $-x_1 + 2x_2 \leq 6$. Have I missed a step, or does that line segment simply cannot be derived as a GC cut from the original inequalities $(1),(2)$ (and hence not part of the first closure)?

I'm having trouble understand the definition because, while it is a clear specification, there can potentially be many values of $y$ that qualify, so I can't picture which GC cuts can be generated for the first closure and which cannot.

=====
Edit 2: I've managed to decode the slide a bit more. There's one typo at the line $-6x_1 + 8x_2 \leq 10$. It should be $-6x_1 + 8x_2 \leq 20$.

Also please disregard the multiplier I found in edit 1. It's wrong, as pointed out by Siong Thye Goh below. (Thanks)

Regardless, I try to follow the procedure and find multipliers, and realize to get to (7) it's a two-step process:

• First apply the multiplier $[\frac{1}{2} \ 0]$ to $\begin{bmatrix} -6 & 8 \\ 2 & 3 \\ \end{bmatrix}$ $\begin{bmatrix} x_1 \\ x_2 \\ \end{bmatrix}$ and $\begin{bmatrix} 21 \\ 27 \\ \end{bmatrix}$ to get (5): $-3x_1 + 4x_2 \leq \lfloor 10.5 \rfloor = 10$.
• Add this new inequality to the original two, and use the multiplier $[0 \ 3 \ 2]$ on the new system, i.e. on $\begin{bmatrix} -6 & 8 \\ 2 & 3 \\ -3 & 4 \end{bmatrix}$ $\begin{bmatrix} x_1 \\ x_2 \\ \end{bmatrix}$ and $\begin{bmatrix} 21 \\ 27 \\ 10 \end{bmatrix}$, to get (7): $x_2 \leq \lfloor \frac{101}{17} \rfloor = 5$. (Technically the third lines of the matrices can replace the first ones, as the example seems to have done, but I want to follow the procedure and not using shortcuts that can muddle it. Anyway the multiplier $0$ makes sure that the redundant inequality will be crossed out).

This analysis makes it clear what happens in the example, but it still doesn't answer my questions about which specific inequalities make up the first Chvátal closure and how I know that I've got there, since there are so many multipliers that could qualify. The only insight/conjecture I got is that (7) does not belong to the first closure, since it cannot be derived directly from the first two inequalities. But I'm not sure about this conclusion.

Answer 1

Let's examine if your choice of $y$ satisfies the condition stated:

$y \ge 0$ but $y^TA=(-\frac{38}{34}, \frac{62}{34}) \notin \mathbb{Z}^2$, hence the $y$ does not satisfies the condition.

---

$$-6y_1 + 2y_2=k_1 \in \mathbb{Z}$$

$$8y_1+3y_2=k_2 \in \mathbb{Z}$$

Then we have $$\begin{bmatrix} y_1 \\ y_2 \end{bmatrix}=\frac1{-18-16}\begin{bmatrix} 3 & -2 \\ -8 & -6\end{bmatrix}\begin{bmatrix} k_1 \\ k_2\end{bmatrix}=-\frac1{34}\begin{bmatrix} 3k_1-2k_2 \\ -8k_1-6k_2 \end{bmatrix}$$

We want $$34y_1=-3k_1 +2k_2 \ge 0\tag{1}$$

and $$34y_2=8k_1+6k_2 \ge 0\tag{2}$$

Multiply $(1)$ by $8$ and add to $3$ times of $(2)$ show that $k_2 \ge 0$.

$$\frac{-3}{4}k_2 \le k_1 \le \frac{2}{3}k_2$$

We want to find $x_1, x_2$ such that for all $k_2 \ge 0, \frac{-3}{4}k_2 \le k_1 \le \frac{2}{3}k_2 $, the following holds:

\begin{align}k_1x_1+k_2x_2 &\le \lfloor21y_1+27y_2\rfloor \\&= \lfloor\frac{21(-3k_1+2k_2)+27(8k_1+6k_2)}{34}\rfloor \\&=\lfloor \frac{153k_1+204k_2}{34}\rfloor \\ &= \lfloor4.5k_1 +6k_2 \rfloor \\ &= 4.5k_1+6k_2 - 0.5\mathbb{1}_{k_1 \text{ is odd}}\end{align}

Notice that when $k_2=0$, then we must have $k_1=0$ and every $x \in \mathbb{R}^2$ satisfies, hence it is not interesting.

We will assume that $k_2 >0$ from now on. Under this setting, we can rewrite the inequality as

$$\frac{k_1}{k_2}x_1 +x_2 \le \frac92 \frac{k_1}{k_2}+6 - \frac{\mathbb{1}_{k_1 \text{ is odd}}}{2k_2} \tag{3}$$

For simplicity, I will denote $m=\frac{k_1}{k_2}$ and we want $$-\frac34 \le m \le \frac23$$

Example of valid cut is when $k_1=-3, k_2=4$, we obtained the cut:

$$-3x_1+4x_2 \le 10$$

which can be rewritten as

$$-\frac34 x_1 + x_2 \le \frac52\tag{4}$$

Another valid cut is when $k_1=2, k_2=3$, we obtain the following cut:

$$2x_1+3x_2 \le 27$$

which can be rewritten as

$$\frac23 x_1 + x_2 \le 9\tag{5}$$

Let's consider the implication of $(4)$ and $(5)$.

Suppose $\alpha \in [0,1]$ and $m = \alpha \left( -\frac34\right)+(1-\alpha)\left( \frac23 \right) \iff \alpha = \frac8{17}-\frac{12}{17}m$, then $(4)$ and $(5)$ would imply that

\begin{align}mx_1 + x_2 &\le \frac52 \alpha + (1-\alpha)9\\&=9-\frac{13}2\alpha \\ &=9 - \frac{13}2 \left(\frac{8}{17} - \frac{12}{17}m \right)\\ &= \frac{101}{17} + \frac{78}{17}m\end{align}

Compare with the inequality in $(3)$, we investigate when does

$$\frac{101}{17} + \frac{78}{17}m\ \le \frac92 m+6 - \frac{\mathbb{1}_{k_1 \text{ is odd}}}{2k_2} $$

which can be simplifed to

$$\frac{101}{17} + \frac{78}{17}m\ \le \frac92 m+6 - \frac{\mathbb{1}_{k_1 \text{ is odd}}}{2k_2} $$

$$\frac3{34}m \le \frac1{17}- \frac{\mathbb{1}_{k_1 \text{ is odd}}}{2k_2}$$

$$m \le \frac23- \frac{17\mathbb{1}_{k_1 \text{ is odd}}}{3k_2}$$

Hence when $k_1$ is even, the inequalities hold for sure. Hence we do not need to add any more cuts with $k_1$ being even. Any additional non-redundant cut must be due to $k_1$ being odd.

Let's explore a few values of $k_2$ and see the possible values of odd $k_1$'s from $-\frac34 k_2 \le k_1 \le \frac23 k_2$.

If $k_2=1$, there is no feasible $k_1$ odd value.

If $k_2=2$, then we have odd $k_1 \in \{-1,1\}$.

The corresponding cuts are

$$-\frac12 x_1 + x_2 \le \frac72 \tag{6}$$ $$\frac12 x_1 + x_2 \le 8 \tag{7}$$

An implication is $x_2 \le \frac{23}4$.

If $k_2=3$, $k_1 \in \{-1,1\}$, I claim that we do not need to include them explicitly into the set once we have the $4$ cuts that I stated earlier. Furthermore, we do not need to include any more additional cuts.

We will consider $3$ cases:

• $m \in \left[ -\frac34, -\frac12\right]$, in this case, we write $\alpha \in [0,1]$, $m= -\frac34 \alpha - \frac12 (1-\alpha)=-\frac12 -\frac14\alpha \iff \alpha = -4m-2$. Now, from equation $(4)$ and equation $(6)$, we have \begin{align}mx_1 + x_2 &\le \frac52 \alpha + \frac72 (1-\alpha) \\ &= \frac72 -\alpha \\ &=\frac72 -(-4m-2)\\&= 4m +\frac{11}2\end{align}

Compare with the inequality in $(3)$, we investigate when does the following hold for sure:

$$4m +\frac{11}2 \le \frac92m + 6 - \frac{1}{2k_2}$$ $$-1 \le m - \frac{1}{k_2}$$ $$\frac1{k_2} \le m+1 $$

which is true when $k_2 \ge 4$. For the cases when $k_2 < 4$, we have examine it manually.

---

• $m \in \left[ -\frac12, -\frac12\right]$, in this case, we write $\alpha \in [0,1]$, $m= -\frac12 \alpha + \frac12 (1-\alpha)=\frac12 -\alpha \iff \alpha = -m+\frac12$. Now, from equation $(6)$ and equation $(7)$, we have \begin{align}mx_1 + x_2 &\le \frac72 \alpha + 8 (1-\alpha) \\ &= 8 -\frac92\alpha \\ &=8 -\frac92(-m + \frac12)\\&= \frac{9m}2 +\frac{23}4\end{align}

Compare with the inequality in $(3)$, we investigate when does the following hold for sure:

$$\frac{9m}2 +\frac{23}4 \le \frac92m + 6 - \frac{1}{2k_2}$$ $$23 \le 24 - \frac{2}{k_2}$$ $$\frac2{k_2} \le 1 \iff k_2 \ge 2 $$

which is true when $k_2 \ge 2$ within this range. For the cases when $k_2 < 2$, we have examine it manually.

---

• $m \in \left[ \frac12, \frac23\right]$, in this case, we write $\alpha \in [0,1]$, $m= \frac12 \alpha + \frac23 (1-\alpha)=\frac23 -\frac16\alpha \iff \alpha = 4-6m$. Now, from equation $(7)$ and equation $(5)$, we have \begin{align}mx_1 + x_2 &\le 8 \alpha + 9 (1-\alpha) \\ &= 9 -\alpha \\ &=9 -(4-6m )\\&= 5+6m\end{align}

Compare with the inequality in $(3)$, we investigate when does the following hold for sure:

$$5+6m \le \frac92m + 6 - \frac{1}{2k_2}$$ $$\frac32m \le 1 - \frac{1}{2k_2}$$ $$3k_1 \le 2k_2-1 $$

$$3k_1 + 1 \le 2k_2 $$

Recall that we know that $k_1$ is odd,

Hence it is equivalent to $$3k_1 \le 2k_2$$

which is just $$m \le \frac23$$

which is true for our condition. Hence, only $(4), (5), (6), (7)$ are needed.