A new dominance procedure for combinatorial optimization problems (Q1109683)

The effectiveness of branch and bound algorithms can be improved by dominance criteria which allow fathomings of large solution subsets. The authors consider a branch and bound algorithm for solving the combinatorial optimization problem (P): \(v(P)=\min c\) Tx subject to \(x\in F(P)\), and the corresponding branch-decision tree. For each feasible node k of the tree, let \(J^{(k)}\) be the set containing the indices of the fixed variables \(x_ j=x_ j^{(k)}\), any feasible solution \(\tilde x\in F(P)\) with the partial solution \(\tilde x_ j=x_ j^{(k)}\) for \(j\in J^{(k)}\) defines a completion for node k given by values \(\tilde x_ j\) for \(j\not\in J^{(k)}\). A node \(\beta\) dominates a node \(\alpha\) iff: (1) \(J^{(\beta)}\) \(=\) \(J^{(\alpha)}\) (2) \(\sum_{j\in J^{(\beta)}}c_ jx_ j^{(\beta)}\leq\) \(\sum_{j\in J^{(\alpha)}}c_ jx_ j^{(\alpha)}\) (3) any completion for node \(\alpha\) is also a completion for node \(\beta\). In order to check dominance, the authors introduce the neighborhood set \(N^{(\alpha)}\) containing all the nodes \(\beta\) satisfying conditions (1) and (3) and they consider the auxiliary problem: \[ v\quad =\quad \min \quad \sum_{j\in J^{(\alpha)}}c_ jx_ j \] where \(\{x_ j:\) \(j\in J^{(\alpha)}\}\) defines a partial solution associated with a node in \(N^{(\alpha)}.\) The auxiliary problems can be solved exactly or by heuristics. The authors consider the multiple knapsack problem and give several heuristics which are used in the algorithm by \textit{S. Martello} and the second author [ACM Trans. Math. Software 11, 135-140 (1985; Zbl 0562.90061)]. The computational results show that the dominance procedures reduce both the number of nodes and the computing time.