Solving an Assignment Problem

This section presents an example that shows how to solve an assignment problem using both the MIP solver and the CP-SAT solver.

Example

In the example there are five workers (numbered 0-4) and four tasks (numbered 0-3). Note that there is one more worker than in the example in the Overview.

The costs of assigning workers to tasks are shown in the following table.

0 1 2 3
0 90 80 75 70
1 35 85 55 65
2 125 95 90 95
3 45 110 95 115
4 50 100 90 100

The problem is to assign each worker to at most one task, with no two workers performing the same task, while minimizing the total cost. Since there are more workers than tasks, one worker will not be assigned a task.

MIP solution

The following sections describe how to solve the problem using the MIP solver.

Import the libraries

The following code imports the required libraries.

Python

from ortools.linear_solver import pywraplp

C++

#include <vector>

#include "ortools/base/logging.h"
#include "ortools/linear_solver/linear_solver.h"

Java

import com.google.ortools.Loader;
import com.google.ortools.linearsolver.MPConstraint;
import com.google.ortools.linearsolver.MPObjective;
import com.google.ortools.linearsolver.MPSolver;
import com.google.ortools.linearsolver.MPVariable;

C#

using System;
using Google.OrTools.LinearSolver;

Declare the MIP solver

The following code declares the MIP solver.

Python

# Create the mip solver with the SCIP backend.
solver = pywraplp.Solver.CreateSolver('SCIP')

C++

// Create the mip solver with the SCIP backend.
MPSolver solver("assignment_mip", MPSolver::SCIP_MIXED_INTEGER_PROGRAMMING);

Java

// Create the linear solver with the SCIP backend.
MPSolver solver = MPSolver.createSolver("SCIP");
if (solver == null) {
  System.out.println("Could not create solver SCIP");
  return;
}

C#

Solver solver = Solver.CreateSolver("SCIP");

Create the data

The following code creates the data for the problem.

Python

costs = [
    [90, 80, 75, 70],
    [35, 85, 55, 65],
    [125, 95, 90, 95],
    [45, 110, 95, 115],
    [50, 100, 90, 100],
]
num_workers = len(costs)
num_tasks = len(costs[0])

C++

const std::vector<std::vector<double>> costs{
    {90, 80, 75, 70},   {35, 85, 55, 65},   {125, 95, 90, 95},
    {45, 110, 95, 115}, {50, 100, 90, 100},
};
const int num_workers = costs.size();
const int num_tasks = costs[0].size();

Java

double[][] costs = {
    {90, 80, 75, 70},
    {35, 85, 55, 65},
    {125, 95, 90, 95},
    {45, 110, 95, 115},
    {50, 100, 90, 100},
};
int numWorkers = costs.length;
int numTasks = costs[0].length;

C#

int[,] costs = {
  {90, 80, 75, 70},
  {35, 85, 55, 65},
  {125, 95, 90, 95},
  {45, 110, 95, 115},
  {50, 100, 90, 100},
};
int numWorkers = costs.GetLength(0);
int numTasks = costs.GetLength(1);

The costs array corresponds to the table of costs for assigning workers to tasks, shown above.

Create the variables

The following code creates binary integer variables for the problem.

Python

# x[i, j] is an array of 0-1 variables, which will be 1
# if worker i is assigned to task j.
x = {}
for i in range(num_workers):
    for j in range(num_tasks):
        x[i, j] = solver.IntVar(0, 1, '')

C++

// x[i][j] is an array of 0-1 variables, which will be 1
// if worker i is assigned to task j.
std::vector<std::vector<const MPVariable*>> x(
    num_workers, std::vector<const MPVariable*>(num_tasks));
for (int i = 0; i < num_workers; ++i) {
  for (int j = 0; j < num_tasks; ++j) {
    x[i][j] = solver.MakeIntVar(0, 1, "");
  }
}

Java

// x[i][j] is an array of 0-1 variables, which will be 1
// if worker i is assigned to task j.
MPVariable[][] x = new MPVariable[numWorkers][numTasks];
for (int i = 0; i < numWorkers; ++i) {
  for (int j = 0; j < numTasks; ++j) {
    x[i][j] = solver.makeIntVar(0, 1, "");
  }
}

C#

// x[i, j] is an array of 0-1 variables, which will be 1
// if worker i is assigned to task j.
Variable[,] x = new Variable[numWorkers, numTasks];
for (int i = 0; i < numWorkers; ++i)
{
  for (int j = 0; j < numTasks; ++j)
  {
    x[i, j] = solver.MakeIntVar(0, 1, $"worker_{i}_task_{j}");
  }
}

Create the constraints

The following code creates the constraints for the problem.

Python

# 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)

C++

// Each worker is assigned to at most one task.
for (int i = 0; i < num_workers; ++i) {
  LinearExpr worker_sum;
  for (int j = 0; j < num_tasks; ++j) {
    worker_sum += x[i][j];
  }
  solver.MakeRowConstraint(worker_sum <= 1.0);
}
// Each task is assigned to exactly one worker.
for (int j = 0; j < num_tasks; ++j) {
  LinearExpr task_sum;
  for (int i = 0; i < num_workers; ++i) {
    task_sum += x[i][j];
  }
  solver.MakeRowConstraint(task_sum == 1.0);
}

Java

// Each worker is assigned to at most one task.
for (int i = 0; i < numWorkers; ++i) {
  MPConstraint constraint = solver.makeConstraint(0, 1, "");
  for (int j = 0; j < numTasks; ++j) {
    constraint.setCoefficient(x[i][j], 1);
  }
}
// Each task is assigned to exactly one worker.
for (int j = 0; j < numTasks; ++j) {
  MPConstraint constraint = solver.makeConstraint(1, 1, "");
  for (int i = 0; i < numWorkers; ++i) {
    constraint.setCoefficient(x[i][j], 1);
  }
}

C#

// Each worker is assigned to at most one task.
for (int i = 0; i < numWorkers; ++i)
{
  Constraint constraint = solver.MakeConstraint(0, 1, "");
  for (int j = 0; j < numTasks; ++j)
  {
    constraint.SetCoefficient(x[i, j], 1);
  }
}
// Each task is assigned to exactly one worker.
for (int j = 0; j < numTasks; ++j)
{
  Constraint constraint = solver.MakeConstraint(1, 1, "");
  for (int i = 0; i < numWorkers; ++i)
  {
    constraint.SetCoefficient(x[i, j], 1);
  }
}

Create the objective function

The following code creates the objective function for the problem.

Python

objective_terms = []
for i in range(num_workers):
    for j in range(num_tasks):
        objective_terms.append(costs[i][j] * x[i, j])
solver.Minimize(solver.Sum(objective_terms))

C++

MPObjective* const objective = solver.MutableObjective();
for (int i = 0; i < num_workers; ++i) {
  for (int j = 0; j < num_tasks; ++j) {
    objective->SetCoefficient(x[i][j], costs[i][j]);
  }
}
objective->SetMinimization();

Java

MPObjective objective = solver.objective();
for (int i = 0; i < numWorkers; ++i) {
  for (int j = 0; j < numTasks; ++j) {
    objective.setCoefficient(x[i][j], costs[i][j]);
  }
}
objective.setMinimization();

C#

Objective objective = solver.Objective();
for (int i = 0; i < numWorkers; ++i)
{
  for (int j = 0; j < numTasks; ++j)
  {
    objective.SetCoefficient(x[i, j], 1);
  }
}
objective.SetMinimization();

The value of the objective function is the total cost over all variables that are assigned the value 1 by the solver.

Invoke the solver

The following code invokes the solver.

Python

status = solver.Solve()

C++

const MPSolver::ResultStatus result_status = solver.Solve();

Java

MPSolver.ResultStatus resultStatus = solver.solve();

C#

Solver.ResultStatus resultStatus = solver.Solve();

The following code prints the solution to the problem.

Python

if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE:
    print('Total cost = ', solver.Objective().Value(), '\n')
    for i in range(num_workers):
        for j in range(num_tasks):
            # Test if x[i,j] is 1 (with tolerance for floating point arithmetic).
            if x[i, j].solution_value() > 0.5:
                print('Worker %d assigned to task %d.  Cost = %d' %
                      (i, j, costs[i][j]))

C++

// Check that the problem has a feasible solution.
if (result_status != MPSolver::OPTIMAL &
    result_status != MPSolver::FEASIBLE) {
  LOG(FATAL) << "No solution found.";
}

LOG(INFO) << "Total cost = " << objective->Value() << "\n\n";

for (int i = 0; i < num_workers; ++i) {
  for (int j = 0; j < num_tasks; ++j) {
    // Test if x[i][j] is 0 or 1 (with tolerance for floating point
    // arithmetic).
    if (x[i][j]->solution_value() > 0.5) {
      LOG(INFO) << "Worker " << i << " assigned to task " << j
                << ".  Cost = " << costs[i][j];
    }
  }
}

Java

// Check that the problem has a feasible solution.
if (resultStatus == MPSolver.ResultStatus.OPTIMAL
    || resultStatus == MPSolver.ResultStatus.FEASIBLE) {
  System.out.println("Total cost: " + objective.value() + "\n");
  for (int i = 0; i < numWorkers; ++i) {
    for (int j = 0; j < numTasks; ++j) {
      // Test if x[i][j] is 0 or 1 (with tolerance for floating point
      // arithmetic).
      if (x[i][j].solutionValue() > 0.5) {
        System.out.println(
            "Worker " + i + " assigned to task " + j + ".  Cost = " + costs[i][j]);
      }
    }
  }
} else {
  System.err.println("No solution found.");
}

C#

// Check that the problem has a feasible solution.
if (resultStatus == Solver.ResultStatus.OPTIMAL || resultStatus == Solver.ResultStatus.FEASIBLE)
{
  Console.WriteLine($"Total cost: {solver.Objective().Value()}\n");
  for (int i = 0; i < numWorkers; ++i)
  {
    for (int j = 0; j < numTasks; ++j)
    {
      // Test if x[i, j] is 0 or 1 (with tolerance for floating point
      // arithmetic).
      if (x[i, j].SolutionValue() > 0.5)
      {
        Console.WriteLine($"Worker {i} assigned to task {j}. Cost: {costs[i, j]}");
      }
    }
  }
} else {
  Console.WriteLine("No solution found.");
}

Here is the output of the program.

Total cost =  265.0

Worker 0 assigned to task 3.  Cost = 70
Worker 1 assigned to task 2.  Cost = 55
Worker 2 assigned to task 1.  Cost = 95
Worker 3 assigned to task 0.  Cost = 45

Complete programs

Here are the complete programs for the MIP solution.

Python

from ortools.linear_solver import pywraplp


def main():
    # Data
    costs = [
        [90, 80, 75, 70],
        [35, 85, 55, 65],
        [125, 95, 90, 95],
        [45, 110, 95, 115],
        [50, 100, 90, 100],
    ]
    num_workers = len(costs)
    num_tasks = len(costs[0])

    # Solver
    # Create the mip solver with the SCIP backend.
    solver = pywraplp.Solver.CreateSolver('SCIP')


    # Variables
    # x[i, j] is an array of 0-1 variables, which will be 1
    # if worker i is assigned to task j.
    x = {}
    for i in range(num_workers):
        for j in range(num_tasks):
            x[i, j] = solver.IntVar(0, 1, '')

    # 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)

    # Objective
    objective_terms = []
    for i in range(num_workers):
        for j in range(num_tasks):
            objective_terms.append(costs[i][j] * x[i, j])
    solver.Minimize(solver.Sum(objective_terms))

    # Solve
    status = solver.Solve()

    # Print solution.
    if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE:
        print('Total cost = ', solver.Objective().Value(), '\n')
        for i in range(num_workers):
            for j in range(num_tasks):
                # Test if x[i,j] is 1 (with tolerance for floating point arithmetic).
                if x[i, j].solution_value() > 0.5:
                    print('Worker %d assigned to task %d.  Cost = %d' %
                          (i, j, costs[i][j]))


if __name__ == '__main__':
    main()

C++

#include <vector>

#include "ortools/base/logging.h"
#include "ortools/linear_solver/linear_solver.h"

namespace operations_research {
void AssignmentMip() {
  // Data
  const std::vector<std::vector<double>> costs{
      {90, 80, 75, 70},   {35, 85, 55, 65},   {125, 95, 90, 95},
      {45, 110, 95, 115}, {50, 100, 90, 100},
  };
  const int num_workers = costs.size();
  const int num_tasks = costs[0].size();

  // Solver
  // Create the mip solver with the SCIP backend.
  MPSolver solver("assignment_mip", MPSolver::SCIP_MIXED_INTEGER_PROGRAMMING);

  // Variables
  // x[i][j] is an array of 0-1 variables, which will be 1
  // if worker i is assigned to task j.
  std::vector<std::vector<const MPVariable*>> x(
      num_workers, std::vector<const MPVariable*>(num_tasks));
  for (int i = 0; i < num_workers; ++i) {
    for (int j = 0; j < num_tasks; ++j) {
      x[i][j] = solver.MakeIntVar(0, 1, "");
    }
  }

  // Constraints
  // Each worker is assigned to at most one task.
  for (int i = 0; i < num_workers; ++i) {
    LinearExpr worker_sum;
    for (int j = 0; j < num_tasks; ++j) {
      worker_sum += x[i][j];
    }
    solver.MakeRowConstraint(worker_sum <= 1.0);
  }
  // Each task is assigned to exactly one worker.
  for (int j = 0; j < num_tasks; ++j) {
    LinearExpr task_sum;
    for (int i = 0; i < num_workers; ++i) {
      task_sum += x[i][j];
    }
    solver.MakeRowConstraint(task_sum == 1.0);
  }

  // Objective.
  MPObjective* const objective = solver.MutableObjective();
  for (int i = 0; i < num_workers; ++i) {
    for (int j = 0; j < num_tasks; ++j) {
      objective->SetCoefficient(x[i][j], costs[i][j]);
    }
  }
  objective->SetMinimization();

  // Solve
  const MPSolver::ResultStatus result_status = solver.Solve();

  // Print solution.
  // Check that the problem has a feasible solution.
  if (result_status != MPSolver::OPTIMAL &
      result_status != MPSolver::FEASIBLE) {
    LOG(FATAL) << "No solution found.";
  }

  LOG(INFO) << "Total cost = " << objective->Value() << "\n\n";

  for (int i = 0; i < num_workers; ++i) {
    for (int j = 0; j < num_tasks; ++j) {
      // Test if x[i][j] is 0 or 1 (with tolerance for floating point
      // arithmetic).
      if (x[i][j]->solution_value() > 0.5) {
        LOG(INFO) << "Worker " << i << " assigned to task " << j
                  << ".  Cost = " << costs[i][j];
      }
    }
  }
}
}  // namespace operations_research

int main(int argc, char** argv) {
  operations_research::AssignmentMip();
  return EXIT_SUCCESS;
}

Java

package com.google.ortools.linearsolver.samples;
import com.google.ortools.Loader;
import com.google.ortools.linearsolver.MPConstraint;
import com.google.ortools.linearsolver.MPObjective;
import com.google.ortools.linearsolver.MPSolver;
import com.google.ortools.linearsolver.MPVariable;

/** MIP example that solves an assignment problem. */
public class AssignmentMip {
  public static void main(String[] args) {
    Loader.loadNativeLibraries();
    // Data
    double[][] costs = {
        {90, 80, 75, 70},
        {35, 85, 55, 65},
        {125, 95, 90, 95},
        {45, 110, 95, 115},
        {50, 100, 90, 100},
    };
    int numWorkers = costs.length;
    int numTasks = costs[0].length;

    // Solver
    // Create the linear solver with the SCIP backend.
    MPSolver solver = MPSolver.createSolver("SCIP");
    if (solver == null) {
      System.out.println("Could not create solver SCIP");
      return;
    }

    // Variables
    // x[i][j] is an array of 0-1 variables, which will be 1
    // if worker i is assigned to task j.
    MPVariable[][] x = new MPVariable[numWorkers][numTasks];
    for (int i = 0; i < numWorkers; ++i) {
      for (int j = 0; j < numTasks; ++j) {
        x[i][j] = solver.makeIntVar(0, 1, "");
      }
    }

    // Constraints
    // Each worker is assigned to at most one task.
    for (int i = 0; i < numWorkers; ++i) {
      MPConstraint constraint = solver.makeConstraint(0, 1, "");
      for (int j = 0; j < numTasks; ++j) {
        constraint.setCoefficient(x[i][j], 1);
      }
    }
    // Each task is assigned to exactly one worker.
    for (int j = 0; j < numTasks; ++j) {
      MPConstraint constraint = solver.makeConstraint(1, 1, "");
      for (int i = 0; i < numWorkers; ++i) {
        constraint.setCoefficient(x[i][j], 1);
      }
    }

    // Objective
    MPObjective objective = solver.objective();
    for (int i = 0; i < numWorkers; ++i) {
      for (int j = 0; j < numTasks; ++j) {
        objective.setCoefficient(x[i][j], costs[i][j]);
      }
    }
    objective.setMinimization();

    // Solve
    MPSolver.ResultStatus resultStatus = solver.solve();

    // Print solution.
    // Check that the problem has a feasible solution.
    if (resultStatus == MPSolver.ResultStatus.OPTIMAL
        || resultStatus == MPSolver.ResultStatus.FEASIBLE) {
      System.out.println("Total cost: " + objective.value() + "\n");
      for (int i = 0; i < numWorkers; ++i) {
        for (int j = 0; j < numTasks; ++j) {
          // Test if x[i][j] is 0 or 1 (with tolerance for floating point
          // arithmetic).
          if (x[i][j].solutionValue() > 0.5) {
            System.out.println(
                "Worker " + i + " assigned to task " + j + ".  Cost = " + costs[i][j]);
          }
        }
      }
    } else {
      System.err.println("No solution found.");
    }
  }

  private AssignmentMip() {}
}

C#

using System;
using Google.OrTools.LinearSolver;

public class AssignmentMip
{
  static void Main()
  {
    // Data.
    int[,] costs = {
      {90, 80, 75, 70},
      {35, 85, 55, 65},
      {125, 95, 90, 95},
      {45, 110, 95, 115},
      {50, 100, 90, 100},
    };
    int numWorkers = costs.GetLength(0);
    int numTasks = costs.GetLength(1);

    // Model.
    Solver solver = Solver.CreateSolver("SCIP");

    // Variables.
    // x[i, j] is an array of 0-1 variables, which will be 1
    // if worker i is assigned to task j.
    Variable[,] x = new Variable[numWorkers, numTasks];
    for (int i = 0; i < numWorkers; ++i)
    {
      for (int j = 0; j < numTasks; ++j)
      {
        x[i, j] = solver.MakeIntVar(0, 1, $"worker_{i}_task_{j}");
      }
    }

    // Constraints
    // Each worker is assigned to at most one task.
    for (int i = 0; i < numWorkers; ++i)
    {
      Constraint constraint = solver.MakeConstraint(0, 1, "");
      for (int j = 0; j < numTasks; ++j)
      {
        constraint.SetCoefficient(x[i, j], 1);
      }
    }
    // Each task is assigned to exactly one worker.
    for (int j = 0; j < numTasks; ++j)
    {
      Constraint constraint = solver.MakeConstraint(1, 1, "");
      for (int i = 0; i < numWorkers; ++i)
      {
        constraint.SetCoefficient(x[i, j], 1);
      }
    }

    // Objective
    Objective objective = solver.Objective();
    for (int i = 0; i < numWorkers; ++i)
    {
      for (int j = 0; j < numTasks; ++j)
      {
        objective.SetCoefficient(x[i, j], 1);
      }
    }
    objective.SetMinimization();

    // Solve
    Solver.ResultStatus resultStatus = solver.Solve();

    // Print solution.
    // Check that the problem has a feasible solution.
    if (resultStatus == Solver.ResultStatus.OPTIMAL || resultStatus == Solver.ResultStatus.FEASIBLE)
    {
      Console.WriteLine($"Total cost: {solver.Objective().Value()}\n");
      for (int i = 0; i < numWorkers; ++i)
      {
        for (int j = 0; j < numTasks; ++j)
        {
          // Test if x[i, j] is 0 or 1 (with tolerance for floating point
          // arithmetic).
          if (x[i, j].SolutionValue() > 0.5)
          {
            Console.WriteLine($"Worker {i} assigned to task {j}. Cost: {costs[i, j]}");
          }
        }
      }
    } else {
      Console.WriteLine("No solution found.");
    }
  }
}

CP SAT solution

The following sections describe how to solve the problem using the CP-SAT solver.

Import the libraries

The following code imports the required libraries.

Python

from ortools.sat.python import cp_model

C++

#include "ortools/sat/cp_model.h"

Java

import com.google.ortools.Loader;
import com.google.ortools.sat.CpModel;
import com.google.ortools.sat.CpSolver;
import com.google.ortools.sat.CpSolverStatus;
import com.google.ortools.sat.IntVar;
import com.google.ortools.sat.LinearExpr;

C#

using System;
using Google.OrTools.Sat;

Declare the model

The following code declares the CP-SAT model.

Python

model = cp_model.CpModel()

C++

CpModelBuilder cp_model;

Java

CpModel model = new CpModel();

C#

CpModel model = new CpModel();

Create the data

The following code sets up the data for the problem.

Python

costs = [
    [90, 80, 75, 70],
    [35, 85, 55, 65],
    [125, 95, 90, 95],
    [45, 110, 95, 115],
    [50, 100, 90, 100],
]
num_workers = len(costs)
num_tasks = len(costs[0])

C++

const std::vector<std::vector<double>> costs{
    {90, 80, 75, 70},   {35, 85, 55, 65},   {125, 95, 90, 95},
    {45, 110, 95, 115}, {50, 100, 90, 100},
};
const int num_workers = costs.size();
const int num_tasks = costs[0].size();

Java

int[][] costs = {
    {90, 80, 75, 70},
    {35, 85, 55, 65},
    {125, 95, 90, 95},
    {45, 110, 95, 115},
    {50, 100, 90, 100},
};
final int numWorkers = costs.length;
final int numTasks = costs[0].length;

C#

int[,] costs = {
  {90, 80, 75, 70},
  {35, 85, 55, 65},
  {125, 95, 90, 95},
  {45, 110, 95, 115},
  {50, 100, 90, 100},
};
int numWorkers = costs.GetLength(0);
int numTasks = costs.GetLength(1);

The costs array corresponds to the table of costs for assigning workers to tasks, shown above.

Create the variables

The following code creates binary integer variables for the problem.

Python

x = []
for i in range(num_workers):
    t = []
    for j in range(num_tasks):
        t.append(model.NewBoolVar('x[%i,%i]' % (i, j)))
    x.append(t)

C++

// x[i][j] is an array of Boolean variables. x[i][j] is true
// if worker i is assigned to task j.
std::vector<std::vector<BoolVar>> x(num_workers,
                                    std::vector<BoolVar>(num_tasks));
for (int i = 0; i < num_workers; ++i) {
  for (int j = 0; j < num_tasks; ++j) {
    x[i][j] = cp_model.NewBoolVar();
  }
}

Java

IntVar[][] x = new IntVar[numWorkers][numTasks];
// Variables in a 1-dim array.
IntVar[] xFlat = new IntVar[numWorkers * numTasks];
int[] costsFlat = new int[numWorkers * numTasks];
for (int i = 0; i < numWorkers; ++i) {
  for (int j = 0; j < numTasks; ++j) {
    x[i][j] = model.newIntVar(0, 1, "");
    int k = i * numTasks + j;
    xFlat[k] = x[i][j];
    costsFlat[k] = costs[i][j];
  }
}

C#

IntVar[,] x = new IntVar[numWorkers, numTasks];
// Variables in a 1-dim array.
IntVar[] xFlat = new IntVar[numWorkers * numTasks];
int[] costsFlat = new int[numWorkers * numTasks];
for (int i = 0; i < numWorkers; ++i)
{
  for (int j = 0; j < numTasks; ++j)
  {
    x[i, j] = model.NewIntVar(0, 1, $"worker_{i}_task_{j}");
    int k = i * numTasks + j;
    xFlat[k] = x[i, j];
    costsFlat[k] = costs[i, j];
  }
}

Create the constraints

The following code creates the constraints for the problem.

Python

# Each worker is assigned to at most one task.
for i in range(num_workers):
    model.Add(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):
    model.Add(sum(x[i][j] for i in range(num_workers)) == 1)

C++

// Each worker is assigned to at most one task.
for (int i = 0; i < num_workers; ++i) {
  LinearExpr worker_sum;
  for (int j = 0; j < num_tasks; ++j) {
    worker_sum.AddTerm(x[i][j], 1);
  }
  cp_model.AddLessOrEqual(worker_sum, 1);
}
// Each task is assigned to exactly one worker.
for (int j = 0; j < num_tasks; ++j) {
  LinearExpr task_sum;
  for (int i = 0; i < num_workers; ++i) {
    task_sum.AddTerm(x[i][j], 1);
  }
  cp_model.AddEquality(task_sum, 1);
}

Java

// Each worker is assigned to at most one task.
for (int i = 0; i < numWorkers; ++i) {
  IntVar[] vars = new IntVar[numTasks];
  for (int j = 0; j < numTasks; ++j) {
    vars[j] = x[i][j];
  }
  model.addLessOrEqual(LinearExpr.sum(vars), 1);
}
// Each task is assigned to exactly one worker.
for (int j = 0; j < numTasks; ++j) {
  // LinearExpr taskSum;
  IntVar[] vars = new IntVar[numWorkers];
  for (int i = 0; i < numWorkers; ++i) {
    vars[i] = x[i][j];
  }
  model.addEquality(LinearExpr.sum(vars), 1);
}

C#

// Each worker is assigned to at most one task.
for (int i = 0; i < numWorkers; ++i)
{
  IntVar[] vars = new IntVar[numTasks];
  for (int j = 0; j < numTasks; ++j)
  {
    vars[j] = x[i, j];
  }
  model.Add(LinearExpr.Sum(vars) <= 1);
}

// Each task is assigned to exactly one worker.
for (int j = 0; j < numTasks; ++j)
{
  IntVar[] vars = new IntVar[numWorkers];
  for (int i = 0; i < numWorkers; ++i)
  {
    vars[i] = x[i, j];
  }
  model.Add(LinearExpr.Sum(vars) == 1);
}

Create the objective function

The following code creates the objective function for the problem.

Python

objective_terms = []
for i in range(num_workers):
    for j in range(num_tasks):
        objective_terms.append(costs[i][j] * x[i][j])
model.Minimize(sum(objective_terms))

C++

LinearExpr total_cost;
for (int i = 0; i < num_workers; ++i) {
  for (int j = 0; j < num_tasks; ++j) {
    total_cost.AddTerm(x[i][j], costs[i][j]);
  }
}
cp_model.Minimize(total_cost);

Java

model.minimize(LinearExpr.scalProd(xFlat, costsFlat));

C#

model.Minimize(LinearExpr.ScalProd(xFlat, costsFlat));

The value of the objective function is the total cost over all variables that are assigned the value 1 by the solver.

Invoke the solver

The following code invokes the solver.

Python

solver = cp_model.CpSolver()
status = solver.Solve(model)

C++

const CpSolverResponse response = Solve(cp_model.Build());

Java

CpSolver solver = new CpSolver();
CpSolverStatus status = solver.solve(model);

C#

CpSolver solver = new CpSolver();
CpSolverStatus status = solver.Solve(model);
Console.WriteLine($"Solve status: {status}");

The following code prints the solution to the problem.

Python

if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print('Total cost = %i' % solver.ObjectiveValue())
    print()
    for i in range(num_workers):
        for j in range(num_tasks):
            if solver.BooleanValue(x[i][j]):
                print('Worker ', i, ' assigned to task ', j, '  Cost = ',
                      costs[i][j])
else:
    print('No solution found.')

C++

if (response.status() == CpSolverStatus::INFEASIBLE) {
  LOG(FATAL) << "No solution found.";
}

LOG(INFO) << "Total cost: " << response.objective_value();
LOG(INFO);
for (int i = 0; i < num_workers; ++i) {
  for (int j = 0; j < num_tasks; ++j) {
    if (SolutionBooleanValue(response, x[i][j])) {
      LOG(INFO) << "Task " << i << " assigned to worker " << j
                << ".  Cost: " << costs[i][j];
    }
  }
}

Java

// Check that the problem has a feasible solution.
if (status == CpSolverStatus.OPTIMAL || status == CpSolverStatus.FEASIBLE) {
  System.out.println("Total cost: " + solver.objectiveValue() + "\n");
  for (int i = 0; i < numWorkers; ++i) {
    for (int j = 0; j < numTasks; ++j) {
      if (solver.value(x[i][j]) == 1) {
        System.out.println(
            "Worker " + i + " assigned to task " + j + ".  Cost: " + costs[i][j]);
      }
    }
  }
} else {
  System.err.println("No solution found.");
}

C#

// Check that the problem has a feasible solution.
if (status == CpSolverStatus.Optimal || status == CpSolverStatus.Feasible) {
  Console.WriteLine($"Total cost: {solver.ObjectiveValue}\n");
  for (int i = 0; i < numWorkers; ++i)
  {
    for (int j = 0; j < numTasks; ++j)
    {
      if (solver.Value(x[i, j]) > 0.5)
      {
        Console.WriteLine($"Worker {i} assigned to task {j}. Cost: {costs[i, j]}");
      }
    }
  }
} else {
  Console.WriteLine("No solution found.");
}

Here is the output of the program.

Total cost = 265

Worker  0  assigned to task  3   Cost =  70
Worker  1  assigned to task  2   Cost =  55
Worker  2  assigned to task  1   Cost =  95
Worker  3  assigned to task  0   Cost =  45

Complete programs

Here are the complete programs for the CP-SAT solution.

Python

from ortools.sat.python import cp_model


def main():
    # Data
    costs = [
        [90, 80, 75, 70],
        [35, 85, 55, 65],
        [125, 95, 90, 95],
        [45, 110, 95, 115],
        [50, 100, 90, 100],
    ]
    num_workers = len(costs)
    num_tasks = len(costs[0])

    # Model
    model = cp_model.CpModel()

    # Variables
    x = []
    for i in range(num_workers):
        t = []
        for j in range(num_tasks):
            t.append(model.NewBoolVar('x[%i,%i]' % (i, j)))
        x.append(t)

    # Constraints
    # Each worker is assigned to at most one task.
    for i in range(num_workers):
        model.Add(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):
        model.Add(sum(x[i][j] for i in range(num_workers)) == 1)

    # Objective
    objective_terms = []
    for i in range(num_workers):
        for j in range(num_tasks):
            objective_terms.append(costs[i][j] * x[i][j])
    model.Minimize(sum(objective_terms))

    # Solve
    solver = cp_model.CpSolver()
    status = solver.Solve(model)

    # Print solution.
    if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
        print('Total cost = %i' % solver.ObjectiveValue())
        print()
        for i in range(num_workers):
            for j in range(num_tasks):
                if solver.BooleanValue(x[i][j]):
                    print('Worker ', i, ' assigned to task ', j, '  Cost = ',
                          costs[i][j])
    else:
        print('No solution found.')


if __name__ == '__main__':
    main()

C++

#include "ortools/sat/cp_model.h"
namespace operations_research {
namespace sat {

void IntegerProgrammingExample() {
  // Data
  const std::vector<std::vector<double>> costs{
      {90, 80, 75, 70},   {35, 85, 55, 65},   {125, 95, 90, 95},
      {45, 110, 95, 115}, {50, 100, 90, 100},
  };
  const int num_workers = costs.size();
  const int num_tasks = costs[0].size();

  // Model
  CpModelBuilder cp_model;

  // Variables
  // x[i][j] is an array of Boolean variables. x[i][j] is true
  // if worker i is assigned to task j.
  std::vector<std::vector<BoolVar>> x(num_workers,
                                      std::vector<BoolVar>(num_tasks));
  for (int i = 0; i < num_workers; ++i) {
    for (int j = 0; j < num_tasks; ++j) {
      x[i][j] = cp_model.NewBoolVar();
    }
  }

  // Constraints
  // Each worker is assigned to at most one task.
  for (int i = 0; i < num_workers; ++i) {
    LinearExpr worker_sum;
    for (int j = 0; j < num_tasks; ++j) {
      worker_sum.AddTerm(x[i][j], 1);
    }
    cp_model.AddLessOrEqual(worker_sum, 1);
  }
  // Each task is assigned to exactly one worker.
  for (int j = 0; j < num_tasks; ++j) {
    LinearExpr task_sum;
    for (int i = 0; i < num_workers; ++i) {
      task_sum.AddTerm(x[i][j], 1);
    }
    cp_model.AddEquality(task_sum, 1);
  }

  // Objective
  LinearExpr total_cost;
  for (int i = 0; i < num_workers; ++i) {
    for (int j = 0; j < num_tasks; ++j) {
      total_cost.AddTerm(x[i][j], costs[i][j]);
    }
  }
  cp_model.Minimize(total_cost);

  // Solve
  const CpSolverResponse response = Solve(cp_model.Build());

  // Print solution.
  if (response.status() == CpSolverStatus::INFEASIBLE) {
    LOG(FATAL) << "No solution found.";
  }

  LOG(INFO) << "Total cost: " << response.objective_value();
  LOG(INFO);
  for (int i = 0; i < num_workers; ++i) {
    for (int j = 0; j < num_tasks; ++j) {
      if (SolutionBooleanValue(response, x[i][j])) {
        LOG(INFO) << "Task " << i << " assigned to worker " << j
                  << ".  Cost: " << costs[i][j];
      }
    }
  }
}
}  // namespace sat
}  // namespace operations_research

int main(int argc, char** argv) {
  operations_research::sat::IntegerProgrammingExample();
  return EXIT_SUCCESS;
}

Java

package com.google.ortools.sat.samples;
import com.google.ortools.Loader;
import com.google.ortools.sat.CpModel;
import com.google.ortools.sat.CpSolver;
import com.google.ortools.sat.CpSolverStatus;
import com.google.ortools.sat.IntVar;
import com.google.ortools.sat.LinearExpr;

/** Assignment problem. */
public class AssignmentSat {
  public static void main(String[] args) {
    Loader.loadNativeLibraries();
    // Data
    int[][] costs = {
        {90, 80, 75, 70},
        {35, 85, 55, 65},
        {125, 95, 90, 95},
        {45, 110, 95, 115},
        {50, 100, 90, 100},
    };
    final int numWorkers = costs.length;
    final int numTasks = costs[0].length;

    // Model
    CpModel model = new CpModel();

    // Variables
    IntVar[][] x = new IntVar[numWorkers][numTasks];
    // Variables in a 1-dim array.
    IntVar[] xFlat = new IntVar[numWorkers * numTasks];
    int[] costsFlat = new int[numWorkers * numTasks];
    for (int i = 0; i < numWorkers; ++i) {
      for (int j = 0; j < numTasks; ++j) {
        x[i][j] = model.newIntVar(0, 1, "");
        int k = i * numTasks + j;
        xFlat[k] = x[i][j];
        costsFlat[k] = costs[i][j];
      }
    }

    // Constraints
    // Each worker is assigned to at most one task.
    for (int i = 0; i < numWorkers; ++i) {
      IntVar[] vars = new IntVar[numTasks];
      for (int j = 0; j < numTasks; ++j) {
        vars[j] = x[i][j];
      }
      model.addLessOrEqual(LinearExpr.sum(vars), 1);
    }
    // Each task is assigned to exactly one worker.
    for (int j = 0; j < numTasks; ++j) {
      // LinearExpr taskSum;
      IntVar[] vars = new IntVar[numWorkers];
      for (int i = 0; i < numWorkers; ++i) {
        vars[i] = x[i][j];
      }
      model.addEquality(LinearExpr.sum(vars), 1);
    }

    // Objective
    model.minimize(LinearExpr.scalProd(xFlat, costsFlat));

    // Solve
    CpSolver solver = new CpSolver();
    CpSolverStatus status = solver.solve(model);

    // Print solution.
    // Check that the problem has a feasible solution.
    if (status == CpSolverStatus.OPTIMAL || status == CpSolverStatus.FEASIBLE) {
      System.out.println("Total cost: " + solver.objectiveValue() + "\n");
      for (int i = 0; i < numWorkers; ++i) {
        for (int j = 0; j < numTasks; ++j) {
          if (solver.value(x[i][j]) == 1) {
            System.out.println(
                "Worker " + i + " assigned to task " + j + ".  Cost: " + costs[i][j]);
          }
        }
      }
    } else {
      System.err.println("No solution found.");
    }
  }

  private AssignmentSat() {}
}

C#

using System;
using Google.OrTools.Sat;

public class AssignmentSat
{
  static void Main()
  {
    // Data.
    int[,] costs = {
      {90, 80, 75, 70},
      {35, 85, 55, 65},
      {125, 95, 90, 95},
      {45, 110, 95, 115},
      {50, 100, 90, 100},
    };
    int numWorkers = costs.GetLength(0);
    int numTasks = costs.GetLength(1);

    // Model.
    CpModel model = new CpModel();

    // Variables.
    IntVar[,] x = new IntVar[numWorkers, numTasks];
    // Variables in a 1-dim array.
    IntVar[] xFlat = new IntVar[numWorkers * numTasks];
    int[] costsFlat = new int[numWorkers * numTasks];
    for (int i = 0; i < numWorkers; ++i)
    {
      for (int j = 0; j < numTasks; ++j)
      {
        x[i, j] = model.NewIntVar(0, 1, $"worker_{i}_task_{j}");
        int k = i * numTasks + j;
        xFlat[k] = x[i, j];
        costsFlat[k] = costs[i, j];
      }
    }

    // Constraints
    // Each worker is assigned to at most one task.
    for (int i = 0; i < numWorkers; ++i)
    {
      IntVar[] vars = new IntVar[numTasks];
      for (int j = 0; j < numTasks; ++j)
      {
        vars[j] = x[i, j];
      }
      model.Add(LinearExpr.Sum(vars) <= 1);
    }

    // Each task is assigned to exactly one worker.
    for (int j = 0; j < numTasks; ++j)
    {
      IntVar[] vars = new IntVar[numWorkers];
      for (int i = 0; i < numWorkers; ++i)
      {
        vars[i] = x[i, j];
      }
      model.Add(LinearExpr.Sum(vars) == 1);
    }

    // Objective
    model.Minimize(LinearExpr.ScalProd(xFlat, costsFlat));

    // Solve
    CpSolver solver = new CpSolver();
    CpSolverStatus status = solver.Solve(model);
    Console.WriteLine($"Solve status: {status}");

    // Print solution.
    // Check that the problem has a feasible solution.
    if (status == CpSolverStatus.Optimal || status == CpSolverStatus.Feasible) {
      Console.WriteLine($"Total cost: {solver.ObjectiveValue}\n");
      for (int i = 0; i < numWorkers; ++i)
      {
        for (int j = 0; j < numTasks; ++j)
        {
          if (solver.Value(x[i, j]) > 0.5)
          {
            Console.WriteLine($"Worker {i} assigned to task {j}. Cost: {costs[i, j]}");
          }
        }
      }
    } else {
      Console.WriteLine("No solution found.");
    }

    Console.WriteLine("Statistics");
    Console.WriteLine($"  - conflicts : {solver.NumConflicts()}");
    Console.WriteLine($"  - branches  : {solver.NumBranches()}");
    Console.WriteLine($"  - wall time : {solver.WallTime()}s");
  }
}