From Approximate to Optimal Solutions: Constructing Pruning and Propagation Rules

Research output: Contribution to conferencePaper

Abstract

At the heart of many optimization procedures are powerful pruning and propagation rules. 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. The 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 reduced 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 rules derived from bounds on the remaining subproblem - may be effective on other NP-complete problems.

Original languageEnglish
Pages1396-1401
Publication statusPublished - 1997

Fingerprint

Dive into the research topics of 'From Approximate to Optimal Solutions: Constructing Pruning and Propagation Rules'. Together they form a unique fingerprint.

Cite this