# An Improved Algor i thm for Opt imal B in

@inproceedings{Richard2007AnIA, title={An Improved Algor i thm for Opt imal B in}, author={Packing Richard}, year={2007} }

Given a set of numbers, and a set of bins of fixed capacity, the NP-complete problem of bin packing is to find the minimum number of bins needed to contain the numbers, such that the sum of the numbers assigned to each bin does not exceed the bin capacity. We present two improvements to our previous bin-completion algorithm. The first speeds up the constant factor per node generation, and the second prunes redundant parts of the search tree. The resulting algorithm appears to be asymptotically… Expand

#### Tables from this paper

#### References

SHOWING 1-10 OF 14 REFERENCES

A new algorithm for optimal bin packing

- Computer Science
- AAAI/IAAI
- 2002

This work presents a new algorithm for optimal bin packing, which appears to be asymptotically faster than the best existing optimal algorithm, and runs more that a thousand times faster on problems with 60 numbers. Expand

Bison: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem

- Engineering, Computer Science
- Comput. Oper. Res.
- 1997

For solving BPP-1, an exact hybrid solution procedure, called BISON, is proposed, which favourably combines the well-known meta-strategy tabu search and a branch and bound procedure based on known and new bound arguments and a new branching scheme. Expand

Lower bounds and reduction procedures for the bin packing problem

- Computer Science, Mathematics
- Discret. Appl. Math.
- 1990

Lower bounds and a dominance criterion are presented and a reduction algorithm is derived and an experimental analysis is provided for both lower bounds and reduction algorithm. Expand

Heuristic Solution of Open Bin Packing Problems

- Mathematics, Computer Science
- J. Heuristics
- 1998

The solution of the five open benchmark problems introduced by Falkenauer is reported, and improved packings are given to refute conjectures that previously reported packings were optimal and a proof that the fifth conjecture was correct. Expand

Computational study of a column generation algorithm for bin packing and cutting stock problems

- Mathematics, Computer Science
- Math. Program.
- 1999

The main focus of the research is to study the extend to which standard branch- and-bound enhancement features such as variable fixing, the tightening of the formulation with cutting planes, early branching, and rounding heuristics can be usefully incorporated in a branch-and-price algorithm. Expand

Exact solution of bin-packing problems using column generation and branch-and-bound

- Mathematics, Computer Science
- Ann. Oper. Res.
- 1999

The linear relaxation of this model provides a strong lower bound for the bin‐packing problem and leads to tractable branch‐and‐bound trees for the instances under consideration. Expand

A hybrid grouping genetic algorithm for bin packing

- Mathematics, Computer Science
- J. Heuristics
- 1996

This article describes the GGA paradigm as compared to the classic Holland-style GA and the ordering GA and shows how the bin packing GGA can be enhanced with a local optimization inspired by the dominance criterion. Expand

Branch-and-Price Algorithms for the One-Dimensional Cutting Stock Problem

- Mathematics, Computer Science
- Comput. Optim. Appl.
- 1998

Two branch-and-price approaches for the cutting stock problem are compared, based on a different integer programming formulation of the column generation master problem, which results in a master problem with 0–1 integer variables while the other has general integer variables. Expand

Optimal Integer Solutions to Industrial Cutting Stock Problems

- Mathematics, Computer Science
- INFORMS J. Comput.
- 1999

An extension of a method proposed by Degraeve for embedding a column generation procedure within branch and bound is described and test and it is shown that the algorithm is quite general and can easily cope with various combinations of real world complications. Expand

Computers and Intractability: A Guide to the Theory of NP-Completeness

- Computer Science, Mathematics
- 1978

Horn formulae play a prominent role in artificial intelligence and logic programming. In this paper we investigate the problem of optimal compression of propositional Horn production rule knowledge… Expand