Lecture Notes on Integer Linear Programming Models for Combinatorial Optimization

Author

Your Name

Published

January 30, 2025

Introduction

In this lecture, we transition from modeling classic, straightforward problems with Integer Linear Programming (ILP) to addressing more complex and realistic scenarios. Previous examples featured problems with readily apparent variables and constraints, resulting in compact and unambiguous models. However, many real-world problems present a variety of modeling possibilities, necessitating a careful consideration of variable and constraint choices. This lecture will explore such problems, emphasizing the discussion of alternative modeling approaches and the rationale behind selecting specific variables and constraints. The examples presented will demonstrate how to construct effective ILP models for intricate, application-driven problems where the optimal modeling strategy is not immediately self-evident.

Time Tabling and Graph Coloring

Time Tabling Problem

Problem Description

The time tabling problem addresses the scheduling of university courses, considering constraints arising from course incompatibilities. Given $N$ courses, each requiring daily lectures, the task is to schedule these lectures into 2-hour slots (e.g., 8:00-10:00, 10:00-12:00, 12:00-14:00). The objective is to assign each course to a daily time slot while respecting predefined incompatibilities between certain course pairs.

Course Incompatibilities

Incompatibilities prevent specific pairs of courses, say $C_i$ and $C_j$, from being scheduled in the same time slot. These incompatibilities stem from several potential conflicts:

Shared Instructor: Courses taught by the same instructor cannot occur simultaneously.
Shared Resources: Courses requiring a unique resource, such as a specialized laboratory, cannot be scheduled concurrently.
Shared Students: Courses mandatory for the same student cohort cannot be scheduled at the same time to avoid student scheduling conflicts.

We are provided with a comprehensive list of incompatible course pairs. Crucially, this incompatibility is slot-independent; incompatible courses can never share a time slot, regardless of the specific slot in question.

Objective: Minimizing Time Slots

The goal is to minimize the total number of daily time slots needed to schedule all courses, ensuring that no incompatible courses are assigned to the same time slot. Assuming all courses are offered daily, the problem seeks the minimum number of slots to accommodate the schedule. For instance, three courses for the same first-year students necessitate at least three distinct time slots to prevent conflicts arising from student overlap.

Graph Coloring Formulation

Vertex Coloring Definition

The time tabling problem can be effectively modeled using graph theory, specifically through vertex coloring.

Given an undirected graph $G = (\mathcal{V}, \mathcal{E})$, vertex coloring is the assignment of colors to each vertex $v \in \mathcal{V}$ such that no two adjacent vertices, connected by an edge $(u, v) \in \mathcal{E}$, share the same color. The objective in the vertex coloring problem is typically to minimize the number of colors used.

Graph Construction for Time Tabling

To model time tabling as a graph coloring problem:

Vertices: Represent each course as a vertex in the graph. Let $\mathcal{V}$ be the set of vertices, with each $v \in \mathcal{V}$ corresponding to a course.
Edges: Introduce an edge between two vertices (courses) if and only if they are incompatible. Let $\mathcal{E}$ be the set of edges, where $(u, v) \in \mathcal{E}$ if course $u$ and course $v$ are incompatible.

This construction yields an incompatibility graph $G = (\mathcal{V}, \mathcal{E})$ where vertices are courses and edges represent scheduling conflicts.

Correspondence between Colors and Time Slots

In this graph representation, assigning a ‘color’ to a vertex (course) is analogous to assigning a time slot. A valid vertex coloring, where no adjacent vertices share a color, directly translates to a valid time table where no incompatible courses are in the same slot.

Each color in a valid vertex coloring corresponds to a unique time slot.
Courses assigned the same color can be scheduled in the same time slot as they are mutually compatible.
The minimum number of colors required for vertex coloring is equivalent to the minimum number of time slots needed to schedule all courses without conflicts.

Therefore, determining the minimum vertex coloring of the incompatibility graph directly solves the time tabling problem by identifying the minimum number of required time slots.

Graph Coloring Problem

Problem Definition

Input: Undirected Graph

The Graph Coloring Problem takes as input an undirected graph $G = (\mathcal{V}, \mathcal{E})$, where $\mathcal{V}$ is the set of vertices and $\mathcal{E}$ is the set of edges. We assume the graph has no isolated vertices. Isolated vertices can be trivially colored with the first color and removed from consideration without affecting the minimum number of colors needed for the rest of the graph.

Objective: Minimize the Number of Colors

The goal is to find a valid vertex coloring of $G$ using the minimum possible number of colors. This minimum number is the chromatic number $\chi(G)$.

Constraint: Proper Coloring

A valid vertex coloring requires that for every edge $(u, v) \in \mathcal{E}$, the color assigned to vertex $u$ must be different from the color assigned to vertex $v$.

Integer Linear Programming Model 1: Color as Integer Variable

Variables: Integer Color Assignment

For each vertex $i \in \mathcal{V}$, we define an integer variable $x_i$ representing the color assigned to vertex $i$.

$x_i \in \mathbb{Z}^+$: Integer color assigned to vertex $i$.

Objective Function: Minimize Maximum Color

We introduce a variable $w$ to represent the maximum color used. The objective is to minimize $w$, thus minimizing the number of colors. \[\min w \label{eq:ilp1_obj}\]

Constraints: Enforcing Proper Coloring

To ensure adjacent vertices have different colors, for each edge $(i, j) \in \mathcal{E}$, we must enforce $x_i \neq x_j$. This is modeled using binary variables and Big-M constraints to linearize the disjunctive constraint ($x_i > x_j$ or $x_j > x_i$).

Binary Variables and Big-M Formulation

For each edge $(i, j) \in \mathcal{E}$, we introduce a binary variable $y_{ij} \in \{0, 1\}$.

$y_{ij} = 0 \implies x_i \geq x_j + 1$
$y_{ij} = 1 \implies x_j \geq x_i + 1$

Using a sufficiently large constant $M$ (Big-M), set to $n$ (number of vertices), the constraints are: $$ \[\begin{aligned} x_i &\geq x_j + 1 - n \cdot y_{ij} & \forall (i, j) \in \mathcal{E}\label{eq:ilp1_con1} \\ x_j &\geq x_i + 1 - n \cdot (1 - y_{ij}) & \forall (i, j) \in \mathcal{E}\label{eq:ilp1_con2} \\ w &\geq x_i & \forall i \in \mathcal{V}\label{eq:ilp1_con3} \end{aligned}\]

$$ Constraints [eq:ilp1_con1] and [eq:ilp1_con2] ensure that for each edge $(i, j)$, colors are different. Constraint [eq:ilp1_con3] ensures $w$ is at least the maximum color. Minimizing $w$ minimizes the highest color index used.

Integer Linear Programming Model 2: Binary Color Assignment Variables

Variables: Binary Vertex-Color Assignment

We introduce binary variables $x_{ic}$ for each vertex $i \in \mathcal{V}$ and each possible color $c \in \{1, 2, \dots, n\}$.

$x_{ic} \in \{0, 1\}$:
- $x_{ic} = 1$ if vertex $i$ is assigned color $c$.
- $x_{ic} = 0$ otherwise.

Variables: Binary Color Usage

We define binary variables $y_c$ for each color $c \in \{1, 2, \dots, n\}$ to indicate if color $c$ is used.

$y_c \in \{0, 1\}$:
- $y_c = 1$ if color $c$ is used by at least one vertex.
- $y_c = 0$ otherwise.

Objective Function: Minimize Number of Colors Used

The objective is to minimize the number of colors used, represented by the sum of $y_c$ variables. \[\min \sum_{c=1}^{n} y_c \label{eq:ilp2_obj}\]

Constraints: Unique Color Assignment

Each vertex must be assigned exactly one color. \[\sum_{c=1}^{n} x_{ic} = 1 \quad \forall i \in \mathcal{V}\label{eq:ilp2_con1}\]

Constraints: Linking Color Usage and Assignment

If a vertex $i$ is assigned color $c$ ($x_{ic}=1$), then color $c$ must be considered used ($y_c=1$). \[x_{ic} \leq y_c \quad \forall i \in \mathcal{V}, \forall c \in \{1, 2, \dots, n\} \label{eq:ilp2_con2}\]

Constraints: Proper Coloring

For each edge $(i, j) \in \mathcal{E}$, vertices $i$ and $j$ cannot have the same color. \[x_{ic} + x_{jc} \leq 1 \quad \forall (i, j) \in \mathcal{E}, \forall c \in \{1, 2, \dots, n\} \label{eq:ilp2_con3}\] This ensures that for any edge $(i, j)$ and any color $c$, at most one of the vertices $i$ or $j$ can be colored with $c$.

Baggage Handling Problem

Problem Description

Airline Baggage Policy

Consider an airline with the following baggage policy: passengers are allowed two free carry-on items, a small personal item and a standard carry-on bag, with weight restrictions. Additional baggage must be checked for a fee, with weight limits and overweight charges. The specifics are as follows:

Free Carry-on Baggage: Each passenger may bring on board:
- One personal item (e.g., purse, laptop bag) with a maximum weight of 6 kg.
- One carry-on bag (e.g., small suitcase) with a maximum weight of 10 kg.
Checked Baggage (for each additional bag):
- Fee: €25 per checked bag.
- Weight Limit: Maximum 20 kg per checked bag.
- Overweight Charge: €2 per kilogram for any weight exceeding 20 kg in a checked bag.

Objective: Minimizing Baggage Costs

Given a set of $n$ indivisible items with known weights $w_1, w_2, \dots, w_n$, where each $w_i \leq 20$ kg, the goal is to determine how to distribute these items into different types of bags (personal item, carry-on, and checked bags) such that the total baggage cost is minimized. The total cost includes checked baggage fees and overweight charges.

Integer Linear Programming Model Formulation

Variables

To formulate this problem as an Integer Linear Program, we define the following variables:

Binary Bag Usage Variables: For each bag type $j$, we define a binary variable $y_j$ to indicate if bag $j$ is used. We index bag types as: $j=1$ for the personal item, $j=2$ for the carry-on bag, and $j \in \{3, 4, \dots, n+2\}$ for potential checked bags. We assume up to $n$ checked bags might be necessary. \[y_j = \begin{cases} 1 & \text{if bag } j \text{ is used} \\ 0 & \text{otherwise} \end{cases} \quad \text{for } j \in \{1, 2, \dots, n+2\}\]
Real Extra Weight Variables: For each checked bag $j \in \{3, 4, \dots, n+2\}$, we define a continuous variable $z_j$ to represent the weight exceeding the 20 kg limit, if any. \[z_j \geq 0: \text{ extra weight in checked bag } j \text{ (in kg), for } j \in \{3, 4, \dots, n+2\}\]
Binary Item-Bag Assignment Variables: For each item $i$ and bag type $j$, we define a binary variable $x_{ij}$ to indicate if item $i$ is placed in bag $j$. \[x_{ij} = \begin{cases} 1 & \text{if item } i \text{ is placed in bag } j \\ 0 & \text{otherwise} \end{cases} \quad \text{for } i \in \{1, 2, \dots, n\}, j \in \{1, 2, \dots, n+2\}\]

Objective Function: Minimize Total Cost

The objective is to minimize the total baggage cost, which is the sum of the costs for all checked bags, including the base fee and overweight charges. The carry-on bags (types 1 and 2) are free and do not contribute to the cost. \[\min \sum_{j=3}^{n+2} (25 y_j + 2 z_j) \label{eq:baggage_obj}\]

Constraints

We must define constraints to ensure a valid baggage assignment according to the airline’s policy.

Each Item in Exactly One Bag: Every item must be placed in exactly one bag. \[\sum_{j=1}^{n+2} x_{ij} = 1 \quad \forall i \in \{1, 2, \dots, n\} \label{eq:baggage_con1}\]
Carry-on Weight Limits: The total weight of items in the personal item bag (bag 1) must not exceed 6 kg, and in the carry-on bag (bag 2) must not exceed 10 kg. $$
\[\begin{aligned} \sum_{i=1}^{n} w_i x_{i1} &\leq 6 \label{eq:baggage_con2} \\ \sum_{i=1}^{n} w_i x_{i2} &\leq 10 \label{eq:baggage_con3} \end{aligned}\]
$$
Linking Bag Usage and Item Assignment: If any item is assigned to bag $j$, then $y_j$ must be set to 1, indicating that bag $j$ is used. \[x_{ij} \leq y_j \quad \forall i \in \{1, 2, \dots, n\}, \forall j \in \{1, 2, \dots, n+2\} \label{eq:baggage_con4}\]
Calculating Extra Weight for Checked Bags: For each checked bag $j \in \{3, 4, \dots, n+2\}$, the extra weight $z_j$ is defined as the excess weight over 20 kg, or zero if the weight is within the limit. This is enforced by: \[z_j \geq \sum_{i=1}^{n} w_i x_{ij} - 20 \quad \forall j \in \{3, 4, \dots, n+2\} \label{eq:baggage_con6}\] and \[z_j \geq 0 \quad \forall j \in \{3, 4, \dots, n+2\} \label{eq:baggage_con7}\]

Remark. Remark 1 (Redundancy of Big M Constraint).

A constraint of the form $z_j \leq M \cdot y_j$ for $j \geq 3$, which might initially seem necessary to link extra weight to bag usage, is actually redundant. If $y_j = 0$, constraint [eq:baggage_con4] forces $x_{ij} = 0$ for all items $i$, making $\sum_{i=1}^{n} w_i x_{ij} = 0$. Then, constraint [eq:baggage_con6] becomes $z_j \geq -20$. Combined with $z_j \geq 0$ and the minimization of $z_j$ in the objective function [eq:baggage_obj], the solver will naturally set $z_j = 0$ when $y_j = 0$. Thus, an explicit upper bound constraint like $z_j \leq M \cdot y_j$ is not required for model correctness.

The complete Integer Linear Programming model for the baggage handling problem is to minimize the objective function [eq:baggage_obj] subject to the constraints [eq:baggage_con1], [eq:baggage_con2], [eq:baggage_con3], [eq:baggage_con4], [eq:baggage_con6], and [eq:baggage_con7].

Conclusion

This lecture extended our application of Integer Linear Programming (ILP) to model more complex combinatorial optimization problems, specifically the Time Tabling Problem and the Baggage Handling Problem. We demonstrated how the Time Tabling Problem can be recast as a Graph Coloring Problem, and presented two distinct ILP formulations for graph coloring, including a refined model with stronger constraints for potentially improved solver performance. For the Baggage Handling Problem, we developed an ILP model to minimize the cost of baggage according to a detailed airline policy, showcasing the critical role of variable selection and constraint design in capturing real-world complexities. These examples illustrate the power and flexibility of ILP in addressing intricate optimization challenges across diverse application domains. The process highlighted the translation of problem descriptions into formal mathematical models, a crucial step for leveraging computational methods to find optimal or near-optimal solutions.

Further considerations for these problems include:

Exploring alternative ILP formulations and their comparative strengths and weaknesses.
Analyzing the computational complexity of the presented ILP models and methods for complexity reduction.
Investigating efficient algorithms and solvers for practical implementation and scalability.

--- title: "Lecture Notes on Integer Linear Programming Models for Combinatorial Optimization" author: "Your Name" date: "2025-01-30" format: html: toc: true # Table of Contents toc-depth: 2 code-tools: true theme: cosmo # Or "journal" for Distill-like minimalism --- # Introduction In this lecture, we transition from modeling classic, straightforward problems with Integer Linear Programming (ILP) to addressing more complex and realistic scenarios. Previous examples featured problems with readily apparent variables and constraints, resulting in compact and unambiguous models. However, many real-world problems present a variety of modeling possibilities, necessitating a careful consideration of variable and constraint choices. This lecture will explore such problems, emphasizing the discussion of alternative modeling approaches and the rationale behind selecting specific variables and constraints. The examples presented will demonstrate how to construct effective ILP models for intricate, application-driven problems where the optimal modeling strategy is not immediately self-evident. # Time Tabling and Graph Coloring ## Time Tabling Problem ### Problem Description The time tabling problem addresses the scheduling of university courses, considering constraints arising from course incompatibilities. Given $N$ courses, each requiring daily lectures, the task is to schedule these lectures into 2-hour slots (e.g., 8:00-10:00, 10:00-12:00, 12:00-14:00). The objective is to assign each course to a daily time slot while respecting predefined incompatibilities between certain course pairs. ### Course Incompatibilities Incompatibilities prevent specific pairs of courses, say $C_i$ and $C_j$, from being scheduled in the same time slot. These incompatibilities stem from several potential conflicts: - **Shared Instructor:** Courses taught by the same instructor cannot occur simultaneously. - **Shared Resources:** Courses requiring a unique resource, such as a specialized laboratory, cannot be scheduled concurrently. - **Shared Students:** Courses mandatory for the same student cohort cannot be scheduled at the same time to avoid student scheduling conflicts. We are provided with a comprehensive list of incompatible course pairs. Crucially, this incompatibility is slot-independent; incompatible courses can never share a time slot, regardless of the specific slot in question. ### Objective: Minimizing Time Slots The goal is to minimize the total number of daily time slots needed to schedule all courses, ensuring that no incompatible courses are assigned to the same time slot. Assuming all courses are offered daily, the problem seeks the minimum number of slots to accommodate the schedule. For instance, three courses for the same first-year students necessitate at least three distinct time slots to prevent conflicts arising from student overlap. ## Graph Coloring Formulation ### Vertex Coloring Definition The time tabling problem can be effectively modeled using graph theory, specifically through vertex coloring. ::: tcolorbox Given an undirected graph $G = (\mathcal{V}, \mathcal{E})$, vertex coloring is the assignment of colors to each vertex $v \in \mathcal{V}$ such that no two adjacent vertices, connected by an edge $(u, v) \in \mathcal{E}$, share the same color. The objective in the vertex coloring problem is typically to minimize the number of colors used. ::: ### Graph Construction for Time Tabling To model time tabling as a graph coloring problem: - **Vertices:** Represent each course as a vertex in the graph. Let $\mathcal{V}$ be the set of vertices, with each $v \in \mathcal{V}$ corresponding to a course. - **Edges:** Introduce an edge between two vertices (courses) if and only if they are incompatible. Let $\mathcal{E}$ be the set of edges, where $(u, v) \in \mathcal{E}$ if course $u$ and course $v$ are incompatible. This construction yields an incompatibility graph $G = (\mathcal{V}, \mathcal{E})$ where vertices are courses and edges represent scheduling conflicts. ### Correspondence between Colors and Time Slots In this graph representation, assigning a 'color' to a vertex (course) is analogous to assigning a time slot. A valid vertex coloring, where no adjacent vertices share a color, directly translates to a valid time table where no incompatible courses are in the same slot. - Each color in a valid vertex coloring corresponds to a unique time slot. - Courses assigned the same color can be scheduled in the same time slot as they are mutually compatible. - The minimum number of colors required for vertex coloring is equivalent to the minimum number of time slots needed to schedule all courses without conflicts. Therefore, determining the minimum vertex coloring of the incompatibility graph directly solves the time tabling problem by identifying the minimum number of required time slots. # Graph Coloring Problem ## Problem Definition ### Input: Undirected Graph The Graph Coloring Problem takes as input an undirected graph $G = (\mathcal{V}, \mathcal{E})$, where $\mathcal{V}$ is the set of vertices and $\mathcal{E}$ is the set of edges. We assume the graph has no isolated vertices. Isolated vertices can be trivially colored with the first color and removed from consideration without affecting the minimum number of colors needed for the rest of the graph. ### Objective: Minimize the Number of Colors The goal is to find a valid vertex coloring of $G$ using the minimum possible number of colors. This minimum number is the chromatic number $\chi(G)$. ### Constraint: Proper Coloring A valid vertex coloring requires that for every edge $(u, v) \in \mathcal{E}$, the color assigned to vertex $u$ must be different from the color assigned to vertex $v$. ## Integer Linear Programming Model 1: Color as Integer Variable ### Variables: Integer Color Assignment For each vertex $i \in \mathcal{V}$, we define an integer variable $x_i$ representing the color assigned to vertex $i$. - $x_i \in \mathbb{Z}^+$: Integer color assigned to vertex $i$. ### Objective Function: Minimize Maximum Color We introduce a variable $w$ to represent the maximum color used. The objective is to minimize $w$, thus minimizing the number of colors. $$\min w \label{eq:ilp1_obj}$$ ### Constraints: Enforcing Proper Coloring To ensure adjacent vertices have different colors, for each edge $(i, j) \in \mathcal{E}$, we must enforce $x_i \neq x_j$. This is modeled using binary variables and Big-M constraints to linearize the disjunctive constraint ($x_i > x_j$ or $x_j > x_i$). ### Binary Variables and Big-M Formulation For each edge $(i, j) \in \mathcal{E}$, we introduce a binary variable $y_{ij} \in \{0, 1\}$. - $y_{ij} = 0 \implies x_i \geq x_j + 1$ - $y_{ij} = 1 \implies x_j \geq x_i + 1$ Using a sufficiently large constant $M$ (Big-M), set to $n$ (number of vertices), the constraints are: $$\begin{aligned} x_i &\geq x_j + 1 - n \cdot y_{ij} & \forall (i, j) \in \mathcal{E}\label{eq:ilp1_con1} \\ x_j &\geq x_i + 1 - n \cdot (1 - y_{ij}) & \forall (i, j) \in \mathcal{E}\label{eq:ilp1_con2} \\ w &\geq x_i & \forall i \in \mathcal{V}\label{eq:ilp1_con3} \end{aligned}$$ Constraints [\[eq:ilp1_con1\]](#eq:ilp1_con1){reference-type="eqref" reference="eq:ilp1_con1"} and [\[eq:ilp1_con2\]](#eq:ilp1_con2){reference-type="eqref" reference="eq:ilp1_con2"} ensure that for each edge $(i, j)$, colors are different. Constraint [\[eq:ilp1_con3\]](#eq:ilp1_con3){reference-type="eqref" reference="eq:ilp1_con3"} ensures $w$ is at least the maximum color. Minimizing $w$ minimizes the highest color index used. ## Integer Linear Programming Model 2: Binary Color Assignment Variables ### Variables: Binary Vertex-Color Assignment We introduce binary variables $x_{ic}$ for each vertex $i \in \mathcal{V}$ and each possible color $c \in \{1, 2, \dots, n\}$. - $x_{ic} \in \{0, 1\}$: - $x_{ic} = 1$ if vertex $i$ is assigned color $c$. - $x_{ic} = 0$ otherwise. ### Variables: Binary Color Usage We define binary variables $y_c$ for each color $c \in \{1, 2, \dots, n\}$ to indicate if color $c$ is used. - $y_c \in \{0, 1\}$: - $y_c = 1$ if color $c$ is used by at least one vertex. - $y_c = 0$ otherwise. ### Objective Function: Minimize Number of Colors Used The objective is to minimize the number of colors used, represented by the sum of $y_c$ variables. $$\min \sum_{c=1}^{n} y_c \label{eq:ilp2_obj}$$ ### Constraints: Unique Color Assignment Each vertex must be assigned exactly one color. $$\sum_{c=1}^{n} x_{ic} = 1 \quad \forall i \in \mathcal{V}\label{eq:ilp2_con1}$$ ### Constraints: Linking Color Usage and Assignment If a vertex $i$ is assigned color $c$ ($x_{ic}=1$), then color $c$ must be considered used ($y_c=1$). $$x_{ic} \leq y_c \quad \forall i \in \mathcal{V}, \forall c \in \{1, 2, \dots, n\} \label{eq:ilp2_con2}$$ ### Constraints: Proper Coloring For each edge $(i, j) \in \mathcal{E}$, vertices $i$ and $j$ cannot have the same color. $$x_{ic} + x_{jc} \leq 1 \quad \forall (i, j) \in \mathcal{E}, \forall c \in \{1, 2, \dots, n\} \label{eq:ilp2_con3}$$ This ensures that for any edge $(i, j)$ and any color $c$, at most one of the vertices $i$ or $j$ can be colored with $c$. ## Model Refinement: Stronger Constraints ### Combining Constraints for Improved Formulation Model 2 can be strengthened by combining constraints [\[eq:ilp2_con2\]](#eq:ilp2_con2){reference-type="eqref" reference="eq:ilp2_con2"} and [\[eq:ilp2_con3\]](#eq:ilp2_con3){reference-type="eqref" reference="eq:ilp2_con3"} into a single set of constraints, leading to a tighter and potentially more efficient ILP formulation. ### Refined Constraints We replace constraints [\[eq:ilp2_con2\]](#eq:ilp2_con2){reference-type="eqref" reference="eq:ilp2_con2"} and [\[eq:ilp2_con3\]](#eq:ilp2_con3){reference-type="eqref" reference="eq:ilp2_con3"} with the following stronger constraint: $$x_{ic} + x_{jc} \leq y_c \quad \forall (i, j) \in \mathcal{E}, \forall c \in \{1, 2, \dots, n\} \label{eq:ilp_refined_con1}$$ ::: tcolorbox Constraint [\[eq:ilp_refined_con1\]](#eq:ilp_refined_con1){reference-type="eqref" reference="eq:ilp_refined_con1"} is stronger because it implies both [\[eq:ilp2_con2\]](#eq:ilp2_con2){reference-type="eqref" reference="eq:ilp2_con2"} and [\[eq:ilp2_con3\]](#eq:ilp2_con3){reference-type="eqref" reference="eq:ilp2_con3"}. - **Implication of [\[eq:ilp2_con3\]](#eq:ilp2_con3){reference-type="eqref" reference="eq:ilp2_con3"}:** If $y_c = 1$, then [\[eq:ilp_refined_con1\]](#eq:ilp_refined_con1){reference-type="eqref" reference="eq:ilp_refined_con1"} reduces to $x_{ic} + x_{jc} \leq 1$, which is exactly constraint [\[eq:ilp2_con3\]](#eq:ilp2_con3){reference-type="eqref" reference="eq:ilp2_con3"}, ensuring no two adjacent vertices share the same color. - **Implication of [\[eq:ilp2_con2\]](#eq:ilp2_con2){reference-type="eqref" reference="eq:ilp2_con2"}:** For any vertex $i$ and color $c$, consider an edge $(i, j) \in \mathcal{E}$ incident to $i$ (assuming no isolated vertices). From [\[eq:ilp_refined_con1\]](#eq:ilp_refined_con1){reference-type="eqref" reference="eq:ilp_refined_con1"}, we have $x_{ic} + x_{jc} \leq y_c$. Since $x_{jc} \geq 0$, it follows that $x_{ic} \leq y_c$, which is constraint [\[eq:ilp2_con2\]](#eq:ilp2_con2){reference-type="eqref" reference="eq:ilp2_con2"}, linking color assignment to color usage. ::: The refined ILP model for graph coloring minimizes the objective function [\[eq:ilp2_obj\]](#eq:ilp2_obj){reference-type="eqref" reference="eq:ilp2_obj"} subject to constraints [\[eq:ilp2_con1\]](#eq:ilp2_con1){reference-type="eqref" reference="eq:ilp2_con1"} and [\[eq:ilp_refined_con1\]](#eq:ilp_refined_con1){reference-type="eqref" reference="eq:ilp_refined_con1"}. This formulation generally leads to a more efficient solution process due to the tighter constraints reducing the feasible region of the linear programming relaxation. # Baggage Handling Problem ## Problem Description ### Airline Baggage Policy Consider an airline with the following baggage policy: passengers are allowed two free carry-on items, a small personal item and a standard carry-on bag, with weight restrictions. Additional baggage must be checked for a fee, with weight limits and overweight charges. The specifics are as follows: - **Free Carry-on Baggage:** Each passenger may bring on board: - One personal item (e.g., purse, laptop bag) with a maximum weight of 6 kg. - One carry-on bag (e.g., small suitcase) with a maximum weight of 10 kg. - **Checked Baggage (for each additional bag):** - Fee: €25 per checked bag. - Weight Limit: Maximum 20 kg per checked bag. - Overweight Charge: €2 per kilogram for any weight exceeding 20 kg in a checked bag. ### Objective: Minimizing Baggage Costs Given a set of $n$ indivisible items with known weights $w_1, w_2, \dots, w_n$, where each $w_i \leq 20$ kg, the goal is to determine how to distribute these items into different types of bags (personal item, carry-on, and checked bags) such that the total baggage cost is minimized. The total cost includes checked baggage fees and overweight charges. ## Integer Linear Programming Model Formulation ### Variables To formulate this problem as an Integer Linear Program, we define the following variables: - **Binary Bag Usage Variables:** For each bag type $j$, we define a binary variable $y_j$ to indicate if bag $j$ is used. We index bag types as: $j=1$ for the personal item, $j=2$ for the carry-on bag, and $j \in \{3, 4, \dots, n+2\}$ for potential checked bags. We assume up to $n$ checked bags might be necessary. $$y_j = \begin{cases} 1 & \text{if bag } j \text{ is used} \\ 0 & \text{otherwise} \end{cases} \quad \text{for } j \in \{1, 2, \dots, n+2\}$$ - **Real Extra Weight Variables:** For each checked bag $j \in \{3, 4, \dots, n+2\}$, we define a continuous variable $z_j$ to represent the weight exceeding the 20 kg limit, if any. $$z_j \geq 0: \text{ extra weight in checked bag } j \text{ (in kg), for } j \in \{3, 4, \dots, n+2\}$$ - **Binary Item-Bag Assignment Variables:** For each item $i$ and bag type $j$, we define a binary variable $x_{ij}$ to indicate if item $i$ is placed in bag $j$. $$x_{ij} = \begin{cases} 1 & \text{if item } i \text{ is placed in bag } j \\ 0 & \text{otherwise} \end{cases} \quad \text{for } i \in \{1, 2, \dots, n\}, j \in \{1, 2, \dots, n+2\}$$ ### Objective Function: Minimize Total Cost The objective is to minimize the total baggage cost, which is the sum of the costs for all checked bags, including the base fee and overweight charges. The carry-on bags (types 1 and 2) are free and do not contribute to the cost. $$\min \sum_{j=3}^{n+2} (25 y_j + 2 z_j) \label{eq:baggage_obj}$$ ### Constraints We must define constraints to ensure a valid baggage assignment according to the airline's policy. 1. **Each Item in Exactly One Bag:** Every item must be placed in exactly one bag. $$\sum_{j=1}^{n+2} x_{ij} = 1 \quad \forall i \in \{1, 2, \dots, n\} \label{eq:baggage_con1}$$ 2. **Carry-on Weight Limits:** The total weight of items in the personal item bag (bag 1) must not exceed 6 kg, and in the carry-on bag (bag 2) must not exceed 10 kg. $$\begin{aligned} \sum_{i=1}^{n} w_i x_{i1} &\leq 6 \label{eq:baggage_con2} \\ \sum_{i=1}^{n} w_i x_{i2} &\leq 10 \label{eq:baggage_con3} \end{aligned}$$ 3. **Linking Bag Usage and Item Assignment:** If any item is assigned to bag $j$, then $y_j$ must be set to 1, indicating that bag $j$ is used. $$x_{ij} \leq y_j \quad \forall i \in \{1, 2, \dots, n\}, \forall j \in \{1, 2, \dots, n+2\} \label{eq:baggage_con4}$$ 4. **Calculating Extra Weight for Checked Bags:** For each checked bag $j \in \{3, 4, \dots, n+2\}$, the extra weight $z_j$ is defined as the excess weight over 20 kg, or zero if the weight is within the limit. This is enforced by: $$z_j \geq \sum_{i=1}^{n} w_i x_{ij} - 20 \quad \forall j \in \{3, 4, \dots, n+2\} \label{eq:baggage_con6}$$ and $$z_j \geq 0 \quad \forall j \in \{3, 4, \dots, n+2\} \label{eq:baggage_con7}$$ :::: remark **Remark 1** (Redundancy of Big M Constraint). ::: tcolorbox A constraint of the form $z_j \leq M \cdot y_j$ for $j \geq 3$, which might initially seem necessary to link extra weight to bag usage, is actually redundant. If $y_j = 0$, constraint [\[eq:baggage_con4\]](#eq:baggage_con4){reference-type="eqref" reference="eq:baggage_con4"} forces $x_{ij} = 0$ for all items $i$, making $\sum_{i=1}^{n} w_i x_{ij} = 0$. Then, constraint [\[eq:baggage_con6\]](#eq:baggage_con6){reference-type="eqref" reference="eq:baggage_con6"} becomes $z_j \geq -20$. Combined with $z_j \geq 0$ and the minimization of $z_j$ in the objective function [\[eq:baggage_obj\]](#eq:baggage_obj){reference-type="eqref" reference="eq:baggage_obj"}, the solver will naturally set $z_j = 0$ when $y_j = 0$. Thus, an explicit upper bound constraint like $z_j \leq M \cdot y_j$ is not required for model correctness. ::: :::: The complete Integer Linear Programming model for the baggage handling problem is to minimize the objective function [\[eq:baggage_obj\]](#eq:baggage_obj){reference-type="eqref" reference="eq:baggage_obj"} subject to the constraints [\[eq:baggage_con1\]](#eq:baggage_con1){reference-type="eqref" reference="eq:baggage_con1"}, [\[eq:baggage_con2\]](#eq:baggage_con2){reference-type="eqref" reference="eq:baggage_con2"}, [\[eq:baggage_con3\]](#eq:baggage_con3){reference-type="eqref" reference="eq:baggage_con3"}, [\[eq:baggage_con4\]](#eq:baggage_con4){reference-type="eqref" reference="eq:baggage_con4"}, [\[eq:baggage_con6\]](#eq:baggage_con6){reference-type="eqref" reference="eq:baggage_con6"}, and [\[eq:baggage_con7\]](#eq:baggage_con7){reference-type="eqref" reference="eq:baggage_con7"}. # Conclusion This lecture extended our application of Integer Linear Programming (ILP) to model more complex combinatorial optimization problems, specifically the Time Tabling Problem and the Baggage Handling Problem. We demonstrated how the Time Tabling Problem can be recast as a Graph Coloring Problem, and presented two distinct ILP formulations for graph coloring, including a refined model with stronger constraints for potentially improved solver performance. For the Baggage Handling Problem, we developed an ILP model to minimize the cost of baggage according to a detailed airline policy, showcasing the critical role of variable selection and constraint design in capturing real-world complexities. These examples illustrate the power and flexibility of ILP in addressing intricate optimization challenges across diverse application domains. The process highlighted the translation of problem descriptions into formal mathematical models, a crucial step for leveraging computational methods to find optimal or near-optimal solutions. Further considerations for these problems include: - Exploring alternative ILP formulations and their comparative strengths and weaknesses. - Analyzing the computational complexity of the presented ILP models and methods for complexity reduction. - Investigating efficient algorithms and solvers for practical implementation and scalability.