From Approximate to Optimal Solutions: Constructing Pruning and Propagation Rules

Abstract

At the heart of many optimization procedur es are powerful pruning and propagation rul es. This paper presents a case study in the construction of such rules. We develop a new algorithm, Complete Decreasing Best Fit, that finds the optimal packing of objects into bins. The algorithm use a branching rule based on the well known Decreasing Best Fit approximation algorithm. In addition, it includes a powerful pruning rule derived from a bound on the solution to the remaining subproblem. Th e bound is constructed by using modular arithmetic to decompose the numerical constraints. We show that the pruning rule adds essentially a constant factor overhead to runtime, whilst reducing search significantly. On the hardest problems , runtime can be redu ce d by an order of magnitude . Finally we demonstrate how propagation rules can be built by adding lookahead to pruning rules. This general approach - optimization procedures built from branching rules based on good approximation algorithms, and pruning and propagation rul es derived from bounds on the remaining subproblem - may be effective on other NP-complete problems.