Skip to content

Formulations of packing problems

Part 2 · Formulations and their properties · Chapter 10 · Lecture notes, volume 2 (PDF) · Slides · Exercises: Packing problems

Prerequisites

Objectives

At the end of this chapter you will be able to:

  • write the ILP model of the Bin Packing Problem and explain the link between the assignment variables and the activation variables;

  • write the two LP relaxations and their duals, and prove that their optimal value is \(\sum_{j} w_j / c\);

  • round the LP bound up to obtain a lower bound on the number of bins;

  • prove that the LP bound is at least one half of the optimal value, and that the factor is tight;

  • write the ILP model of the Cutting Stock Problem, with integer variables for the copies of the items.

10.1 Overview of the family

  • The ILP models of the packing problems use an upper bound \(m\) on the number of bins and the set \(\mathscr{B} = \{1,2,\dots,m\}\) of the bins that may be used.

  • The assignment variables \(x_{jb}\) place the items \(j \in \mathscr{I}\) into the bins \(b \in \mathscr{B}\), and the binary activation variables \(y_b\) say whether bin \(b\) is used.

  • Each bin gives one capacity constraint, which also links the two kinds of variables, and the objective function minimizes the number \(\sum_{b \in \mathscr{B}} y_b\) of bins used.

The packing models are assignment models: every item, or every copy of an item, is assigned to a used bin, and the items assigned to a bin respect its capacity. The members of the family change the domain of the assignment variables.

  • The table lists the members of the family, with the name of their ILP model and the section that writes it.
Problem Model Assignment variables Section
BPP \(\mathrm{ILP}_{\mathrm{BPP}}\) binary \(x_{jb}\) 10.2
CSP \(\mathrm{ILP}_{\mathrm{CSP}}\) integer \(x_{jb}\), the copies of item \(j\) in bin \(b\) 10.5

  • Overview

    Overview of the family

    Open

  • 10.2 An ILP model for the Bin Packing Problem

    Some important theoretical properties

    Open

  • 10.5 An ILP model for the Cutting Stock Problem

    In summary

    Open

Next: 10.2 An ILP model for the Bin Packing Problem

Exercises on this chapter: Packing problems