# Solving an Assignment Problem

Stay organized with collections Save and categorize content based on your preferences.

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"```

### Java

```import com.google.ortools.Loader;

### C#

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

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

```package com.google.ortools.linearsolver.samples;

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

`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 com.google.ortools.Loader;
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

```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<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 = []
for i in range(num_workers):
t = []
t.append(model.NewBoolVar(f'x[{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,
for (int i = 0; i < num_workers; ++i) {
for (int j = 0; j < num_tasks; ++j) {
x[i][j] = cp_model.NewBoolVar();
}
}```

### Java

```Literal[][] x = new Literal[numWorkers][numTasks];
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.
for i in range(num_workers):

# 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

```objective_terms = []
for i in range(num_workers):
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 += 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.ObjectiveValue()}')
print()
for i in range(num_workers):
if solver.BooleanValue(x[i][j]):
print(
f'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.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

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

# Model
model = cp_model.CpModel()

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

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

# Each task is assigned to exactly one worker.

# Objective
objective_terms = []
for i in range(num_workers):
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(f'Total cost = {solver.ObjectiveValue()}')
print()
for i in range(num_workers):
if solver.BooleanValue(x[i][j]):
print(
f'Worker {i} assigned to task {j} Cost = {costs[i][j]}')
else:
print('No solution found.')

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

```package com.google.ortools.sat.samples;
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" }]