# 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 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 MPSolver wrapper.

### Import the libraries

The following code imports the required libraries.

### Python

from ortools.linear_solver import pywraplp

### C++

#include <memory>
#include <vector>

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

using System;

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

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

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

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

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

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

if not solver:
return

### C++

// Create the mip solver with the SCIP backend.
std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("SCIP"));
if (!solver) {
LOG(WARNING) << "SCIP solver unavailable.";
return;
}

### 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");
if (solver is null)
{
return;
}

### 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):
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(
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.
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):

# Each task is assigned to exactly one worker.
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) {
for (int i = 0; i < num_workers; ++i) {
}
}

### 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):
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], costs[i, j]);
}
}
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

print(f"Solving with {solver.SolverVersion()}")
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(f"Total cost = {solver.Objective().Value()}\n")
for i in range(num_workers):
# Test if x[i,j] is 1 (with tolerance for floating point arithmetic).
if x[i, j].solution_value() > 0.5:
print(f"Worker {i} assigned to task {j}." + f" Cost: {costs[i][j]}")
else:
print("No solution found.")

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

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

if not solver:
return

# 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):
x[i, j] = solver.IntVar(0, 1, "")

# Constraints
# Each worker is assigned to at most 1 task.
for i in range(num_workers):

# Each task is assigned to exactly one worker.
solver.Add(solver.Sum([x[i, j] for i in range(num_workers)]) == 1)

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

# Solve
print(f"Solving with {solver.SolverVersion()}")
status = solver.Solve()

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

if __name__ == "__main__":
main()

### C++

#include <memory>
#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();

// Solver
// Create the mip solver with the SCIP backend.
std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("SCIP"));
if (!solver) {
LOG(WARNING) << "SCIP solver unavailable.";
return;
}

// 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(
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) {
for (int i = 0; i < num_workers; ++i) {
}
}

// 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

/** MIP example that solves an assignment problem. */
public class AssignmentMip {
public static void main(String[] args) {
// 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;

// 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.
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;

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

// Solver.
Solver solver = Solver.CreateSolver("SCIP");
if (solver is null)
{
return;
}

// 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], costs[i, j]);
}
}
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

import io

import pandas as pd

from ortools.sat.python import cp_model

### C++

#include <stdlib.h>

#include <vector>

#include "ortools/base/logging.h"
#include "ortools/sat/cp_model.h"
#include "ortools/sat/cp_model.pb.h"
#include "ortools/sat/cp_model_solver.h"

### Java

import java.util.ArrayList;
import java.util.List;
import java.util.stream.IntStream;

### C#

using System;
using System.Collections.Generic;

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

data_str = """
w1    t1    90
w1    t2    80
w1    t3    75
w1    t4    70
w2    t1    35
w2    t2    85
w2    t3    55
w2    t4    65
w3    t1   125
w3    t2    95
w3    t3    90
w3    t4    95
w4    t1    45
w4    t2   110
w4    t3    95
w4    t4   115
w5    t1    50
w5    t2   110
w5    t3    90
w5    t4   100
"""

### C++

const std::vector<std::vector<int>> 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 = static_cast<int>(costs.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[] allWorkers = IntStream.range(0, numWorkers).toArray();

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

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 = model.new_bool_var_series(name="x", index=data.index)

### 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,
for (int i = 0; i < num_workers; ++i) {
for (int j = 0; j < num_tasks; ++j) {
x[i][j] = cp_model.NewBoolVar();
}
}

### Java

for (int worker : allWorkers) {
}
}

### C#

BoolVar[,] x = new BoolVar[numWorkers, numTasks];
// Variables in a 1-dim array.
for (int worker = 0; worker < numWorkers; ++worker)
{
{
}
}

### Create the constraints

The following code creates the constraints for the problem.

### Python

# Each worker is assigned to at most one task.

# Each task is assigned to exactly one worker.

### C++

// Each worker is assigned to at most one task.
for (int i = 0; i < num_workers; ++i) {
}
// Each task is assigned to exactly one worker.
for (int j = 0; j < num_tasks; ++j) {
for (int i = 0; i < num_workers; ++i) {
}
}

### Java

// Each worker is assigned to at most one task.
for (int worker : allWorkers) {
}
}

// Each task is assigned to exactly one worker.
List<Literal> workers = new ArrayList<>();
for (int worker : allWorkers) {
}
}

### C#

// Each worker is assigned to at most one task.
for (int worker = 0; worker < numWorkers; ++worker)
{
{
}
}

// Each task is assigned to exactly one worker.
{
List<ILiteral> workers = new List<ILiteral>();
for (int worker = 0; worker < numWorkers; ++worker)
{
}
}

### Create the objective function

The following code creates the objective function for the problem.

### Python

model.minimize(data.cost.dot(x))

### C++

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

### Java

LinearExprBuilder obj = LinearExpr.newBuilder();
for (int worker : allWorkers) {
}
}
model.minimize(obj);

### C#

LinearExprBuilder obj = LinearExpr.NewBuilder();
for (int worker = 0; worker < numWorkers; ++worker)
{
{
}
}
model.Minimize(obj);

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(f"Total cost = {solver.objective_value}\n")
selected = data.loc[solver.boolean_values(x).loc[lambda x: x].index]
for unused_index, row in selected.iterrows():
print(f"{row.task} assigned to {row.worker} with a cost of {row.cost}")
elif status == cp_model.INFEASIBLE:
print("No solution found")
else:
print("Something is wrong, check the status and the log of the solve")

### 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.booleanValue(x[i][j])) {
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

import io

import pandas as pd

from ortools.sat.python import cp_model

def main() -> None:
# Data
data_str = """
w1    t1    90
w1    t2    80
w1    t3    75
w1    t4    70
w2    t1    35
w2    t2    85
w2    t3    55
w2    t4    65
w3    t1   125
w3    t2    95
w3    t3    90
w3    t4    95
w4    t1    45
w4    t2   110
w4    t3    95
w4    t4   115
w5    t1    50
w5    t2   110
w5    t3    90
w5    t4   100
"""

# Model
model = cp_model.CpModel()

# Variables
x = model.new_bool_var_series(name="x", index=data.index)

# Constraints
# Each worker is assigned to at most one task.

# Each task is assigned to exactly one worker.

# Objective
model.minimize(data.cost.dot(x))

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

# Print solution.
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
print(f"Total cost = {solver.objective_value}\n")
selected = data.loc[solver.boolean_values(x).loc[lambda x: x].index]
for unused_index, row in selected.iterrows():
print(f"{row.task} assigned to {row.worker} with a cost of {row.cost}")
elif status == cp_model.INFEASIBLE:
print("No solution found")
else:
print("Something is wrong, check the status and the log of the solve")

if __name__ == "__main__":
main()

### C++

#include <stdlib.h>

#include <vector>

#include "ortools/base/logging.h"
#include "ortools/sat/cp_model.h"
#include "ortools/sat/cp_model.pb.h"
#include "ortools/sat/cp_model_solver.h"

namespace operations_research {
namespace sat {

void IntegerProgrammingExample() {
// Data
const std::vector<std::vector<int>> 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 = static_cast<int>(costs.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,
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) {
}
// Each task is assigned to exactly one worker.
for (int j = 0; j < num_tasks; ++j) {
for (int i = 0; i < num_workers; ++i) {
}
}

// Objective
LinearExpr total_cost;
for (int i = 0; i < num_workers; ++i) {
for (int j = 0; j < num_tasks; ++j) {
total_cost += 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

import java.util.ArrayList;
import java.util.List;
import java.util.stream.IntStream;

/** Assignment problem. */
public class AssignmentSat {
public static void main(String[] args) {
// 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[] allWorkers = IntStream.range(0, numWorkers).toArray();

// Model
CpModel model = new CpModel();

// Variables
for (int worker : allWorkers) {
}
}

// Constraints
// Each worker is assigned to at most one task.
for (int worker : allWorkers) {
}
}

// Each task is assigned to exactly one worker.
List<Literal> workers = new ArrayList<>();
for (int worker : allWorkers) {
}
}

// Objective
LinearExprBuilder obj = LinearExpr.newBuilder();
for (int worker : allWorkers) {
}
}
model.minimize(obj);

// 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.booleanValue(x[i][j])) {
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 System.Collections.Generic;

public class AssignmentSat
{
public static void Main(String[] args)
{
// 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);

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

// Variables.
BoolVar[,] x = new BoolVar[numWorkers, numTasks];
// Variables in a 1-dim array.
for (int worker = 0; worker < numWorkers; ++worker)
{
{
}
}

// Constraints
// Each worker is assigned to at most one task.
for (int worker = 0; worker < numWorkers; ++worker)
{
{
}
}

// Each task is assigned to exactly one worker.
{
List<ILiteral> workers = new List<ILiteral>();
for (int worker = 0; worker < numWorkers; ++worker)
{
}
}

// Objective
LinearExprBuilder obj = LinearExpr.NewBuilder();
for (int worker = 0; worker < numWorkers; ++worker)
{
{
}
}
model.Minimize(obj);

// 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");
}
}
[{ "type": "thumb-down", "id": "missingTheInformationINeed", "label":"Missing the information I need" },{ "type": "thumb-down", "id": "tooComplicatedTooManySteps", "label":"Too complicated / too many steps" },{ "type": "thumb-down", "id": "outOfDate", "label":"Out of date" },{ "type": "thumb-down", "id": "samplesCodeIssue", "label":"Samples / code issue" },{ "type": "thumb-down", "id": "otherDown", "label":"Other" }]
[{ "type": "thumb-up", "id": "easyToUnderstand", "label":"Easy to understand" },{ "type": "thumb-up", "id": "solvedMyProblem", "label":"Solved my problem" },{ "type": "thumb-up", "id": "otherUp", "label":"Other" }]