Greedy Solution to Bin Packing Problem

Bin Packing Problem

The bin packing problem is a classic combinatorial optimization problem. Imagine you have a finite number of identical “bins” with a certain capacity and a set of “items” with varying sizes. The objective is to pack the items into the fewest bins possible such that the total size of items in each bin does not exceed the bin’s capacity.

• Formal definition

  • Items have size between 0 and 1

  • Bins have capacity 1

  • Each item must be packed into a bin

  • Minimize the number of bins used

• Two variations of the problem

  • Online: Items arrive one at a time and must be immediately packed

  • Offline: All items are known in advance

• NP-hard problem - suitable for approximation algorithms

• Applications in logistics, scheduling, resource allocation, etc.

Algorithms to Solve Bin Packing Problem

• Exact algorithms

  • Brute force

  • Dynamic programming

  • Branch and bound

  • Integer linear programming

• Approximation algorithms

  • Greedy algorithms

• The brute-force algorithm has exponential or factorial time complexity. It serves as a baseline for comparison with other algorithms.

Baseline Solution

• Brute force

  • Create all possible permutations of items

  • Pack the permutations into bins in a deterministic order (e.g. online next fit)

  • Find the permutation that uses the fewest bins

Greedy Solution

Process items one by one, in each step, decide which bin to put the item in. Create a new bin if necessary.

• Heuristics for online bin packing

  • Next Fit: only check the last bin

  • First Fit: check all previous bins for first fit

  • Best Fit: check all previous bins for best (tightest) fit

• A simple greedy solution for offline bin packing (Many complicated alternatives exist)

  • Sort items in decreasing order of size

  • Pack items into bins using online method (first fit or best fit)