Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

In this chapter, we briefly review an alternative application of dual-feasible functions in general integer programming. We explore these functions in particular to derive valid inequalities for integer programs. Since the notion of superadditivity is essential for this purpose, we start by reviewing superadditivity in the scope of valid inequalities. Different examples are provided with alternative families of dual-feasible functions. We discuss also the difference between the valid inequalities derived by dual-feasible functions and the well-known Chvátal-Gomory cuts.

5.1 Superadditive Functions in Integer Programming

When good dual-feasible functions are sought, they are frequently characterized by superadditivity and monotonicity. For the sake of clarity, these properties are briefly recalled in the sequel for general domains. Given \(X \subseteq \mathbb{R}^{m}\), a function \(F: X \rightarrow \mathbb{R}\) is superadditive if for all x, y ∈ X with x + y ∈ X, it holds that

$$\displaystyle{F(\mathbf{x}) + F(\mathbf{y}) \leq F(\mathbf{x} + \mathbf{y}).}$$

The function \(F: X \rightarrow \mathbb{R}\) is nondecreasing if for all x, y ∈ X, one has that

$$\displaystyle{\mathbf{x} \leq \mathbf{y}\Longrightarrow F(\mathbf{x}) \leq F(\mathbf{y}).}$$

Analogously to the duality theory of linear optimization (without integer constraints), there is also a strong duality theorem in the discrete counterpart. Here superadditive and nondecreasing functions are essential. Given \(\mathbf{A} \in \mathbb{Q}^{m\times n}\), \(\mathbf{b} \in \mathbb{Q}^{m}\) and \(\mathbf{c} \in \mathbb{Q}^{n}\) and an integer linear optimization problem

$$\displaystyle\begin{array}{rcl} \max \mathbf{c}^{\top }\mathbf{x}& &{}\end{array}$$
(5.1)
$$\displaystyle\begin{array}{rcl} \mathrm{s.\,to\,}\mathbf{A}\mathbf{x} \leq \mathbf{b}& &{}\end{array}$$
(5.2)
$$\displaystyle\begin{array}{rcl} \mathbf{x} \in \mathbb{Z}_{+}^{n},& &{}\end{array}$$
(5.3)

the dual consists in determining a nondecreasing and superadditive function \(F: \mathbb{R}^{m} \rightarrow \mathbb{R}\) such that

$$\displaystyle\begin{array}{rcl} \min F(\mathbf{b})& &{}\end{array}$$
(5.4)
$$\displaystyle\begin{array}{rcl} \mathrm{s.\,to\,}F(\mathbf{o}) = 0& &{}\end{array}$$
(5.5)
$$\displaystyle\begin{array}{rcl} F(\mathbf{a}^{\,j}) \geq c_{ j}\mbox{ for }j = 1,\ldots,n,& &{}\end{array}$$
(5.6)

where a j is the j-th column of the matrix A, and o denotes as usual the zero vector. As mentioned before, the relationship between the two problems is given by the strong duality theorem. If the problem (5.1)–(5.3) is solvable, i.e. a feasible x exists and the objective function value is bounded from above, then the optimal objective function values of the primal and the dual problem are equal. If F(b) is unbounded from below (\(-\infty\)), then there is no \(\mathbf{x} \in \mathbb{Z}_{+}^{n}\) fulfilling (5.2), and if (5.1)–(5.3) yields an unbounded objective function value (\(+\infty\)) then F does not exist. Furthermore, if \(\hat{\mathbf{x}}\) is an optimal solution of (5.1)–(5.3) then any optimal F in the dual problem necessarily obeys the equation

$$\displaystyle{F(\mathbf{A}\mathbf{x}) = \mathbf{c}^{\top }\mathbf{x} = F(\mathbf{b}) - F(\mathbf{b} -\mathbf{A}\mathbf{x})}$$

for all \(\mathbf{x} \in \mathbb{Z}_{+}^{n}\) with \(\mathbf{x} \leq \hat{\mathbf{x}}\).

Since the problem (5.1)–(5.3) is NP-hard, solving it exactly or finding an optimal superadditive and nondecreasing function \(F: \mathbb{R}^{m} \rightarrow \mathbb{R}\) according to the above conditions (5.4)–(5.6) may be very difficult. However, contributing to the resolution of (5.1)–(5.3) is possible by deriving valid inequalities using a superadditive and nondecreasing function \(F: \mathbb{R}^{m} \rightarrow \mathbb{R}\) fulfilling the constraints (5.5). These functions lead to the following valid inequalities:

$$\displaystyle{\sum \limits _{j=1}^{n}F(\mathbf{a}^{j}) \times x_{ j} \leq F(\mathbf{b}).}$$

5.2 Valid Inequalities for Integer Programs

General dual-feasible functions can be used not only to compute fast lower bounds, but also to generate valid inequalities for integer problems defined over sets of the kind \(\{\mathbf{x} \in \mathbb{Z}_{+}^{n}: \mathbf{A}\mathbf{x} \leq \mathbf{b}\}\), as stated formally in the sequel.

Proposition 5.1

If f is a maximal general dual-feasible function (and hence a superadditive function with f(0) = 0) and \(S =\{ \mathbf{x} \in \mathbb{Z}_{+}^{n}:\sum _{ j=1}^{n}a_{ij}x_{j} \leq b_{i},\ i = 1,\ldots,m\}\) , then for any i, \(\sum _{j=1}^{n}f(a_{ij})x_{j} \leq f(b_{i})\) is a valid inequality for S.

In Chaps. 2 and 3 it turned out that (general) dual feasible functions should be superadditive to get good lower bounds, because otherwise another dominating function exists. In the context of valid inequalities for integer problems, the same applies. Any valid inequality for S can be obtained either through a superadditive function or it is dominated by an inequality that can be computed in this way. Cuts generated by a superadditive function are commonly referred to as superadditive inequalities. Among these cuts, those that are not dominated by any other valid inequality are called maximal. This applies particularly to the facets of the integer hull of S. Maximal valid inequalities are necessarily superadditive. The same properties characterize the dominant families of dual-feasible functions.

Any maximal inequality for S can be obtained through the Gomory procedure based on recursive linear combinations and rounding of other inequalities for S. However, in order to get these maximal cuts, it might be necessary to use a very long recursion. Other authors assumed that other superadditive functions, eventually more complex ones, might generate these maximal cuts using shorter recursions, demonstrating the relevance of research on dual-feasible functions as tools to compute valid inequalities for integer programs. Other works propose alternative characterizations of the integer hull of S in terms of a finite set of superadditive inequalities, but the cardinality of this set may be very large, such that many cuts are required.

5.3 Examples

In this section, we show through different examples how to apply several generalized dual-feasible functions to derive valid inequalities, which may be better than the well-known Chvátal-Gomory cuts.

Given the inequality system A x ≤ b, \(\mathbf{x} \in \mathbb{N}^{n}\), any nonnegative linear combination of the inequalities may be used to derive cuts. Choosing u ≥ o yields \(\mathbf{u}^{\top }\mathbf{A}\mathbf{x} \leq \mathbf{u}^{\top }\mathbf{b}\), hence the following scalar inequality

$$\displaystyle{ \mathbf{d}^{\top }\mathbf{x} \leq r, }$$
(5.7)

and finally the Chvátal-Gomory cut

$$\displaystyle{ \sum \limits _{j=1}^{n}\lfloor d_{ j}\rfloor \times x_{j} \leq \lfloor r\rfloor. }$$
(5.8)

If r > 0, then dividing the inequality (5.7) by r and applying a maximal general dual-feasible function \(f: \mathbb{R} \rightarrow \mathbb{R}\) with f(1) = 1 leads to the valid inequality

$$\displaystyle{ \sum \limits _{j=1}^{n}f\left (\frac{d_{j}} {r} \right ) \times x_{j} \leq 1. }$$
(5.9)

In some situations it may happen that the inequality (5.9) is stronger than (5.8), but not if 0 < r < 1, as the right-hand sides show immediately. The following example demonstrates the strength of a maximal general dual-feasible function for the construction of valid inequalities, even in the case r = 1.

Example 5.1

We use the function (3.7), p. 65, with the parameter b: = 1, hence

$$\displaystyle\begin{array}{rcl} f(d)& =& \left \{\begin{array}{cl} \lfloor 2d\rfloor, &\mbox{ if }d <1/2, \\ 1/2, &\mbox{ if }d = 1/2, \\ \lceil 2d\rceil - 1,&\mbox{ if }d> 1/2. \end{array} \right.{}\end{array}$$
(5.10)

Let be given the inequality

$$\displaystyle{1.6x_{1} - 0.4x_{2} \leq 1.}$$

Of course, if there would be no negative coefficient then a coefficient d j  > 1 would immediately imply x j  = 0 for that j. The Chvátal-Gomory cut (5.8) transforms the given inequality to \(x_{1} - x_{2} \leq 1\), but the function (5.10) used in (5.9) leads to the stronger inequality \(3x_{1} - x_{2} \leq 1\). This inequality would be obtained by the Chvátal-Gomory procedure only after multiplying the given inequality by a suitable number like 1.9. □

Example 5.2

The dual-feasible function (2.10) is used for deriving valid inequalities. It was defined as

$$\displaystyle{f_{FS,1}(x;k):= \left \{\begin{array}{cl} x, &\mbox{ if }(k + 1) \times x \in \mathbb{N},\\ \lfloor (k + 1) \times x\rfloor /k, &\mbox{ otherwise}. \end{array} \right.}$$

and is again illustrated in Fig. 5.1. Next, we show the result of applying the function f FS, 1 with parameters k ∈ { 1, 2, 3} to a given knapsack inequality (after dividing it by the right-hand side):

$$\displaystyle{\begin{array}{*{13}c} && 9x_{1} & +& 7x_{2} & +& 6x_{3} & +& 4x_{4} & +& 2x_{5} & \leq &12 \\ \hline a_{i}/b &&0.75& &0.58& & 0.5 & &0.33& &0.17& & \\ \hline k = 1&& 1x_{1} & +& 1x_{2} & +&\frac{1} {2}x_{3} & & & & \leq & 1 \\ k = 2 && 1x_{1} & +& \frac{1} {2}x_{2} & +&\frac{1} {2}x_{3} & +& \frac{1} {3}x_{4} & & \leq & 1 \\ k = 3 && \frac{3} {4}x_{1} & +& \frac{2} {3}x_{2} & +&\frac{1} {2}x_{3} & +& \frac{1} {3}x_{4} & & \leq & 1\\ \hline \end{array} }$$
Fig. 5.1
figure 1

MDFF f FS, 1(⋅ ; k) for \(k \in \{ 1,\ldots,4\}\)

Full size image

□

Given multiple knapsack constraints like in the vector packing problem, one may use a VP-MDFF to get cuts.

Example 5.3

Neglecting the integrality constraints in

$$\displaystyle\begin{array}{rcl} 8x_{1} + 5x_{2} + 5x_{3}& \leq & 10 {}\\ 5x_{1} + 8x_{2} + 5x_{3}& \leq & 10 {}\\ x_{1},x_{2},x_{3}& \in & \{0,1\} {}\\ \end{array}$$

would allow the fractional solution x = (0. 5, 0. 8, 0. 2)⊤, because

$$\displaystyle{8 \times 0.5 + 5 \times 0.8 + 5 \times 0.2 = 4 + 4 + 1 = 9 \leq 10}$$

and

$$\displaystyle{5 \times 0.5 + 8 \times 0.8 + 5 \times 0.2 = 2.5 + 6.4 + 1 = 9.9 \leq 10.}$$

However, taking e.g. the VP-MDFF (4.9), p. 65, with the parameter \(\mathbf{u}:= (\frac{1} {2}, \frac{1} {2})^{\top }\), which considers all constraints simultaneously, yields the valid inequality

$$\displaystyle{x_{1} + x_{2} + 0.5x_{3} \leq 1,}$$

which is violated by the fractional solution, since

$$\displaystyle{0.5 + 0.8 + 0.5 \times 0.2 = 1.4> 1.}$$

□

The following example illustrates the generation of valid inequalities with dual-feasible functions obtained from bin packing problems with conflicts.

Example 5.4

Consider the following system of inequalities:

$$\displaystyle\begin{array}{rcl} 4x_{1} + 3x_{2} + 3x_{3}& \leq & 10 {}\\ x_{2} + x_{3}& \leq & 1 {}\\ x_{1},x_{2},x_{3}& \in & \{0,1\} {}\\ \end{array}$$

The first inequality does not restrict anything. However, a BPC-DFF yields the valid inequality

$$\displaystyle{0.9x_{1} + 0.1x_{2} + 0.1x_{3} \leq 1.}$$

The DFF used is the one defined in Proposition 4.17, with J = { 2, 3}, α 2 = 0. 1 and α 3 = 0. 1. □

5.4 Related Literature

In Nemhauser and Wolsey (1998), the relationship between the integer linear optimization problem (5.1)–(5.3) and its dual (5.4)–(5.6) and a revision of superadditive valid inequalities are provided, together with the basic function underlying the Chvátal-Gomory procedure. Previous results on the (explicit or implicit) use of dual-feasible functions to generate valid inequalities for integer programs were reported by Vanderbeck (2000), Alves (2005), Rietz et al (2014), Letchford and Lodi (2002), and Dash and Günlük (2006).

5.5 Exercises

1. Let be given the feasible region \(\sum \limits _{j=1}^{n}a_{ij}x_{j} \leq b_{i}\), \(i = 1,\ldots,m\), \(\mathbf{x} \in \mathbb{N}^{n}\) for an integer linear optimization problem. Which of the following assertions are true? Justify your answer.

  1. (a)

    \(\sum \limits _{i=1}^{n}f(a_{ij})x_{j} \leq f(b_{i})\) is a valid inequality for every general DFF \(f: \mathbb{R} \rightarrow \mathbb{R}\).

  2. (b)

    \(\sum \limits _{i=1}^{n}f(a_{ij})x_{j} \leq f(b_{i})\) is a valid inequality for every superadditive function \(f: \mathbb{R} \rightarrow \mathbb{R}\).

2. Consider the set of all ordered triplets \((x_{1},x_{2},x_{3}) \in \mathbb{Z}_{+}^{3}\), for which

$$\displaystyle\begin{array}{rcl} 5x_{1} + 4x_{2} + 3x_{3}& \leq & 11 {}\\ 3x_{1} + 4x_{2} + 2x_{3}& \leq & 8 {}\\ \end{array}$$

holds. Derive the valid inequality

$$\displaystyle{2x_{1} + 2x_{2} + x_{3} \leq 4}$$

using the VP-MDFF f I, FS, 1 of Corollary 4.1, p. 102, with the parameter choice v: = (3, 2)⊤.

3. Let \(\mathbf{w}:= (1,\ldots,1)^{\top }\in \mathbb{R}^{m}\). Given the inequality system

$$\displaystyle{\sum \limits _{j=1}^{n}\mathbf{a}^{j}x_{ j} \leq \mathbf{w};\;\mathbf{x} \geq \mathbf{o},}$$

where \(\mathbf{a}^{j} \in [0,1]^{m}\) for all j, suppose that a VP-MDFF f: [0, 1]m → [0, 1] yields \(f(\mathbf{a}^{j_{0}}) = 1\) for a certain \(j_{0} \in \{ 1,\ldots,n\}\). Why does this imply f(a j) = 0 for all those j, for which \(\mathbf{a}^{j_{0}} + \mathbf{a}^{j} \leq \mathbf{w}\)? What is the conclusion for the possible usage of the functions of Classes II, III and IV?