---
title: "From Approximate to Optimal Solutions: Constructing Pruning and Propagation Rules"
authors:
  - "Ian P. Gent"
  - "Toby Walsh"
doi: ""
url: "https://ijcai.org/proceedings/1997/201"
pdf: "https://ijcai.org/proceedings/1997/0201.pdf"
venue: "Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence"
year: 1997
pages: "1396-1400"
track: "Search"
keywords:
---

# From Approximate to Optimal Solutions: Constructing Pruning and Propagation Rules

Ian P. Gent, Toby Walsh

*Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence*, pages 1396-1400.

## 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.