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.

Contents

• Julia Optimization Study
  • Assignment Problem
  • Bin Packing Problem
  • Cutting Stock Problem
  • Facility Location Problem
  • Knapsack Problem
  • Set Partitioning Problem
  • Travelling Salesman Problem
  • Dial-a-Ride Problem

Assignment Problem

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

Objective Function:

$$ \min \left( \sum_{i=1}^{n}\sum_{j=1}^{n} c_{ij}x_{ij} \right) $$

s.t.:

$$ \sum_{i=1}^{n} x_{ij} \, = \,1 \qquad i \, \in \, n $$

$$ \sum_{i=1}^{n} x_{ij} \, = \, 1 \qquad j \,\in \, n $$

$$ x_{ij} \, \in \, \{ 0, 1 \} $$

Bin Packing Problem

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$

Objective Function:

$$ \min \left( \sum_{i=1}^{n}y_{i} \right) $$

s.t.:

$$ \sum_{i=1}^{n} x_{ij} \, \geq \, b_{j} \qquad j \, \in \, m $$

$$ \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

Objective Function:

$$ \min \left( \sum_{i=1}^{I}f_{i}y_{i} + \sum_{i=1}^{I}\sum_{j=1}^{J}c_{ij}x_{ij}\right) $$

s.t.:

$$ \sum_{i=1}^{I} x_{ij} \, = \, 1 \qquad j \, \in \, J $$

$$ \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

Objective Function:

$$ \max \left( \sum_{i=1}^{n}v_{i}x_{i} \right) $$

s.t.:

$$ \sum_{i=1}^{n} w_{i}x_{i} \, \leq \, W $$

$$ x_{i} \, \in \, \{ 0, 1 \} $$

Set Partitioning Problem

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

Objective Function:

$$ \min \left( \sum_{i=1}^{n} \sum_{\substack{j=1 \\ i \neq j}}^{n} c_{ij}x_{ij} \right) $$

s.t.:

$$ \sum_{i=1}^{n} x_{ij} \, = \, 1 \qquad j \, \in \, n \, , \, j \, \neq \, i $$

$$ \sum_{j=1}^{n} x_{ij} \, = \, 1 \qquad i \, \in \, n \, , \, i \, \neq \, j $$

$$ \sum_{i \, \in \, S}\sum_{j \, \in \, S} x_{ij} \, \leq \, |S| - 1 \qquad S \, \subset \, N \, , \, 2 \, \leq \,|S| - 1| \, \leq \, \left \lfloor \frac{n}{2} \right \rfloor$$

$$ x_{ij} \, \in \, \{ 0, 1 \} $$

• Mixed Integer Programming - Flow Variable

Formulation

Data:

$n$ is the number of vertices
$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
$f_{ij}$ assumes the amount of flow from vertex $i$ to $j$

Objective Function:

$$ \min \left( \sum_{i=1}^{n} \sum_{\substack{j=1 \\ i \neq j}}^{n} c_{ij}x_{ij} \right) $$

s.t.:

$$ \sum_{i=1}^{n} x_{ij} \, = \, 1 \qquad j \, \in \, n \, , \, j \, \neq \, i $$

$$ \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.

• Mixed Integer Programming

Formulation

The formulation is based on Cordeau and Laporte (2007)

Data:

$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$

Objective Function:

$$ \min \sum_{k \in K} \sum_{i \in V} \sum_{j \in V} c_{ij}x^{k}_{ij} $$

s.t.:

$$ \sum_{k \in K} \sum_{j \in V} x_{ij}^{k} \, = \, 1 \qquad i \, \in \,P $$

$$ \sum_{j \in V} x_{m_o, j}^{k} \, = \, 1 \qquad k \, \in \,K $$

$$ \sum_{j \in V} x_{i, m_e}^{k} \, = \, 1 \qquad k \, \in \,K $$

$$ \sum_{j \in V} x_{ij}^{k} \, - \, \sum_{j \in V} x_{n+i,j}^{k} \, = \, 0 \qquad i \, \in \,P, k \, \in \, K $$

$$ \sum_{j \in V} x_{ji}^{k} \, - \, \sum_{j \in V} x_{ij}^{k} \, = \, 0 \qquad i \, \in \,P \, \cup \, D, k \, \in \, K $$

$$u_{j}^{k} \geq (u_{i}^{k} + s_{i} + t_{ij}) - M(1 - x_{ij}^{k}) \qquad i \, \in \, V, j \, \in \, V, \, k \, \in \, K$$

$$w_{j}^{k} \geq (w_{i}^{k} + q_{j}) - M'(1 - x_{ij}^{k}) \qquad i \, \in \, V, j \, \in \, V, \, k \, \in \, K$$

$$r_{i}^{k} \geq u_{i+n}^{k} - (u_{i}^{k} + s_i) \qquad i \, \in \, P, \, k \, \in \, K$$

$$u_{m_e}^{k} - u_{m_o}^{k} \leq T \qquad k \, \in \, K$$

$$e_i \leq u_{i}^{k} \leq l_i \qquad i \, \in \, V, \, k \, \in \, K$$

$$u_{i+n}^{k} \geq u_{i}^{k} \qquad i \, \in \, P, \, k \, \in \, K$$

$$t_{i,i+n} \leq r_{i}^{k} \leq L \qquad i \, \in \, P, \, k \, \in \, K$$

$$\max\{0, q_i \} \leq w_{i}^{k} \leq \min \{C, C + q_i \} \qquad i \, \in \, V, \, k \, \in \, K$$

$$ x_{ij}^{k} \, \in \, \{ 0, 1 \} \qquad i \, \in \, V, j \, \in \, V, \, k \, \in \, K $$

$$ u_{i}^{k} \, \geq \, 0 \qquad i \, \in \, V, \, k \, \in \, K $$

$$ w_{i}^{k} \, \geq \, 0 \qquad i \, \in \, V, \, k \, \in \, K $$

$$ r_{i}^{k} \, \geq \, 0 \qquad i \, \in \, P, \, k \, \in \, K $$