integer-linear-programming-models

Integer Linear Programming (ILP) models for total graph coloring and transmitter scheduling.

Integer Linear Programming: Operations Research Models

Author: Aleksandra Syska
Context: Academic Project – Mathematical Modeling, Faculty of Mathematics and Information Science (MiNI), Warsaw University of Technology (PW)[cite: 3].

This repository contains two decision optimization models solved using Integer Linear Programming (ILP)[cite: 3]. The project demonstrates the ability to translate complex mathematical requirements and logical constraints into computational models.

Technologies & Tools

• Modeling Language: AMPL
• Solver: Gurobi Optimizer
• Techniques: Integer Linear Programming (ILP)[cite: 3], Big-M method[cite: 3], Minimax objective modeling[cite: 3].

Project 1: Total Graph Coloring Optimization

The first task focuses on finding the total coloring of a graph $G=(V,E)$ utilizing a given pool of $k$ colors[cite: 3]. A total coloring is defined as a function $f:V\cup E\rightarrow[k]$[cite: 3]. The goal is not just to find a feasible coloring, but to minimize the maximum color used, effectively expressing the minimax relationship $z = \max(x_1, x_2, ..., x_n)$ through linear constraints and the objective function[cite: 3].

Mathematical Constraints Applied:

• Adjacent vertices must not share the same color[cite: 3].
• Incident edges sharing a common vertex must not share the same color[cite: 3].
• An edge and its incident vertices must have different colors[cite: 3].

Data & Testing: The model requires the number of vertices $n$, an adjacency matrix $E$, and the maximum available colors $K$[cite: 1]. It was tested and validated for $K \in {3, 4, 5}$ across multiple graph topologies[cite: 1, 3].

Project 2: Data Center Transmitter Scheduling

The second model solves a network coverage problem using spatial and cost parameters[cite: 3]. A data center operates several transmitters distributed across a city, serving receivers located on a $5\times5$ coordinate grid[cite: 2, 3]. The objective is to schedule transmitter activations over $d$ days ($d \in {3, 4, 5}$) to minimize total operational transmission costs[cite: 2, 3].

Mathematical Constraints Applied:

• Coverage Guarantee: Every receiver must be within the Euclidean range of at least one active transmitter for a minimum of one day during the evaluated period (modeled using the Big-M method)[cite: 3].
• Capacity Limit: A maximum of 3 transmitters can be active on any single day[cite: 2, 3].
• Cost Minimization: Total cost optimization based on varied daily operation costs for 8 distinct transmitters (T1-T8)[cite: 2].

How to Run

To run these models, an installed AMPL environment configured with the Gurobi solver is required.

1. Clone this repository to your local machine.
2. Open your AMPL IDE or command-line interface.
3. Load the chosen model and its corresponding data file. For Project 1:

   model AleksandraSyskaZ1.mod;
   data AleksandraSyskaZ1.dat;
   option solver gurobi;
   solve;