Exercises — Intro & Modelling

Chapter 1 · Fully solved exercises on ILP modelling and problem classification

Exercise 1: Weighted Independent Set

Problem. Given an undirected graph \(G=(V,E)\) with node weights \(w:V\to\mathbb{R}_{\ge 0}\), formulate an ILP to find the maximum-weight independent set (no two selected nodes are adjacent).

Solution. Introduce a binary variable \(x_v \in \{0,1\}\) for each \(v \in V\), where \(x_v=1\) means node \(v\) is selected.

\[ \begin{aligned} \text{maximize} \quad & \sum_{v \in V} w(v)\, x_v \\ \text{subject to} \quad & x_u + x_v \le 1 & \forall\, \{u,v\} \in E \\ & x_v \in \{0,1\} & \forall\, v \in V \end{aligned} \]

Each edge constraint forbids both endpoints from being simultaneously selected. On the example graph below (5 nodes, 6 edges, weights \(w=[3,5,2,4,1]\)), we enumerate feasible independent sets. The adjacency is: \(1:\{2,3\}\), \(2:\{1,3,4\}\), \(3:\{1,2,5\}\), \(4:\{2,5\}\), \(5:\{3,4\}\). The optimal independent set is \(\{1,4\}\) with weight \(3+4=7\).

Exercise 2: b-Quasiclique

Problem. Given \(G=(V,E)\), weights \(w:V\to\mathbb{N}\), \(b\in\mathbb{N}\). A \(b\)-quasiclique is a set \(S\subseteq V\) with at most \(b\) pairs \(i,j\in S\) where \(ij\notin E\). Write an ILP to find the maximum-weight \(b\)-quasiclique.

Solution. Introduce binary \(x_i\) for \(i\in V\) and binary \(y_{ij}\) for each non-edge \(ij\in\bar{E}\). The variable \(y_{ij}\) captures whether both endpoints of a non-edge are simultaneously in \(S\).

\[ \begin{aligned} \text{maximize} \quad & \sum_{i \in V} w(i)\, x_i \\ \text{subject to} \quad & y_{ij} \le x_i & \forall\, ij \in \bar{E} \\ & y_{ij} \le x_j & \forall\, ij \in \bar{E} \\ & y_{ij} \ge x_i + x_j - 1 & \forall\, ij \in \bar{E} \\ & \sum_{ij \in \bar{E}} y_{ij} \le b \\ & x_i,\, y_{ij} \in \{0,1\} \end{aligned} \]

The three constraints on \(y_{ij}\) linearise the product \(y_{ij} = x_i \cdot x_j \cdot \mathbf{1}[ij\notin E]\). The fourth constraint limits the number of non-edge pairs inside \(S\) to at most \(b\).

On the example below: \(V=\{1,2,3,4\}\), \(E=\{1\text{-}2,\,1\text{-}3,\,1\text{-}4,\,2\text{-}3,\,2\text{-}4\}\) (\(K_4\) minus edge \(3\text{-}4\)). The only non-edge is \(\bar{E}=\{3\text{-}4\}\), so with \(b=1\) all four nodes form a valid \(1\)-quasiclique.

Exercise 3: Set Cover

Problem. Given universe \(U=\{1,\ldots,n\}\) and sets \(S_1,\ldots,S_m \subseteq U\) each with cost \(c_i\), find the minimum-cost collection of sets covering all elements.

Solution. Introduce binary \(x_j \in \{0,1\}\) for each set \(S_j\), where \(x_j=1\) means \(S_j\) is selected.

\[ \begin{aligned} \text{minimize} \quad & \sum_{j=1}^{m} c_j\, x_j \\ \text{subject to} \quad & \sum_{j:\, i \in S_j} x_j \ge 1 & \forall\, i \in U \\ & x_j \in \{0,1\} \end{aligned} \]

Each element constraint ensures that element \(i\) is covered by at least one selected set.

Instance: \(U=\{1,2,3,4,5\}\), \(S_1=\{1,2,3\}\) (\(c=3\)), \(S_2=\{2,4\}\) (\(c=2\)), \(S_3=\{3,5\}\) (\(c=2\)), \(S_4=\{1,4,5\}\) (\(c=4\)). The optimal solution is \(\{S_1, S_2, S_3\}\) with total cost \(3+2+2=7\), covering all elements.

Exercise 4: Problem Classification on Trees

Problem. For each problem, state whether it is polynomial or NP-hard when restricted to trees (undirected acyclic graphs):

  1. Maximum clique
  2. Graph colouring (minimum colours)
  3. Longest path between two given nodes
  4. Minimum vertex cover

Solution.

  1. Maximum clique — Polynomial. Trees have no cycles, so they contain no triangle or larger clique. The maximum clique is either a single node (edgeless tree) or any single edge, giving clique size at most 2. Finding any edge takes \(O(n)\).

  2. Graph colouring — Polynomial. Every tree is bipartite (it has no odd-length cycle). A bipartite graph needs at most 2 colours if it has any edge, or 1 colour if it is edgeless. A 2-colouring can be found by BFS in \(O(n)\).

  3. Longest path — Polynomial. In a tree there is exactly one simple path between any two nodes. That unique path is therefore the longest (and only) path between them. It can be found in \(O(n)\) via BFS/DFS.

  4. Minimum vertex cover — Polynomial. Trees are bipartite, so König’s theorem applies: minimum vertex cover \(=\) maximum matching. A maximum matching on a tree can be found greedily in \(O(n)\), giving the minimum vertex cover size directly.

The visualisation below shows a small 6-node tree illustrating all four results simultaneously.

Exercise 5: Bin Packing Formulation

Problem. There are \(n\) items with sizes \(s_1,\ldots,s_n \in (0,1]\) and \(m\) identical bins of capacity 1. Write an ILP to assign all items to bins minimising the number of bins used.

Solution. Introduce binary \(x_{ij}=1\) if item \(i\) is placed in bin \(j\), and binary \(y_j=1\) if bin \(j\) is used.

\[ \begin{aligned} \text{minimize} \quad & \sum_{j=1}^{m} y_j \\ \text{subject to} \quad & \sum_{j=1}^{m} x_{ij} = 1 & \forall\, i \quad \text{(each item in exactly one bin)} \\ & \sum_{i=1}^{n} s_i\, x_{ij} \le y_j & \forall\, j \quad \text{(capacity; forces } y_j=1 \text{ if used)} \\ & x_{ij} \le y_j & \forall\, i,j \quad \text{(optional tightening)} \\ & x_{ij},\, y_j \in \{0,1\} \end{aligned} \]

Instance: \(n=5\) items, sizes \([0.4,\, 0.6,\, 0.3,\, 0.7,\, 0.5]\), \(m=3\) bins. Total size \(= 2.5 > 2\), so at least 3 bins are needed. Optimal packing: bin 1 \(=\{0.4, 0.6\}\) (full), bin 2 \(=\{0.3, 0.7\}\) (full), bin 3 \(=\{0.5\}\) — exactly 3 bins.