Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
It is known for knapsack type constraint $\sum_{i \in N} a_i x_i \leq b , x \in \{0,1\}$, we can generate the so called cover cuts that have the sum of coefficient in a set C greater than b. The cover cuts are $\sum_{j \in C} x_j \leq |C| - 1, ~\forall~ C \subseteq N$.
Is it possible to generate the similar kind of cuts if x is integer, $x \in \mathbb{Z}^{+}$.? Or there a way to generate other kind of valid inequalities from this constraint?
Consider the integer knapsack set as:
$$ K_{I} = \{ x \in Z^{N}_{+} : ax \leq b, x \leq u\} $$
Let $C \subseteq N$ be a cover if $\lambda = \sum_{i \in C} u_ia_i − b \gt 0$ and consider the restriction $K_I (N \text{\\} C, \varnothing)$ obtained by fixing all $x_i, i \in N \text{\\} C$ to zero. Extending the combinatorial argument on covers for the $0$-$1$ knapsack set, since not all variables $x_i, i \in C$ can be at their upper bound simultaneously, inequality:
$$ \sum_{i \in C} x_i \leq u(C)-1 \quad (1)$$
is valid for $K_I (N \text{\\} C, \varnothing)$. Another way to write the above inequality is:
$$ \sum_{i \in C} (u_{i} - x_{i}) \geq 1 \quad (2)$$
which states that at least one $x_{i}$ must be less than its upper bound. However, observe that if $a_i \lt \lambda$ for all $i \in C$ the left-hand side of (2) is greater than $1$ for all feasible solutions. This suggests the strengthening:
$$ \sum_{i \in C} (u_{i} - x_{i}) \geq \lceil \lambda/ \bar{a} \rceil $$
where $\bar{a} = \text{max}_{i \in C} a_{i}$. Suppose the integer knapsack is given as:
$$ K_{I}=\{ x \in \text{Z}^2: 5x_{1} + 9x_{2} \leq 45, x_{1} \leq 6, x_{2} \leq 4\}$$
Let $C = \{1,2\}$ be an integer cover with $\lambda = 30 + 36 − 45 = 21$. The following inequality:
$$ (6-x_{1}) + (4-x_{2}) \geq 1 $$
does not support $K_{I}$ . However, the strengthened inequality:
$$ (6-x_{1}) + (4-x_{2}) \geq \lceil 21/9 \rceil $$
defines a facet of $K_{I}$ for this example. For more details please, see the following paper.
Also, it seems the mentioned integer knapsack set can be supposed as a capacity constraint in the planning models that other valid inequalities like Gomory cuts, MIR cuts, etc. can be applied on.
Atamtürk, A. Cover and Pack Inequalities for (Mixed) Integer Programming. Ann Oper Res 139, 21–38 (2005). https://doi.org/10.1007/s10479-005-3442-1
Sure. Another way of doing this is by extending the number of items. Suffices to create $\lfloor \frac{b}{a_i} \rfloor$ dummy items to each item $i \in N$. Thus, we would have the new items set $N^{'} = \bigcup_{i \in N} N_i$, where $N_i = \{ i_k : k \in \mathbb{N}^{*}_{\leqslant \lfloor \frac{b}{a_i} \rfloor} \}$ is the set of dummies items of item $i \in N$. Resulting in the following formulation.
Max $\sum_{i \in N^{'}} p_i x_i$
s.t.
$\sum_{i \in N^{'}} a_i x_i \leqslant b$
$x \in \mathbb{B}^{|N^{'}|}$
With the following cover cuts.
$\sum_{i \in C} x_i \leqslant |C| - 1 \quad\quad \forall C \subseteq N^{'} : \sum_{i \in C} a_i > b$
