Problem
We’d like to optimize the delivery of loads across a network using a fleet of ships. Assume there is a set of $\mathcal{S}$ ships that need to deliver the set of $\mathcal{L}$ loads in a single day. Let the profit of moving load $j ∈ \mathcal{L}$ with ship $i \in \mathcal{S}$ be given by $w_{ij}$.
- The ship can also chose to not move a load at all (and stay put) at $0$ profit.
- Assume we can only assign a ship to one load per day
- A load may be taken by at most one ship
- Not all loads necessarily need to be moved.
I need to make a model for optimizing profit by formulating the assignment problem for a single day as an integer program and a continuous LP version of it.
Here is my take:
We can model this problem as in a weighted bipartite graph, a matching of a given size, in which the sum of weights of the edges is maximum. Each edge $(i, j)$, where $i$ is in $\mathcal{S}$ and $j$ is in $\mathcal{L}$, has a profit $w_{ij}$. For each edge $(i, j)$ we have a variable $x_{ij}$. The variable is $1$ if the edge is contained in the matching and $0$ otherwise, so we set the domain constraints:
$$ x_{ij} = \{0, 1\} \quad \text{for} \quad i, j \in \mathcal{S},\mathcal{L} $$
The total weight of the matching is
$$ \sum_{(i,j) \in \mathcal{S} \times \mathcal{L}} x_{ij} w_{ij} $$
The goal is to find a perfect matching that maximizes the above objective function. To guarantee that the variables represent a perfect matching, we add constraints saying that each vertex is adjacent to exactly one edge in the matching, i.e,
$$ \sum_{j \in \mathcal{L}} x_{ij} = 1 \quad \text{for} \quad i \in \mathcal{S}\\ \sum_{i \in \mathcal{S}} x_{ij} = 1 \quad \text{for} \quad j \in \mathcal{L} $$
Therefore, the problem can be formulated as –
$$ \begin{eqnarray} \text{maximize} & \sum_{(i,j) \in \mathcal{S} \times \mathcal{L}} x_{ij}w_{ij}\\ \text{subject to} \\ & \sum_{j \in \mathcal{L}} x_{ij} = 1 \quad \text{for} \quad i \in \mathcal{S}\notag \\ & \sum_{i \in \mathcal{S}} x_{ij} = 1 \quad \text{for} \quad j \in \mathcal{L}\notag \\ \text{where,} \qquad & x_{ij} = \{0,1\} \quad \text{for} \quad i,j \in \mathcal{S},\mathcal{L} \notag \end{eqnarray} $$
LP version:
We can solve it without the integrality constraints, using standard methods for solving continuous linear programs. We can just use this constraint instead –
$$ \begin{eqnarray} 0 \leq x_{ij} \leq 1 \quad \text{for} \quad i,j \in \mathcal{S},\mathcal{L} \end{eqnarray} $$
Am I doing it right?
