The assignment problem is a classic problem in linear program. If, for example, you have n jobs that need to be manufactured during the upcoming shift (in a manufacturing plant) and you have m machines to produce these tasks, then you want to assign the jobs to machines in an optimal way. In this say you might want to reduce the manufacturing costs incurred, hence you want to find the cost optimal production plan. The constraint, in this example, is that each machine can only fulfill one job during the upcoming shift. All jobs needs to be scheduled, i.e. assigned to a machine.

The problem can be stated in a mathematical model. Below the problem is stated for a case where there are 3 jobs and 3 machines. The cost of producing job 1 on machine 1 USD but 2 USD when producing it on machine 2. Job 2 costs 2 USD on machine 1 and 3 USD on machine 2. Job 3 costs 5 USD on machine 1 and 1 USD on machine 2. Machine 3 can perform job 1 for 2 USD and jobs 2 and 3 for 3 USD respectively.

The mathematical model for this looks as follows:

We can model and solve this problem with the lpSolve package in R, a package for linear programming (for continous and integer problems). The lp.assign function can do the job:

library(lpSolve)

# prepare the cost matrix
cost.mat <- rbind(c(1,2,3),
                     c(2,3,3),
                     c(5,1,3))

# model and solve with lp.assign
solution <- lp.assign(cost.mat=cost.mat,
                      direction="min")

lp.assign is a function specifically meant for solving the assignment problem. The assignment problem by definition is a problem where all decision variables are integer variables. We therefore do not need to specifically tell lp.assign that the decision variables must be considered as integer variables.

Let us see the minimal costs that we must face during the upcoming shift:

solution

## Success: the objective function is 5

Let us see the cost minimal production plan for the upcoming shift:

solution$solution

##      [,1] [,2] [,3]
## [1,]    1    0    0
## [2,]    0    0    1
## [3,]    0    1    0

The transportation problem is another classical problem. You can see me solving it in R – here: Solving Bronson’s transport problem with lpSolve, using lp.transport.

Linnart Felkl

Data scientist focusing on simulation, optimization and modeling in R, SQL, VBA and Python