MIP 3: Set Covering, Bin Packing, and Graph Coloring Problems

Packages Used: Functions from the following packages are used in this notebook for the first time:

1. Set Covering

The set covering problem refers to minimizing the number of sets whose union includes all of the objects to be covered. Each set can include (or cover) a different subset of objects, and each object can be covered by multiple sets. There are many applications of set covering; for example, each set might represent the customers that are within a one hour drive of a potential site for a service center, and a solution to the set covering problem would correspond to the minimum number of sites required so that each customer can be serviced within one hour.

General formulation of the problem:

$ \begin{eqnarray*} \quad M &=& \bigl\{ 1, \dots, m \bigr\}, & \quad \mbox{objects to be covered} \\ N &=& \bigl\{ 1, \dots, n \bigr\}, & \quad \mbox{indices of } n \mbox{ subsets of } M \\ M_i &\subseteq& M, i \in N, & \quad n \mbox{ subsets of } M \\ I &\subseteq& N, & \quad \mbox{covering of } M \\ I^* &=& \mathrm{arg}\underset{I}{\operatorname{min}} \bigl\{ \lvert I \rvert : \bigcup_{i \in I} M_i = M \bigr\}, & \quad \mbox{min cost covering of } M. \end{eqnarray*}$

BIP formulation of the problem:

$ \begin{eqnarray*} \quad \mbox{Minimize} \quad \sum_{i \in N} x_i \\ \quad \mbox{subject to} \quad \sum_{i \in N} a_{ji} x_i &\ge& 1, &\quad j \in M\\ x_i &\in& \bigl\{ 0, 1 \bigr\}, &\quad i \in N \end{eqnarray*} $

where

$ \begin{eqnarray*} \quad x_i &=& \begin{cases} 1, & \mbox{if } M_i \mbox{ is in cover} \\ 0, & \mbox{otherwise} \end{cases} \\ a_{ji} &=& \begin{cases} 1, & \mbox{if } j \in M_i \\ 0, & \mbox{otherwise.} \end{cases} \\ \end{eqnarray*} $

Ex 1: 6-Object, 5-Subsets

image.png

$ \begin{eqnarray*} \quad M &=& \bigl\{ 1, \dots, 6 \bigr\} \\ N &=& \bigl\{ 1, \dots, 5 \bigr\} \\ M_1 &=& \bigl\{ 1, 2 \bigr\}, M_2 = \bigl\{ 1, 4, 5 \bigr\}, M_3 = \bigl\{ 3, 5 \bigr\}, M_4 = \bigl\{ 2, 3, 6 \bigr\}, M_5 = \bigl\{ 6 \bigr\} \\ I^* &=& \mathrm{arg}\underset{I}{\operatorname{min}} \bigl\{\sum_{i \in I} x_i : \bigcup_{i \in I} M_i = M \bigr\} = \bigl\{ 2, 4 \bigr\} \\ \sum_{i \in I^*} x_i &=& 2 \end{eqnarray*}$

Ex 2: Set Cover for Dijkstra Undirected Network from Net Mod 2

image.png

Ex 3: Set Cover for U.S. Interstate Road Network

2. Set Packing

BIP formulation of the set packing problem:

$ \begin{eqnarray*} \quad \mbox{Maximize} \quad \sum_{i \in N} x_i \\ \quad \mbox{subject to} \quad \sum_{i \in N} a_{ji} x_i &\le& 1, &\quad j \in M\\ x_i &\in& \bigl\{ 0, 1 \bigr\}. &\quad i \in N \end{eqnarray*} $

Ex 4: Same 6-Object, 5-Subsets as Ex 1

image.png

3. Bin Packing

The bin packing problem involves determining the minimum number of equal-capacity bins required to pack different size objects so that all of the objects assigned to a bin do not exceed its capacity. The 1-D bin packing problem refers to the bins having a single scalar capacity and each object having a single scalar size. The 2-D bin packing problem can, for example, refer to each bin having both weight and cubic volume restrictions on its capacity and each object having a weight and cubic volume.

General formulation of the 1-D bin packing problem (where the capacity restruction is assumed to be cubic volume):

$ \begin{eqnarray*} \quad M &=& \bigl\{ 1, \dots, m \bigr\}, \quad \mbox{objects to be packed into bins} \\ v_j &=& \mbox{volume of object } n \\ V &=& \mbox{volume of each bin } B_i \bigl( \max v_j \le V \bigr) \\ B^* &=& \mathrm{arg}\underset{B}{\operatorname{min}} \bigl\{ \lvert B \rvert : \sum_{j \in B_i} v_j \le V, \bigcup_{B_i \in B} = M \bigr\}, \quad \mbox{min cost bin packing of } M. \end{eqnarray*}$

BIP formulation of the problem:

$ \begin{eqnarray*} \quad \mbox{Minimize} \quad \sum_{i \in N} y_i \\ \quad \mbox{subject to} \quad V y_i &\ge& \sum_{j \in M} v_j x_{ij}, &\quad i \in N &\quad (a) \\ \sum_{i \in N} x_{ij} &=& 1, &\quad j \in M &\quad (b) \\ y_i &\in& \bigl\{ 0, 1 \bigr\}, &\quad i \in N \\ x_{ij} &\in& \bigl\{ 0, 1 \bigr\}, &\quad i \in N, j \in M \end{eqnarray*} $

where

$ \begin{eqnarray*} \quad y_i &=& \begin{cases} 1, & \mbox{if bin } B_i \mbox{ is used in packing} \\ 0, & \mbox{otherwise} \end{cases} \\ x_{ij} &=& \begin{cases} 1, & \mbox{if object } j \mbox{ is packed into bin } B_i \\ 0, & \mbox{otherwise.} \end{cases} \\ \end{eqnarray*} $

In the formulation, there are a set N of potential bins. Constraints (a) ensure that, for each bin, the total volume of the assigned objects do not exceed its capacity, and constraints (b) ensure that, for each object, it is assigned to one bin.

Ex 5: 20-Object Bin Packing

Pack 20 objects ranging randomly in size from 1 to 5 into min number of bins of capacity 10:

Ex 6: 200-Object Bin Packing

Pack 200 objects ranging randomly in size from 1 to 10 into min number of bins of capacity 20:

4. Graph Coloring

The graph coloring problem is to assign colors to the vertices of a graph so that any two vertices connected by an edge are assigned different colors. The edges of a graph and faces of a planar graph could be colored instead of vertices but it is always possible to convert these coloring problems to a vertex covering problem. The graph covering problem has many applications associated with assigning resources to activities where each activity is represented by a vertex, and each edge represents pairs of activities that cannot be assigned to the same resource due to some conflict. Each resource is represented by a different color, and it is usually desired to find the minimum number of colors (resources) required for all of the activities.

General formulation of the problem:

$ \begin{eqnarray*} \quad M &=& \bigl\{ 1, \dots, m \bigr\}, \quad \mbox{set of vertices in graph } G \\ W &=& \mbox{adjacency matrix of } G \\ K^* &=& \mathrm{arg}\underset{K}{\operatorname{min}} \bigl\{ \lvert K \rvert : (i,j) \in W, i \in K_r, j \in K_s, \bigcup_{K_r,K_s \in K} = M \bigr\}, \quad \mbox{min coloring of } G. \end{eqnarray*}$

BIP formulation of the problem:

$ \begin{eqnarray*} \quad \mbox{Minimize} \quad \sum_{k \in N} y_k \\ \quad \mbox{subject to} \quad \sum_{k \in N} x_{ik} &=& 1, &\quad i \in M &\quad (a) \\ x_{ik} + x_{jk} &\le& 1, &\quad (i,j) \in W; k \in N &\quad (b) \\ x_{ik} &\le& y_k, &\quad i \in M, k \in N &\quad (c) \\ y_i &\in& \bigl\{ 0, 1 \bigr\}, &\quad i \in M \\ x_{ij} &\in& \bigl\{ 0, 1 \bigr\}, &\quad i \in M; j \in M \end{eqnarray*} $

where

$ \begin{eqnarray*} \quad y_k &=& \begin{cases} 1, & \mbox{if color } k \mbox{ is used} \\ 0, & \mbox{otherwise} \end{cases} \\ x_{ik} &=& \begin{cases} 1, & \mbox{if vertex } i \mbox{ is colored } k \\ 0, & \mbox{otherwise.} \end{cases} \\ \end{eqnarray*} $

In the formulation, there are a set N of potential colors. Constraints (a) ensure that, for each vertex, it is assigned to one color. Constraints (b) ensure that, for each edge (i,j) of W, if vertex i is assigned to color k then vertex j is not assigned to k (i.e., If X then not Y). Constraints (c) ensure that a vertex can be colored k only if color k is being used.

Ex 8: 5-Vertex Coloring

image.png

Ex 9: U.S. State Map Coloring

image.png

Ex 10: Qualifier Exam Scheduling

In 2019, a total of 30 PhD students took either the OR or ISE Qualifying Exam. Each student selected four areas to be tested in from eleven available areas. The portion of the exam for each area is offered on a different day, and multiple areas can be scheduled for the same day as long as no student is taking both areas. The objective is to determine the minimum number of days required for the exam.

Issue: What if each student took a different number of exams so that each row of L did not have the same number of elements?

Instead of reading a CSV, can create a string of data for three students taking 4, 2, and 3 exams, respectively:

Convert matrix into a nested array: