Skip to content

Formulations of knapsack problems

Part 2 · Formulations and their properties · Chapter 9 · Lecture notes, volume 2 (PDF) · Slides · Exercises: Knapsack problems · App: LP relaxation and upper bounds for the 0/1 KP

Prerequisites

Objectives

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

  • write the ILP model of the 0/1 Knapsack Problem and explain each of its constraints;

  • write the ILP models of the SSP, the BKP, the UKP, the MDKP, the MKP, the MCKP and the KPS, and write them on a numerical instance;

  • write the two LP relaxations and their duals, and compute their optimal solutions with closed formulas;

  • compute the split item, the residual capacity and the value \(z(\mathrm{LP}_{\mathrm{KP}})\);

  • compute the Dantzig and the Martello-Toth upper bounds, rounding them correctly;

  • explain why \(z(\mathrm{LP}_{\mathrm{KP}})\) is never larger than twice \(z(\mathrm{ILP}_{\mathrm{KP}})\).

9.1 Overview of the family

  • The ILP models of the knapsack problems use one variable \(x_j\) for each item \(j \in \mathscr{I}\): a binary variable when the item is selected or not, an integer variable when it counts the selected copies of the item.

  • Each capacity gives one knapsack constraint on the total weight of the selected items, and the objective function maximizes their total profit.

  • The members of the family add an index to the variables (the knapsack \(k\) of item \(j\) in the MKP), some constraints on the classes of items (MCKP, KPS) or binary setup variables \(y_h\) (KPS).

The common pattern of the knapsack models is

\[ \max \Big\{ \sum_{j \in \mathscr{I}} p_j \, x_j \;:\; \sum_{j \in \mathscr{I}} w_j \, x_j \le c,~~ x_j \in D_j~~ \forall j \in \mathscr{I} \Big\}, \]

where the domain \(D_j\) is \(\{0,1\}\), \(\{0,1,\dots,b_j\}\) or \(\Z_{\ge 0}\). The members of the family change the domains and add capacities, knapsacks or classes.

  • The table lists the members of the family, with the name of their ILP model and the section that writes it.
Problem Model Variables Section
KP \(\mathrm{ILP}_{\mathrm{KP}}\) binary \(x_j\) 9.2
SSP \(\mathrm{ILP}_{\mathrm{SSP}}\) binary \(x_j\) 9.6
BKP \(\mathrm{ILP}_{\mathrm{BKP}}\) integer \(x_j \in \{0,1,\dots,b_j\}\) 9.7
UKP \(\mathrm{ILP}_{\mathrm{UKP}}\) integer \(x_j \in \Z_{\ge 0}\) 9.8
MDKP \(\mathrm{ILP}_{\mathrm{MDKP}}\) binary \(x_j\), one constraint per capacity 9.9
MKP \(\mathrm{ILP}_{\mathrm{MKP}}\) binary \(x_{jk}\), item \(j\) in knapsack \(k\) 9.10
MCKP \(\mathrm{ILP}_{\mathrm{MCKP}}\) binary \(x_j\), one item per class 9.11
KPS \(\mathrm{ILP}_{\mathrm{KPS}}\) binary \(x_j\) and setup variables \(y_h\) 9.12

  • Overview

    Overview of the family

    Open

  • 9.2 An ILP model for the 0/1 Knapsack Problem

    Item efficiency · Split item and residual capacity · Some important theoretical properties

    Open

  • 9.6 An ILP model for the Subset Sum Problem

    Open

  • 9.7 An ILP model for the Bounded Knapsack Problem

    Open

  • 9.8 An ILP model for the Unbounded Knapsack Problem

    Open

  • 9.9 An ILP model for the Multidimensional Knapsack Problem

    Open

  • 9.10 An ILP model for the Multiple Knapsack Problem

    Open

  • 9.11 An ILP model for the Multiple-Choice Knapsack Problem

    Open

  • 9.12 An ILP model for the Knapsack Problem with Setups

    In summary

    Open

Next: 9.2 An ILP model for the 0/1 Knapsack Problem

Exercises on this chapter: Knapsack problems

In the interactive lab: LP relaxation and upper bounds for the 0/1 KP.