부산대학교 도서관

In a combinatorial optimization problem, $n$ discrete variables, $x_1, \ldots, x_n $, belonging to a set $D = \{ 0, \ldots, k-1\} $ of $k$ colors, satisfy an {\it all-different-except-0} predicate if $$ x_i \neq x_{i'} \text{ or } x_i = x_{i'}= 0, \text{ for all } 1 \leq i < i' \leq n. \tag1 $$ Let $S = \{ 1, \ldots, n \}$, and denote by $P$ the set of all points $(x_1, \ldots, x_n) \in D^n$ that satisfy (1). \par The paper proves that the convex hull of $P$ is described by the following linear system: $$ \alignat2 \sum_{i \in J} { x_i} \leq & \sum_{j=1}^{|J|}(k-j), &&\quad \text{for all } J \subseteq S,\ 1 \leq |J| \leq \min\{ n, k-2 \}, \tag2 \\ \sum_{i \in S} { x_i} \leq & \sum_{j=1}^{k-1}(k-j), &&\quad \text{only when } k-1 \leq n, \tag3 \\ x_i \geq 0&, &&\quad \text{for all } i \in S. \tag4 \endalignat $$ First, the authors show the validity of the constraints (2) and (3). Indeed, the biggest values that can be given to $p$ variables are $k-1, k-2,\ldots, k-p$, for any suitable $p$. Then, inequalities (2) and (3) are proved to be facet-defining. Two lemmas on the sign of coefficients of a facet-defining inequality of conv($P$) allow the authors to deduce the description of conv($P$) by the linear system (2)-(4). The proofs are clearly explained and some examples are given.