2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ In a perfect matching, every load goes on exactly one ship and every ship carries exactly one load. Compare that to your problem statement. $\endgroup$
    – prubin
    Apr 8 at 21:43
  • $\begingroup$ @pubin I see, is it an "unbalanced" version of the assignment problem? In that case how should I formulate it? Because the number of vertices on the either side of the bipartite graph will not be the same. $\endgroup$
    – ramgorur
    Apr 8 at 22:03

1 Answer 1

2
$\begingroup$

You can treat this as a generalized assignment problem, assigning loads to ships, with real ships having capacity one load each and with a dummy "ship" with capacity $\vert \mathcal{L} \vert$ representing loads that are not moved.

$\endgroup$
2
  • $\begingroup$ I think it should be something like $|\mathcal{L} - \mathcal{S}|$ extra imaginary "ships" if $\mathcal{S} < \mathcal{L}$ (and vise-versa), right? But how do I express this idea in a mathematical formula? $\endgroup$
    – ramgorur
    Apr 9 at 0:24
  • $\begingroup$ I was assuming an inequality constraint for the load allocated to the dummy "ship" and did not give the minimum workable capacity. The dummy "ship" needs a capacity of at least $max\lbrace 0, \vert \mathcal{L}\vert - \vert \mathcal{S}\vert\rbrace.$ If some loads have negative weights (you did not specify the sign of $w$), then you may need a larger capacity (to avoid forcing ships to take negative weight loads). Setting the capacity to $\vert \mathcal{L} \vert$ is a safe choice (assuming an inequality constraint on its load). $\endgroup$
    – prubin
    Apr 9 at 16:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.