It is a study guide for people who are interested in learning Mixed Integer Programming. The repository contains a set of classical optimization problems, and each problem has its own mathematical formulation and implementation using Julia language with JuMP framework.
Julia
Julia Optimization Study
It is a study guide for people who are interested in learning Mixed Integer Programming. The repository contains a set of classical optimization problems, and each problem has it is a mathematical formulation and implementation using Julia language with JuMP framework.
Given a set of tasks, a set of agents, and the costs of each agent to perform each task. The problem consists of assigning agents to tasks such that the total cost is minimized.
Formulation
Data:
$n$ is the number of agents and tasks $c_{ij}$ is the cost of agent $i$ perform task $j$
Decision Variables:
$x_{ij}$ assumes value $1$ if task $j$ is assigned to agent $i$, $0$ otherwise
The problem is packing a set of items into a minimum number of bins such that the total weight does not exceed the bin's capacities.
Formulation
Data:
$n$ is the number of items $W$ is the capacity of the bins $w_{j}$ is the weight of item $j$
Decision Variables
$y_{i}$ assumes value $1$ if the bin $i$ is used, $0$ otherwise $x_{ij}$ assumes value $1$ if the item $j$ is assigned to bin $i$, $0$ otherwise
Objective Function:
$$ \min \left( \sum_{i=1}^{n}y_{i} \right) $$
s.t.:
$$ \sum_{i=1}^{n} x_{ij} \, = \, 1 \qquad i \, \in \, n $$
$$ \sum_{j=1}^{n} w_{j} x_{ij} \, \leq \, W y_{i} \qquad i \, \in \, n $$
$$ x_{ij} \,\in \, \{ 0, 1 \} $$
$$ y_{i} \,\in \, \{ 0, 1 \} $$
Cutting Stock Problem
Given a length and number of original rods, and given a set of lengths and demands of new smaller rods. Determine the minimum number of original rods that must be cut to generate all demanded new rods.
Formulation
Data:
$L$ is the size of each original bar $n$ is the upper bound of original rods $m$ is the number of new smaller rods $l_{i}$ is the size of each new smaller rod $l_{1}$, $l_{2}$, ..., $l_{m}$ $b_{i}$ is the demand of each new smaller rod $b_{1}$, $b_{2}$, ..., $b_{m}$
Decision Variables
$y_{i}$ assumes value $1$ if the original rod $i$ is used, $0$ otherwise $x_{ij}$ assumes the number of times that a new rod $j$ is cut in the original rod $i$
$$ \sum_{j=1}^{m} l_{j} x_{ij} \, \leq \, Ly_{i} \qquad i \, \in \, n $$
$$ x_{ij} \, \in \, \mathbb{Z} $$
$$ y_{i} \,\in \, \{ 0, 1 \} $$
Facility Location Problem
Given a set of clients, a set of potential facilities sites, the costs of building each facility, and the costs of assign each client to each possible facility. The problem consists of deciding which places to build facilities to supply the client's demands such that total costs are minimized.
Formulation
Data:
$I$ is the number of potential facilities $J$ is the number of clients $f_{i}$ is the fixed cost of open facility $i$ $c_{ij}$ is the fixed cost of assign client $j$ to facilty $i$ $q_{j}$ is the themand of client $j$ $Q_{i}$ is the capacity of facility $i$
Decision Variables
$y_{i}$ assumes value $1$ if facility $i$ is opened, $0$ otherwise $x_{ij}$ assumes value $1$ if client $j$ is assigned to facility $i$, $0$ otherwise
$$ \sum_{j=1}^{J} q_{j}x_{ij} \, \leq\, Q_{i}y_{i} \qquad i \, \in \, I $$
$$ y_{i} \, \in \, \{ 0, 1 \} $$
$$ x_{ij} \, \in \, \{ 0, 1 \} $$
Knapsack Problem
Given a set of items with different values and weights, determine which items to include in a collection that total weight of items is less than or equal to a given limit, and the total value is higher as possible.
Formulation
Data:
$n$ is the number of items $v_{i}$ is the value of item $i$ $w_{i}$ is the weight of item $i$ $W$ is the capacity of the knapsack
Decision Variables
$x_{i}$ assumes value $1$ if the item $i$ is in knapsack, $0$ otherwise
Given a collection of subsets derived from an original set, the problem is to find a partition of the initial set. In other words, the aim is to select a new set of subsets such that the intersection of every subset is empty, and the union of all subsets is equal to the original set.
Formulation
Data:
$S$ is the original set $n$ is the number of subsets $R_{i}$ is a subset of $S$ that has element $i$
Decision Variables
$y_{j}$ assumes value $1$ if the subset $j$ is part of partitioning, $0$ otherwise
Objective Function:
$$ \min \left( \sum_{j=1}^{n}y_{j} \right) $$
s.t.:
$$ \sum_{j \, \in \, R_{i}} y_{j} \, = \, 1 \qquad i \, \in \, S $$
$$ y_{i} \, \in \, \{ 0, 1 \} $$
Travelling Salesman Problem
Given a set of cities and the distance between every pair of cities, the problem is to find the shortest possible route that visits every city exactly once and returns to the starting point.
Mixed Integer Programming - Subtour formulation
Formulation
Data:
$n$ is the number of vertices $N$ is the set of vertices $S$ is a subtour $c_{ij}$ is the cost of travel from vertex $i$ to vertex $j$
Decision Variables
$x_{ij}$ assumes value $1$ if arc from $i$ to $j$ is used, $0$ otherwise
$$ \sum_{j=1}^{n} x_{ij} \, = \, 1 \qquad i \, \in \, n \, , \, i \, \neq \, j $$
$$ \sum_{\substack{j=1 \\ i \neq j}}^{n} f_{ji} - \sum_{\substack{j=1 \\ i \neq j}}^{n} f_{ij} \, = \, 1 \qquad i \, \in \, n \, \backslash \{1\} $$
$$f_{ij} \, \leq \, (n - 1)x_{ij} \qquad i \, \in \, n \, , \, j \, \in \, n $$
$$ x_{ij} \, \in \, \{ 0, 1 \} $$
$$ f_{ij} \, \in \, \mathbb{N} $$
Dial-a-Ride Problem
This problem consists of designing least-cost routes to serve pickup-and-delivery requests, while meeting capacity, time window, maximum route duration, and maximum ride time constraints.
$n$ is the number of requests $v$ is the number of vehicles $P = {1, \ldots, n}$ is the set of pickup nodes $D = {n+1, \ldots, 2n}$ is the set of delivery nodes $m_{o} = 2n + 1$ is the initial depot node $m_{e} = 2n + 2$ is the ending depot node $V = P \cup D \cup \{m_{o}\} \cup \{m_{e}\}$ is the set of all nodes in the network $K = {1, \ldots, v}$ is the set of vehicles $C \in \mathbb{N_+}$ is the maximum capacity of the vehicles $L \in \mathbb{R_{+}}$ is the maximum ride of the request $T \in \mathbb{R_{+}}$ is the maximum duration of the routes $q_{i} \in \mathbb{N}$ is the demand of node $i \in V$ $e_{i} \in \mathbb{R_{+}}$ is the earliest time to visit the node $i \in V$ $l_{i} \in \mathbb{R_{+}}$ is the latest time to visit the node $i \in V$ $s_{i} \in \mathbb{R_{+}}$ is the service time to visit the node $i \in V$ $t_{ij} \in \mathbb{R_{+}}$ is the travel time to go from $i \in V$ to $j \in V$ $c_{ij} \in \mathbb{R_{+}}$ is the travel cost to go from $i \in V$ to $j \in V$
Decision Variables
$x_{ij}^{k} \in \{0, 1\}$ assumes value $1$ if arc from $i$ to $j$ is used by vehicle $k$, $0$ otherwise $u_{i}^{k} \in \mathbb{R_{+}}$ is the visit time of node $i$ by vehicle $k$ $w_{i}^{k} \in \mathbb{R_{+}}$ is the accumulalted demand up to node $i$ on the vehicle $k$$r_{i}^{k} \in \mathbb{R_{+}}$ is the ride time of request $i$ by vehicle $k$