A new dominance procedure for combinatorial optimization problems (Q1109683): Difference between revisions

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.