Assignment as a MIP problem

The previous section showed how to solve an assignment problem using the min cost flow solver. This section shows how to solve the same problem using the more general mixed integer programming (MIP) solver. Min cost flow is faster than MIP for this particular problem. On the other hand, MIP can solve a larger class of problems than min cost flow.

MIP solution to the assignment problem

The basic idea behind solving the assignment problem as a MIP problem is to assign integer variables to the edges in the graph for the problem. The value of each variable in a solution is the flow across the corresponding edge. For an edge between a given worker and task, the value of the variable is 1 if the worker is assigned to the task, and 0 otherwise.

The following sections describe how to set up and solve an assignment problem as a mixed integer programming problem.

Create the solver

The following code creates the MIP solver.

from ortools.linear_solver import pywraplp

def main():
  """Solving Assignment Problem with MIP"""
  # Instantiate a mixed-integer solver.
  solver = pywraplp.Solver('SolveAssignmentProblemMIP',
                           pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)

Create the data

The following code sets up the data for the problem.

  cost = [[90, 76, 75, 70],
          [35, 85, 55, 65],
          [125, 95, 90, 105],
          [45, 110, 95, 115],
          [60, 105, 80, 75],
          [45, 65, 110, 95]]

  team1 = [0, 2, 4]
  team2 = [1, 3, 5]
  team_max = 2
The array cost is the cost matrix.

Create the variables

The following code creates binary integer variables for the problem.

  x = {}

  for i in range(num_workers):
    for j in range(num_tasks):
      x[i, j] = solver.BoolVar('x[%i,%i]' % (i, j))
There is one variable for each pair of a worker and task. Note that the workers are numbered 0 — 5, while the tasks are numbered 0 — 3, unlike in the original example, in which all nodes had to be numbered differently, as required by the min cost flow solver.

Create the objective function

The following code creates the objective function for the problem.

  solver.Minimize(solver.Sum([cost[i][j] * x[i,j] for i in range(num_workers)
                                                  for j in range(num_tasks)]))
The value of the objective function is the total cost over all variables that are assigned the value 1 by the solver.

Create the constraints

The following code creates the constraints for the problem.


  # Each worker is assigned to at most 1 task.

  for i in range(num_workers):
    solver.Add(solver.Sum([x[i, j] for j in range(num_tasks)]) <= 1)

  # Each task is assigned to exactly one worker.

  for j in range(num_tasks):
    solver.Add(solver.Sum([x[i, j] for i in range(num_workers)]) == 1)

  # Each team takes on two tasks.

  solver.Add(solver.Sum([x[i, j] for i in team1 for j in range(num_tasks)]) <= team_max)
  solver.Add(solver.Sum([x[i, j] for i in team2 for j in range(num_tasks)]) <= team_max)

Invoke the solver

The following code invokes the solver for the problem.

  sol = solver.Solve()

  print('Total cost = ', solver.Objective().Value())
  print()
  for i in range(num_workers):
    for j in range(num_tasks):
      if x[i, j].solution_value() > 0:
        print('Worker %d assigned to task %d.  Cost = %d' % (
              i,
              j,
              cost[i][j]))

  print()
  print("Time = ", solver.WallTime(), " milliseconds")

The command

print("Time = ", solver.WallTime(), " milliseconds")
displays the time the program takes to run.

Here is the output of the program. The solution is the same as the one obtained by the min cost flow solver (except for the minor differences in numbering of workers and costs).

Minimum cost assignment:  250.0

Worker 0 assigned to task 2.  Cost = 75
Worker 1 assigned to task 0.  Cost = 35
Worker 4 assigned to task 3.  Cost = 75
Worker 5 assigned to task 1.  Cost = 65

Time =  6  milliseconds
As you can see, the min cost flow solver is about 20 times faster than the MIP solver for this particular problem — 0.00031 seconds versus 0.006 seconds. So you are definitely better off choosing the min cost flow solver in this case.

In general, if you can write your problem as a min cost flow problem, the min cost flow solver will be faster than either the MIP or CP solvers.

The entire program

Here is the entire code for the program.

from __future__ import print_function
from ortools.linear_solver import pywraplp

def main():
  """Solving Assignment Problem with MIP"""
  # Instantiate a mixed-integer solver.
  solver = pywraplp.Solver('SolveAssignmentProblemMIP',
                           pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)
  cost = [[90, 76, 75, 70],
          [35, 85, 55, 65],
          [125, 95, 90, 105],
          [45, 110, 95, 115],
          [60, 105, 80, 75],
          [45, 65, 110, 95]]

  team1 = [0, 2, 4]
  team2 = [1, 3, 5]
  team_max = 2

  num_workers = len(cost)
  num_tasks = len(cost[1])
  x = {}

  for i in range(num_workers):
    for j in range(num_tasks):
      x[i, j] = solver.BoolVar('x[%i,%i]' % (i, j))

  # Objective
  solver.Minimize(solver.Sum([cost[i][j] * x[i,j] for i in range(num_workers)
                                                  for j in range(num_tasks)]))

  # Constraints

  # Each worker is assigned to at most 1 task.

  for i in range(num_workers):
    solver.Add(solver.Sum([x[i, j] for j in range(num_tasks)]) <= 1)

  # Each task is assigned to exactly one worker.

  for j in range(num_tasks):
    solver.Add(solver.Sum([x[i, j] for i in range(num_workers)]) == 1)

  # Each team takes on two tasks.

  solver.Add(solver.Sum([x[i, j] for i in team1 for j in range(num_tasks)]) <= team_max)
  solver.Add(solver.Sum([x[i, j] for i in team2 for j in range(num_tasks)]) <= team_max)
  sol = solver.Solve()

  print('Total cost = ', solver.Objective().Value())
  print()
  for i in range(num_workers):
    for j in range(num_tasks):
      if x[i, j].solution_value() > 0:
        print('Worker %d assigned to task %d.  Cost = %d' % (
              i,
              j,
              cost[i][j]))

  print()
  print("Time = ", solver.WallTime(), " milliseconds")
if __name__ == '__main__':
  main()

Enviar comentarios sobre…