Converting job assignment problem into a 0-1 linear programming problem

binary-programminglinear programmingword problem

There are $n$ people who need to be assigned to execute $n$ jobs, one person per job. (That is, each person is assigned to exactly one job and each job is assigned to exactly one person.) The cost that would accrue if the $i$-th person is assigned to the $j$-th job is a known quantity $C[i, j]$ for each pair $i, j = 1, \dots , n$. The problem is to assign the people to the jobs to minimize the total cost of the assignment. Express the assignment problem as a $0$–$1$ linear programming problem.

Let $M$ be an $n \times n$ matrix where the value at $M_{ij}$ indicates the cost of assigning person $i$ to job $j$, or $C[i, j]$.

Let $x$ be an $n \times n$ matrix where the value at $x_{ij}$ denotes whether person $i$ was assigned to job $j$. If the assignment occurred, $x_{ij}$ is 1; otherwise, it is 0.

I've managed to come up with these definitions, but unfortunately I'm not sure how to proceed with the problem. The canonical form of a linear programming problem is as follows:

maximize $c^Tx$, subject to $Ax\leq b$, and $x\geq 0$

However, it seems the goal of this problem is to minimize, not to maximize. How do I convert this minimization problem into a maximization problem? Furthermore, how would the constraints be defined by this sort of problem? Are my definitions adequate for the problem?

Best Answer

The required LP is

$\begin{align} \min & \sum_{i=1}^n\sum_{j=1}^n M_{ij} x_{ij} \\ & \sum_{i=1}^n x_{ij} = 1 \quad \forall j \in \{1,\dots, n\} \tag{each job is assigned to exactly one person} \\ & \sum_{j=1}^n x_{ij} = 1 \quad \forall i \in \{1,\dots, n\} \tag{each person is assigned to exactly one job} \\ & x_{ij} \in \{0,1\} \quad \forall i,j \in \{1, \dots, n\} \end{align}$

To understand the objective function, for each job $j$, there exist unique $i_0 \in \{1, \dots, n\}$ such that $x_{ij} = \begin{cases} 1 &\text{if } i = i_0 \\ 0 &\text{otherwise,} \end{cases}$ so the cost for the $j$-th job is $M_{i_0j} = \sum \limits_{i=1}^n M_{ij}$. Sum the previous equality over $j \in \{1,\dots,n\}$ to get the above double sum.

How do I convert this minimization problem into a maximization problem?

To minimize a quantity is equivalent to maximizing its additive inverse.

Furthermore, how would the constraints be defined by this sort of problem?

Use the standard technique of transforming an equality constraint to a set of two inequality constraints:

$$x = a \iff \begin{cases} - x &\le -a \\ x &\le a. \end{cases}$$

Are my definitions adequate for the problem?

They are more than enough. You don't need to define $M$, since you already have $C$, which represents the costs.

To write the LP is a more concise matrix form, denote

$\mathbf{1} \in \{0,1\}^n$ the $n \times 1$ vector filled with $1$.
$C = (C[i,j])_{ij} = (c_{ij})_{ij} \in \mathbb{R}^{n \times n}$: the matrix $C$ is defined by $C[i,j]$ as the $(i,j)$-th element, so that
$(C^T)_{ij} = c_{ji}$: the $(i,j)$-th element of $C^T$ is the $(j,i)$-th element of $C$.
$X = (x_{ij})_{ij} \in \{0,1\}^{n \times n}$

Remarks: I prefer using capital letters for matrices, and use small letters with a subscript to denote the corresponding matrix elements.

Note that the cost function is \begin{align} \sum_{i=1}^n \sum_{j=1}^n C[i,j] x_{ij} &= \sum_{i=1}^n \sum_{j=1}^n (C^T)_{ji} x_{ij} \tag{take transpose of $C$} \\ &= \sum_{j=1}^n \left( \sum_{i=1}^n (C^T)_{ji} x_{ij} \right) \tag{change order of summation} \\ &= \sum_{j=1}^n \left( C^T X \right)_{jj} \tag{defintion of matrix product} \\ &= \mathop{\mathrm{tr}}(C^T X). \tag{definition of trace} \end{align} $\sum\limits_{i=1}^n x_{ij} = 1$ can be rewritten as $\mathbf{1}^T X = \mathbf{1}^T$; $\sum\limits_{j=1}^n x_{ij} = 1$ can be rewritten as $X \mathbf{1} = \mathbf{1}$. Hence the LP in matrix form is $\min\{\mathop{\mathrm{tr}}(C^T X) \mid \mathbf{1}^T X = \mathbf{1}^T, X \mathbf{1} = \mathbf{1}, X \in \{0,1\}^{n \times n} \}$

Related Solutions

[Math] Linear programming vs. Integer programming

Your problem seems to be a knapsack problem: it is NP-hard. As you noticed, it can be formulated as a linear program with binary constraints; most linear programming software packages also allow integral constraints, but those constraints can make them significantly slower.

The bipartite matching problem can also be formulated as a linear program with binary constraints, but it turns out that its relaxation, i.e., the same problem with the binary constraints $x_i \in \{0,1\}$ replaced by $0 \leqslant x_i \leqslant 1$, has integral solutions: the two problems are actually equivalent.

But this is the exception, rather than the rule: in general, binary or integral constraints do make the problem harder, and relaxing them only gives an upper (or lower) bound on the objective.

[Math] Project scheduling using linear programming

Here's how I've tackled this part of a problem. Define a job as the following type of object (using electrical as an example):

{title: 'electrical', duration: 2, precedents: [3, 5]}

Then create the precedent constraints by looping through each job and precedent. (Pesudo code)

for j in jobs:
  for p in precedents:
     add_constraint(start_time_of_j >= start_time_of_p + duration_of_p)

Then create a start_time and an end_time variable, and setting them before and after all jobs. (This effectively makes start_time the minimum of all start_times and end_time the maximum of all start_times plus their respective durations.)

for j in jobs:
  add_constraint(start_time <= start_time_of_j)
  add_constraint(end_time >= start_time_of_j + duration_of_j)

Lastly, set your objective function to minimize total time.

set_objective(minimize, end_time - start_time)

I found it helped to add the following constraint too

add_constraint(start_time == 0)

Best Answer

Related Solutions

[Math] Linear programming vs. Integer programming

[Math] Project scheduling using linear programming

Related Question