# Assignment with Allowed Groups

This section describes an assignment problem in which only certain allowed groups of workers can be assigned to the tasks. In the example there are twelve workers, numbered 0 - 11. The allowed groups are combinations of the following pairs of workers.

```  group1 =  [[2, 3],       # Subgroups of workers 0 - 3
[1, 3],
[1, 2],
[0, 1],
[0, 2]]

group2 =  [[6, 7],       # Subgroups of workers 4 - 7
[5, 7],
[5, 6],
[4, 5],
[4, 7]]

group3 =  [[10, 11],     # Subgroups of workers 8 - 11
[9, 11],
[9, 10],
[8, 10],
[8, 11]]```

An allowed group can be any combination of three pairs of workers, one pair from each of group1, group2, and group3. For example, combining `[2, 3]`, `[6, 7]`, and `[10, 11]` results in the allowed group `[2, 3, 6, 7, 10, 11]`. Since each of the three sets contains five elements, the total number of allowed groups is `5 * 5 * 5 = 125`.

Note that a group of workers can be a solution to the problem if it belongs to any one of the allowed groups. In other words, the feasible set consists of points for which any one of the constraints is satisfied. This is an example of a non-convex problem. By contrast, the MIP Example, described previously, is a convex problem: for a point to be feasible, all constraints must be satisfied.

For non-convex problems like this one, the CP-SAT solver is usually faster than a MIP solver. The following sections present solutions to the problem using the CP-SAT solver and the MIP solver, and compare the solution times for the two solvers.

## CP-SAT solution

First, we'll describe a solution to the problem using the CP-SAT solver.

### Import the libraries

The following code imports the required library.

### Python

`from ortools.sat.python import cp_model`

### C++

```#include <stdlib.h>

#include <cstdint>
#include <numeric>
#include <vector>

#include "absl/strings/str_format.h"
#include "absl/types/span.h"
#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;
using System.Linq;

### Define the data

The following code creates the data for the program.

### Python

```costs = [
[90, 76, 75, 70, 50, 74],
[35, 85, 55, 65, 48, 101],
[125, 95, 90, 105, 59, 120],
[45, 110, 95, 115, 104, 83],
[60, 105, 80, 75, 59, 62],
[45, 65, 110, 95, 47, 31],
[38, 51, 107, 41, 69, 99],
[47, 85, 57, 71, 92, 77],
[39, 63, 97, 49, 118, 56],
[47, 101, 71, 60, 88, 109],
[17, 39, 103, 64, 61, 92],
[101, 45, 83, 59, 92, 27],
]
num_workers = len(costs)

### C++

```const std::vector<std::vector<int>> costs = {{
{{90, 76, 75, 70, 50, 74}},
{{35, 85, 55, 65, 48, 101}},
{{125, 95, 90, 105, 59, 120}},
{{45, 110, 95, 115, 104, 83}},
{{60, 105, 80, 75, 59, 62}},
{{45, 65, 110, 95, 47, 31}},
{{38, 51, 107, 41, 69, 99}},
{{47, 85, 57, 71, 92, 77}},
{{39, 63, 97, 49, 118, 56}},
{{47, 101, 71, 60, 88, 109}},
{{17, 39, 103, 64, 61, 92}},
{{101, 45, 83, 59, 92, 27}},
}};
const int num_workers = static_cast<int>(costs.size());
std::vector<int> all_workers(num_workers);
std::iota(all_workers.begin(), all_workers.end(), 0);

const int num_tasks = static_cast<int>(costs[0].size());

### Java

```int[][] costs = {
{90, 76, 75, 70, 50, 74},
{35, 85, 55, 65, 48, 101},
{125, 95, 90, 105, 59, 120},
{45, 110, 95, 115, 104, 83},
{60, 105, 80, 75, 59, 62},
{45, 65, 110, 95, 47, 31},
{38, 51, 107, 41, 69, 99},
{47, 85, 57, 71, 92, 77},
{39, 63, 97, 49, 118, 56},
{47, 101, 71, 60, 88, 109},
{17, 39, 103, 64, 61, 92},
{101, 45, 83, 59, 92, 27},
};
final int numWorkers = costs.length;
final int numTasks = costs[0].length;

final int[] allWorkers = IntStream.range(0, numWorkers).toArray();

### C#

```int[,] costs = {
{ 90, 76, 75, 70, 50, 74 },    { 35, 85, 55, 65, 48, 101 }, { 125, 95, 90, 105, 59, 120 },
{ 45, 110, 95, 115, 104, 83 }, { 60, 105, 80, 75, 59, 62 }, { 45, 65, 110, 95, 47, 31 },
{ 38, 51, 107, 41, 69, 99 },   { 47, 85, 57, 71, 92, 77 },  { 39, 63, 97, 49, 118, 56 },
{ 47, 101, 71, 60, 88, 109 },  { 17, 39, 103, 64, 61, 92 }, { 101, 45, 83, 59, 92, 27 },
};
int numWorkers = costs.GetLength(0);
int numTasks = costs.GetLength(1);

int[] allWorkers = Enumerable.Range(0, numWorkers).ToArray();

### Create the allowed groups

To define the allowed groups of workers for the CP-SAT solver, you create binary arrays that indicate which workers belong to a group. For example, for `group1` (workers 0 - 3), the binary vector `[0, 0, 1, 1]` specifies the group containing workers 2 and 3.

The following arrays define the allowed groups of workers.

### Python

```group1 = [
[0, 0, 1, 1],  # Workers 2, 3
[0, 1, 0, 1],  # Workers 1, 3
[0, 1, 1, 0],  # Workers 1, 2
[1, 1, 0, 0],  # Workers 0, 1
[1, 0, 1, 0],  # Workers 0, 2
]

group2 = [
[0, 0, 1, 1],  # Workers 6, 7
[0, 1, 0, 1],  # Workers 5, 7
[0, 1, 1, 0],  # Workers 5, 6
[1, 1, 0, 0],  # Workers 4, 5
[1, 0, 0, 1],  # Workers 4, 7
]

group3 = [
[0, 0, 1, 1],  # Workers 10, 11
[0, 1, 0, 1],  # Workers 9, 11
[0, 1, 1, 0],  # Workers 9, 10
[1, 0, 1, 0],  # Workers 8, 10
[1, 0, 0, 1],  # Workers 8, 11
]```

### C++

```const std::vector<std::vector<int64_t>> group1 = {{
{{0, 0, 1, 1}},  // Workers 2, 3
{{0, 1, 0, 1}},  // Workers 1, 3
{{0, 1, 1, 0}},  // Workers 1, 2
{{1, 1, 0, 0}},  // Workers 0, 1
{{1, 0, 1, 0}},  // Workers 0, 2
}};

const std::vector<std::vector<int64_t>> group2 = {{
{{0, 0, 1, 1}},  // Workers 6, 7
{{0, 1, 0, 1}},  // Workers 5, 7
{{0, 1, 1, 0}},  // Workers 5, 6
{{1, 1, 0, 0}},  // Workers 4, 5
{{1, 0, 0, 1}},  // Workers 4, 7
}};

const std::vector<std::vector<int64_t>> group3 = {{
{{0, 0, 1, 1}},  // Workers 10, 11
{{0, 1, 0, 1}},  // Workers 9, 11
{{0, 1, 1, 0}},  // Workers 9, 10
{{1, 0, 1, 0}},  // Workers 8, 10
{{1, 0, 0, 1}},  // Workers 8, 11
}};```

### Java

```int[][] group1 = {
{0, 0, 1, 1}, // Workers 2, 3
{0, 1, 0, 1}, // Workers 1, 3
{0, 1, 1, 0}, // Workers 1, 2
{1, 1, 0, 0}, // Workers 0, 1
{1, 0, 1, 0}, // Workers 0, 2
};

int[][] group2 = {
{0, 0, 1, 1}, // Workers 6, 7
{0, 1, 0, 1}, // Workers 5, 7
{0, 1, 1, 0}, // Workers 5, 6
{1, 1, 0, 0}, // Workers 4, 5
{1, 0, 0, 1}, // Workers 4, 7
};

int[][] group3 = {
{0, 0, 1, 1}, // Workers 10, 11
{0, 1, 0, 1}, // Workers 9, 11
{0, 1, 1, 0}, // Workers 9, 10
{1, 0, 1, 0}, // Workers 8, 10
{1, 0, 0, 1}, // Workers 8, 11
};```

### C#

```long[,] group1 = {
{ 0, 0, 1, 1 }, // Workers 2, 3
{ 0, 1, 0, 1 }, // Workers 1, 3
{ 0, 1, 1, 0 }, // Workers 1, 2
{ 1, 1, 0, 0 }, // Workers 0, 1
{ 1, 0, 1, 0 }, // Workers 0, 2
};

long[,] group2 = {
{ 0, 0, 1, 1 }, // Workers 6, 7
{ 0, 1, 0, 1 }, // Workers 5, 7
{ 0, 1, 1, 0 }, // Workers 5, 6
{ 1, 1, 0, 0 }, // Workers 4, 5
{ 1, 0, 0, 1 }, // Workers 4, 7
};

long[,] group3 = {
{ 0, 0, 1, 1 }, // Workers 10, 11
{ 0, 1, 0, 1 }, // Workers 9, 11
{ 0, 1, 1, 0 }, // Workers 9, 10
{ 1, 0, 1, 0 }, // Workers 8, 10
{ 1, 0, 0, 1 }, // Workers 8, 11
};```

For CP-SAT it is not necessary to create all 125 combinations of these vectors in a loop. The CP-SAT solver provides a method, `AllowedAssignments`, which enables you to specify the constraints for the allowed groups separately for each of the three sets of workers (0 - 3, 4 - 7, and 8 - 11). Here's how it works:

### Python

```# Create variables for each worker, indicating whether they work on some task.
work = {}
for worker in range(num_workers):
work[worker] = model.new_bool_var(f"work[{worker}]")

for worker in range(num_workers):

# Define the allowed groups of worders
model.add_allowed_assignments([work[0], work[1], work[2], work[3]], group1)
model.add_allowed_assignments([work[4], work[5], work[6], work[7]], group2)
model.add_allowed_assignments([work[8], work[9], work[10], work[11]], group3)```

### C++

```// Create variables for each worker, indicating whether they work on some
std::vector<IntVar> work(num_workers);
for (int worker : all_workers) {
work[worker] = IntVar(
cp_model.NewBoolVar().WithName(absl::StrFormat("work[%d]", worker)));
}

for (int worker : all_workers) {
}
}

// Define the allowed groups of worders
auto table1 =
cp_model.AddAllowedAssignments({work[0], work[1], work[2], work[3]});
for (const auto& t : group1) {
}
auto table2 =
cp_model.AddAllowedAssignments({work[4], work[5], work[6], work[7]});
for (const auto& t : group2) {
}
auto table3 =
cp_model.AddAllowedAssignments({work[8], work[9], work[10], work[11]});
for (const auto& t : group3) {
}```

### Java

```// Create variables for each worker, indicating whether they work on some task.
IntVar[] work = new IntVar[numWorkers];
for (int worker : allWorkers) {
work[worker] = model.newBoolVar("work[" + worker + "]");
}

for (int worker : allWorkers) {
LinearExprBuilder expr = LinearExpr.newBuilder();
}
}

// Define the allowed groups of worders
model.addAllowedAssignments(new IntVar[] {work[0], work[1], work[2], work[3]})
model.addAllowedAssignments(new IntVar[] {work[4], work[5], work[6], work[7]})
model.addAllowedAssignments(new IntVar[] {work[8], work[9], work[10], work[11]})

### C#

```// Create variables for each worker, indicating whether they work on some task.
BoolVar[] work = new BoolVar[numWorkers];
foreach (int worker in allWorkers)
{
work[worker] = model.NewBoolVar(\$"work[{worker}]");
}

foreach (int worker in allWorkers)
{
List<ILiteral> tasks = new List<ILiteral>();
{
}
}

// Define the allowed groups of worders
model.AddAllowedAssignments(new IntVar[] { work[0], work[1], work[2], work[3] }).AddTuples(group1);
model.AddAllowedAssignments(new IntVar[] { work[4], work[5], work[6], work[7] }).AddTuples(group2);
model.AddAllowedAssignments(new IntVar[] { work[8], work[9], work[10], work[11] }).AddTuples(group3);```

The variables `work[i]` are 0-1 variables that indicate the work status or each worker. That is, `work[i]` equals 1 if worker i is assigned to a task, and 0 otherwise. The line `solver.Add(solver.AllowedAssignments([work[0], work[1], work[2], work[3]], group1))` defines the constraint that the work status of workers 0 - 3 must match one of the patterns in `group1`. You can see the full details of the code in the next section.

### Create the model

The following code creates the model.

### Python

`model = cp_model.CpModel()`

### C++

`CpModelBuilder cp_model;`

### Java

`CpModel model = new CpModel();`

### C#

`CpModel model = new CpModel();`

### Create the variables

The following code creates an array of variables for the problem.

### Python

```x = {}
for worker in range(num_workers):

### 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 worker : all_workers) {
}
}```

### Java

```Literal[][] x = new Literal[numWorkers][numTasks];
for (int worker : allWorkers) {
x[worker][task] = model.newBoolVar("x[" + worker + "," + task + "]");
}
}```

### C#

```BoolVar[,] x = new BoolVar[numWorkers, numTasks];
// Variables in a 1-dim array.
foreach (int worker in allWorkers)
{
{
}
}```

### Add the constraints

The following code creates the constraints for the program.

### Python

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

# Each task is assigned to exactly one worker.

### C++

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

### Java

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

// 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.
foreach (int worker in allWorkers)
{
List<ILiteral> tasks = new List<ILiteral>();
{
}
}

// Each task is assigned to exactly one worker.
{
List<ILiteral> workers = new List<ILiteral>();
foreach (int worker in allWorkers)
{
}
}```

### Create the objective

The following code creates the objective function.

### Python

```objective_terms = []
for worker in range(num_workers):
model.minimize(sum(objective_terms))```

### C++

```LinearExpr total_cost;
for (int worker : all_workers) {
}
}
cp_model.Minimize(total_cost);```

### Java

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

### C#

```LinearExprBuilder obj = LinearExpr.NewBuilder();
foreach (int worker in allWorkers)
{
{
}
}
model.Minimize(obj);```

### Invoke the solver

The following code invokes the solver and displays the results.

### 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}");```

### Display the results

Now, we can print the solution.

### Python

```if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
print(f"Total cost = {solver.objective_value}\n")
for worker in range(num_workers):
print(
+ f" Cost = {costs[worker][task]}"
)
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 worker : all_workers) {
if (SolutionBooleanValue(response, x[worker][task])) {
LOG(INFO) << "Worker " << worker << " assigned to task " << task
<< ".  Cost: " << costs[worker][task];
}
}
}```

### 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 worker : allWorkers) {
System.out.println("Worker " + worker + " assigned to task " + task
+ ".  Cost: " + costs[worker][task]);
}
}
}
} 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");
foreach (int worker in allWorkers)
{
{
if (solver.Value(x[worker, task]) > 0.5)
{
Console.WriteLine(\$"Worker {worker} assigned to task {task}. " +
}
}
}
}
else
{
Console.WriteLine("No solution found.");
}```

Here's the output of the program.

```Minimum cost = 239

Worker  0  assigned to task  4   Cost =  50
Worker  1  assigned to task  2   Cost =  55
Worker  5  assigned to task  5   Cost =  31
Worker  6  assigned to task  3   Cost =  41
Worker  10  assigned to task  0   Cost =  17
Worker  11  assigned to task  1   Cost =  45

Time =  0.0113 seconds```

### The entire program

Here is the entire program.

### Python

```"""Solves an assignment problem for given group of workers."""
from ortools.sat.python import cp_model

def main() -> None:
# Data
costs = [
[90, 76, 75, 70, 50, 74],
[35, 85, 55, 65, 48, 101],
[125, 95, 90, 105, 59, 120],
[45, 110, 95, 115, 104, 83],
[60, 105, 80, 75, 59, 62],
[45, 65, 110, 95, 47, 31],
[38, 51, 107, 41, 69, 99],
[47, 85, 57, 71, 92, 77],
[39, 63, 97, 49, 118, 56],
[47, 101, 71, 60, 88, 109],
[17, 39, 103, 64, 61, 92],
[101, 45, 83, 59, 92, 27],
]
num_workers = len(costs)

# Allowed groups of workers:
group1 = [
[0, 0, 1, 1],  # Workers 2, 3
[0, 1, 0, 1],  # Workers 1, 3
[0, 1, 1, 0],  # Workers 1, 2
[1, 1, 0, 0],  # Workers 0, 1
[1, 0, 1, 0],  # Workers 0, 2
]

group2 = [
[0, 0, 1, 1],  # Workers 6, 7
[0, 1, 0, 1],  # Workers 5, 7
[0, 1, 1, 0],  # Workers 5, 6
[1, 1, 0, 0],  # Workers 4, 5
[1, 0, 0, 1],  # Workers 4, 7
]

group3 = [
[0, 0, 1, 1],  # Workers 10, 11
[0, 1, 0, 1],  # Workers 9, 11
[0, 1, 1, 0],  # Workers 9, 10
[1, 0, 1, 0],  # Workers 8, 10
[1, 0, 0, 1],  # Workers 8, 11
]

# Model
model = cp_model.CpModel()

# Variables
x = {}
for worker in range(num_workers):

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

# Each task is assigned to exactly one worker.

# Create variables for each worker, indicating whether they work on some task.
work = {}
for worker in range(num_workers):
work[worker] = model.new_bool_var(f"work[{worker}]")

for worker in range(num_workers):

# Define the allowed groups of worders
model.add_allowed_assignments([work[0], work[1], work[2], work[3]], group1)
model.add_allowed_assignments([work[4], work[5], work[6], work[7]], group2)
model.add_allowed_assignments([work[8], work[9], work[10], work[11]], group3)

# Objective
objective_terms = []
for worker in range(num_workers):
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.objective_value}\n")
for worker in range(num_workers):
print(
+ f" Cost = {costs[worker][task]}"
)
else:
print("No solution found.")

if __name__ == "__main__":
main()```

### C++

```// Solve assignment problem for given group of workers.
#include <stdlib.h>

#include <cstdint>
#include <numeric>
#include <vector>

#include "absl/strings/str_format.h"
#include "absl/types/span.h"
#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 AssignmentGroups() {
// Data
const std::vector<std::vector<int>> costs = {{
{{90, 76, 75, 70, 50, 74}},
{{35, 85, 55, 65, 48, 101}},
{{125, 95, 90, 105, 59, 120}},
{{45, 110, 95, 115, 104, 83}},
{{60, 105, 80, 75, 59, 62}},
{{45, 65, 110, 95, 47, 31}},
{{38, 51, 107, 41, 69, 99}},
{{47, 85, 57, 71, 92, 77}},
{{39, 63, 97, 49, 118, 56}},
{{47, 101, 71, 60, 88, 109}},
{{17, 39, 103, 64, 61, 92}},
{{101, 45, 83, 59, 92, 27}},
}};
const int num_workers = static_cast<int>(costs.size());
std::vector<int> all_workers(num_workers);
std::iota(all_workers.begin(), all_workers.end(), 0);

const int num_tasks = static_cast<int>(costs[0].size());

// Allowed groups of workers:
const std::vector<std::vector<int64_t>> group1 = {{
{{0, 0, 1, 1}},  // Workers 2, 3
{{0, 1, 0, 1}},  // Workers 1, 3
{{0, 1, 1, 0}},  // Workers 1, 2
{{1, 1, 0, 0}},  // Workers 0, 1
{{1, 0, 1, 0}},  // Workers 0, 2
}};

const std::vector<std::vector<int64_t>> group2 = {{
{{0, 0, 1, 1}},  // Workers 6, 7
{{0, 1, 0, 1}},  // Workers 5, 7
{{0, 1, 1, 0}},  // Workers 5, 6
{{1, 1, 0, 0}},  // Workers 4, 5
{{1, 0, 0, 1}},  // Workers 4, 7
}};

const std::vector<std::vector<int64_t>> group3 = {{
{{0, 0, 1, 1}},  // Workers 10, 11
{{0, 1, 0, 1}},  // Workers 9, 11
{{0, 1, 1, 0}},  // Workers 9, 10
{{1, 0, 1, 0}},  // Workers 8, 10
{{1, 0, 0, 1}},  // Workers 8, 11
}};

// 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 worker : all_workers) {
}
}

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

// Create variables for each worker, indicating whether they work on some
std::vector<IntVar> work(num_workers);
for (int worker : all_workers) {
work[worker] = IntVar(
cp_model.NewBoolVar().WithName(absl::StrFormat("work[%d]", worker)));
}

for (int worker : all_workers) {
}
}

// Define the allowed groups of worders
auto table1 =
cp_model.AddAllowedAssignments({work[0], work[1], work[2], work[3]});
for (const auto& t : group1) {
}
auto table2 =
cp_model.AddAllowedAssignments({work[4], work[5], work[6], work[7]});
for (const auto& t : group2) {
}
auto table3 =
cp_model.AddAllowedAssignments({work[8], work[9], work[10], work[11]});
for (const auto& t : group3) {
}

// Objective
LinearExpr total_cost;
for (int worker : all_workers) {
}
}
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 worker : all_workers) {
if (SolutionBooleanValue(response, x[worker][task])) {
LOG(INFO) << "Worker " << worker << " assigned to task " << task
<< ".  Cost: " << costs[worker][task];
}
}
}
}
}  // namespace sat
}  // namespace operations_research

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

### Java

```// CP-SAT example that solves an assignment problem.
import java.util.ArrayList;
import java.util.List;
import java.util.stream.IntStream;

/** Assignment problem. */
public class AssignmentGroupsSat {
public static void main(String[] args) {
// Data
int[][] costs = {
{90, 76, 75, 70, 50, 74},
{35, 85, 55, 65, 48, 101},
{125, 95, 90, 105, 59, 120},
{45, 110, 95, 115, 104, 83},
{60, 105, 80, 75, 59, 62},
{45, 65, 110, 95, 47, 31},
{38, 51, 107, 41, 69, 99},
{47, 85, 57, 71, 92, 77},
{39, 63, 97, 49, 118, 56},
{47, 101, 71, 60, 88, 109},
{17, 39, 103, 64, 61, 92},
{101, 45, 83, 59, 92, 27},
};
final int numWorkers = costs.length;
final int numTasks = costs[0].length;

final int[] allWorkers = IntStream.range(0, numWorkers).toArray();

// Allowed groups of workers:
int[][] group1 = {
{0, 0, 1, 1}, // Workers 2, 3
{0, 1, 0, 1}, // Workers 1, 3
{0, 1, 1, 0}, // Workers 1, 2
{1, 1, 0, 0}, // Workers 0, 1
{1, 0, 1, 0}, // Workers 0, 2
};

int[][] group2 = {
{0, 0, 1, 1}, // Workers 6, 7
{0, 1, 0, 1}, // Workers 5, 7
{0, 1, 1, 0}, // Workers 5, 6
{1, 1, 0, 0}, // Workers 4, 5
{1, 0, 0, 1}, // Workers 4, 7
};

int[][] group3 = {
{0, 0, 1, 1}, // Workers 10, 11
{0, 1, 0, 1}, // Workers 9, 11
{0, 1, 1, 0}, // Workers 9, 10
{1, 0, 1, 0}, // Workers 8, 10
{1, 0, 0, 1}, // Workers 8, 11
};

// Model
CpModel model = new CpModel();

// Variables
Literal[][] x = new Literal[numWorkers][numTasks];
for (int worker : allWorkers) {
x[worker][task] = model.newBoolVar("x[" + worker + "," + task + "]");
}
}

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

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

// Create variables for each worker, indicating whether they work on some task.
IntVar[] work = new IntVar[numWorkers];
for (int worker : allWorkers) {
work[worker] = model.newBoolVar("work[" + worker + "]");
}

for (int worker : allWorkers) {
LinearExprBuilder expr = LinearExpr.newBuilder();
}
}

// Define the allowed groups of worders
model.addAllowedAssignments(new IntVar[] {work[0], work[1], work[2], work[3]})
model.addAllowedAssignments(new IntVar[] {work[4], work[5], work[6], work[7]})
model.addAllowedAssignments(new IntVar[] {work[8], work[9], work[10], work[11]})

// 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 worker : allWorkers) {
System.out.println("Worker " + worker + " assigned to task " + task
+ ".  Cost: " + costs[worker][task]);
}
}
}
} else {
System.err.println("No solution found.");
}
}

private AssignmentGroupsSat() {}
}```

### C#

```using System;
using System.Collections.Generic;
using System.Linq;

public class AssignmentGroupsSat
{
public static void Main(String[] args)
{
// Data.
int[,] costs = {
{ 90, 76, 75, 70, 50, 74 },    { 35, 85, 55, 65, 48, 101 }, { 125, 95, 90, 105, 59, 120 },
{ 45, 110, 95, 115, 104, 83 }, { 60, 105, 80, 75, 59, 62 }, { 45, 65, 110, 95, 47, 31 },
{ 38, 51, 107, 41, 69, 99 },   { 47, 85, 57, 71, 92, 77 },  { 39, 63, 97, 49, 118, 56 },
{ 47, 101, 71, 60, 88, 109 },  { 17, 39, 103, 64, 61, 92 }, { 101, 45, 83, 59, 92, 27 },
};
int numWorkers = costs.GetLength(0);
int numTasks = costs.GetLength(1);

int[] allWorkers = Enumerable.Range(0, numWorkers).ToArray();

// Allowed groups of workers:
long[,] group1 = {
{ 0, 0, 1, 1 }, // Workers 2, 3
{ 0, 1, 0, 1 }, // Workers 1, 3
{ 0, 1, 1, 0 }, // Workers 1, 2
{ 1, 1, 0, 0 }, // Workers 0, 1
{ 1, 0, 1, 0 }, // Workers 0, 2
};

long[,] group2 = {
{ 0, 0, 1, 1 }, // Workers 6, 7
{ 0, 1, 0, 1 }, // Workers 5, 7
{ 0, 1, 1, 0 }, // Workers 5, 6
{ 1, 1, 0, 0 }, // Workers 4, 5
{ 1, 0, 0, 1 }, // Workers 4, 7
};

long[,] group3 = {
{ 0, 0, 1, 1 }, // Workers 10, 11
{ 0, 1, 0, 1 }, // Workers 9, 11
{ 0, 1, 1, 0 }, // Workers 9, 10
{ 1, 0, 1, 0 }, // Workers 8, 10
{ 1, 0, 0, 1 }, // Workers 8, 11
};

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

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

// Constraints
// Each worker is assigned to at most one task.
foreach (int worker in allWorkers)
{
List<ILiteral> tasks = new List<ILiteral>();
{
}
}

// Each task is assigned to exactly one worker.
{
List<ILiteral> workers = new List<ILiteral>();
foreach (int worker in allWorkers)
{
}
}

// Create variables for each worker, indicating whether they work on some task.
BoolVar[] work = new BoolVar[numWorkers];
foreach (int worker in allWorkers)
{
work[worker] = model.NewBoolVar(\$"work[{worker}]");
}

foreach (int worker in allWorkers)
{
List<ILiteral> tasks = new List<ILiteral>();
{
}
}

// Define the allowed groups of worders
model.AddAllowedAssignments(new IntVar[] { work[0], work[1], work[2], work[3] }).AddTuples(group1);
model.AddAllowedAssignments(new IntVar[] { work[4], work[5], work[6], work[7] }).AddTuples(group2);
model.AddAllowedAssignments(new IntVar[] { work[8], work[9], work[10], work[11] }).AddTuples(group3);

// Objective
LinearExprBuilder obj = LinearExpr.NewBuilder();
foreach (int worker in allWorkers)
{
{
}
}
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");
foreach (int worker in allWorkers)
{
{
if (solver.Value(x[worker, task]) > 0.5)
{
Console.WriteLine(\$"Worker {worker} assigned to task {task}. " +
}
}
}
}
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");
}
}```

## MIP solution

Next, we describe a solution to the problem using the MIP solver.

### Import the libraries

The following code imports the required library.

### Python

`from ortools.linear_solver import pywraplp`

### C++

```#include <cstdint>
#include <memory>
#include <numeric>
#include <utility>
#include <vector>

#include "absl/strings/str_format.h"
#include "ortools/base/logging.h"
#include "ortools/linear_solver/linear_solver.h"```

### Java

```import com.google.ortools.Loader;
import java.util.stream.IntStream;```

### C#

```using System;
using System.Collections.Generic;
using System.Linq;

### Define the data

The following code creates the data for the program.

### Python

```costs = [
[90, 76, 75, 70, 50, 74],
[35, 85, 55, 65, 48, 101],
[125, 95, 90, 105, 59, 120],
[45, 110, 95, 115, 104, 83],
[60, 105, 80, 75, 59, 62],
[45, 65, 110, 95, 47, 31],
[38, 51, 107, 41, 69, 99],
[47, 85, 57, 71, 92, 77],
[39, 63, 97, 49, 118, 56],
[47, 101, 71, 60, 88, 109],
[17, 39, 103, 64, 61, 92],
[101, 45, 83, 59, 92, 27],
]
num_workers = len(costs)

### C++

```const std::vector<std::vector<int64_t>> costs = {{
{{90, 76, 75, 70, 50, 74}},
{{35, 85, 55, 65, 48, 101}},
{{125, 95, 90, 105, 59, 120}},
{{45, 110, 95, 115, 104, 83}},
{{60, 105, 80, 75, 59, 62}},
{{45, 65, 110, 95, 47, 31}},
{{38, 51, 107, 41, 69, 99}},
{{47, 85, 57, 71, 92, 77}},
{{39, 63, 97, 49, 118, 56}},
{{47, 101, 71, 60, 88, 109}},
{{17, 39, 103, 64, 61, 92}},
{{101, 45, 83, 59, 92, 27}},
}};
const int num_workers = costs.size();
std::vector<int> all_workers(num_workers);
std::iota(all_workers.begin(), all_workers.end(), 0);

const int num_tasks = costs[0].size();

### Java

```double[][] costs = {
{90, 76, 75, 70, 50, 74},
{35, 85, 55, 65, 48, 101},
{125, 95, 90, 105, 59, 120},
{45, 110, 95, 115, 104, 83},
{60, 105, 80, 75, 59, 62},
{45, 65, 110, 95, 47, 31},
{38, 51, 107, 41, 69, 99},
{47, 85, 57, 71, 92, 77},
{39, 63, 97, 49, 118, 56},
{47, 101, 71, 60, 88, 109},
{17, 39, 103, 64, 61, 92},
{101, 45, 83, 59, 92, 27},
};
int numWorkers = costs.length;
int numTasks = costs[0].length;

final int[] allWorkers = IntStream.range(0, numWorkers).toArray();

### C#

```int[,] costs = {
{ 90, 76, 75, 70, 50, 74 },    { 35, 85, 55, 65, 48, 101 }, { 125, 95, 90, 105, 59, 120 },
{ 45, 110, 95, 115, 104, 83 }, { 60, 105, 80, 75, 59, 62 }, { 45, 65, 110, 95, 47, 31 },
{ 38, 51, 107, 41, 69, 99 },   { 47, 85, 57, 71, 92, 77 },  { 39, 63, 97, 49, 118, 56 },
{ 47, 101, 71, 60, 88, 109 },  { 17, 39, 103, 64, 61, 92 }, { 101, 45, 83, 59, 92, 27 },
};
int numWorkers = costs.GetLength(0);
int numTasks = costs.GetLength(1);

int[] allWorkers = Enumerable.Range(0, numWorkers).ToArray();

### Create the allowed groups

The following code creates the allowed groups, by looping through the three sets of subgroups shown above.

### Python

```group1 = [  # Subgroups of workers 0 - 3
[2, 3],
[1, 3],
[1, 2],
[0, 1],
[0, 2],
]

group2 = [  # Subgroups of workers 4 - 7
[6, 7],
[5, 7],
[5, 6],
[4, 5],
[4, 7],
]

group3 = [  # Subgroups of workers 8 - 11
[10, 11],
[9, 11],
[9, 10],
[8, 10],
[8, 11],
]```

### C++

```using WorkerIndex = int;
using Binome = std::pair<WorkerIndex, WorkerIndex>;
using AllowedBinomes = std::vector<Binome>;
const AllowedBinomes group1 = {{
// group of worker 0-3
{2, 3},
{1, 3},
{1, 2},
{0, 1},
{0, 2},
}};

const AllowedBinomes group2 = {{
// group of worker 4-7
{6, 7},
{5, 7},
{5, 6},
{4, 5},
{4, 7},
}};

const AllowedBinomes group3 = {{
// group of worker 8-11
{10, 11},
{9, 11},
{9, 10},
{8, 10},
{8, 11},
}};```

### Java

```int[][] group1 = {
// group of worker 0-3
{2, 3},
{1, 3},
{1, 2},
{0, 1},
{0, 2},
};

int[][] group2 = {
// group of worker 4-7
{6, 7},
{5, 7},
{5, 6},
{4, 5},
{4, 7},
};

int[][] group3 = {
// group of worker 8-11
{10, 11},
{9, 11},
{9, 10},
{8, 10},
{8, 11},
};```

### C#

```int[,] group1 = {
// group of worker 0-3
{ 2, 3 }, { 1, 3 }, { 1, 2 }, { 0, 1 }, { 0, 2 },
};

int[,] group2 = {
// group of worker 4-7
{ 6, 7 }, { 5, 7 }, { 5, 6 }, { 4, 5 }, { 4, 7 },
};

int[,] group3 = {
// group of worker 8-11
{ 10, 11 }, { 9, 11 }, { 9, 10 }, { 8, 10 }, { 8, 11 },
};```

### Declare the solver

The following code creates the 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 an array of variables for the problem.

### Python

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

### 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 worker : all_workers) {
}
}```

### 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 worker : allWorkers) {
x[worker][task] = solver.makeBoolVar("x[" + worker + "," + task + "]");
}
}```

### 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];
foreach (int worker in allWorkers)
{
{
}
}```

### Add the constraints

The following code creates the constraints for the program.

### Python

```# The total size of the tasks each worker takes on is at most total_size_max.
for worker in range(num_workers):

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

### C++

```// Each worker is assigned to at most one task.
for (int worker : all_workers) {
LinearExpr worker_sum;
}
solver->MakeRowConstraint(worker_sum <= 1.0);
}
// Each task is assigned to exactly one worker.
for (int worker : all_workers) {
}
}```

### Java

```// Each worker is assigned to at most one task.
for (int worker : allWorkers) {
MPConstraint constraint = solver.makeConstraint(0, 1, "");
}
}
// Each task is assigned to exactly one worker.
MPConstraint constraint = solver.makeConstraint(1, 1, "");
for (int worker : allWorkers) {
}
}```

### C#

```// Each worker is assigned to at most one task.
foreach (int worker in allWorkers)
{
Constraint constraint = solver.MakeConstraint(0, 1, "");
{
}
}
// Each task is assigned to exactly one worker.
{
Constraint constraint = solver.MakeConstraint(1, 1, "");
foreach (int worker in allWorkers)
{
}
}```

### Create the objective

The following code creates the objective function.

### Python

```objective_terms = []
for worker in range(num_workers):
solver.Minimize(solver.Sum(objective_terms))```

### C++

```MPObjective* const objective = solver->MutableObjective();
for (int worker : all_workers) {
}
}
objective->SetMinimization();```

### Java

```MPObjective objective = solver.objective();
for (int worker : allWorkers) {
}
}
objective.setMinimization();```

### C#

```Objective objective = solver.Objective();
foreach (int worker in allWorkers)
{
{
}
}
objective.SetMinimization();```

### Invoke the solver

The following code invokes the solver and displays the results.

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

### Display the results

Now, we can print the solution.

### Python

```if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE:
print(f"Total cost = {solver.Objective().Value()}\n")
for worker in range(num_workers):
if x[worker, task].solution_value() > 0.5:
print(
+ f" Cost: {costs[worker][task]}"
)
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 worker : all_workers) {
// Test if x[i][j] is 0 or 1 (with tolerance for floating point
// arithmetic).
if (x[worker][task]->solution_value() > 0.5) {
LOG(INFO) << "Worker " << worker << " assigned to task " << task
<< ".  Cost: " << costs[worker][task];
}
}
}```

### 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 worker : allWorkers) {
// Test if x[i][j] is 0 or 1 (with tolerance for floating point
// arithmetic).
if (x[worker][task].solutionValue() > 0.5) {
System.out.println("Worker " + worker + " assigned to task " + task
+ ".  Cost: " + costs[worker][task]);
}
}
}
} 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");
foreach (int worker in allWorkers)
{
{
// Test if x[i, j] is 0 or 1 (with tolerance for floating point
// arithmetic).
if (x[worker, task].SolutionValue() > 0.5)
{
}
}
}
}
else
{
Console.WriteLine("No solution found.");
}```

Here's the output of the program:

```Minimum cost =  239.0

Worker 0  assigned to task 4   Cost =  50
Worker 1  assigned to task 2   Cost =  55
Worker 5  assigned to task 5   Cost =  31
Worker 6  assigned to task 3   Cost =  41
Worker 10  assigned to task 0   Cost =  17
Worker 11  assigned to task 1   Cost =  45

Time =  0.3281 seconds```

### The entire program

Here is the entire program.

### Python

```"""Solve assignment problem for given group of workers."""
from ortools.linear_solver import pywraplp

def main():
# Data
costs = [
[90, 76, 75, 70, 50, 74],
[35, 85, 55, 65, 48, 101],
[125, 95, 90, 105, 59, 120],
[45, 110, 95, 115, 104, 83],
[60, 105, 80, 75, 59, 62],
[45, 65, 110, 95, 47, 31],
[38, 51, 107, 41, 69, 99],
[47, 85, 57, 71, 92, 77],
[39, 63, 97, 49, 118, 56],
[47, 101, 71, 60, 88, 109],
[17, 39, 103, 64, 61, 92],
[101, 45, 83, 59, 92, 27],
]
num_workers = len(costs)

# Allowed groups of workers:
group1 = [  # Subgroups of workers 0 - 3
[2, 3],
[1, 3],
[1, 2],
[0, 1],
[0, 2],
]

group2 = [  # Subgroups of workers 4 - 7
[6, 7],
[5, 7],
[5, 6],
[4, 5],
[4, 7],
]

group3 = [  # Subgroups of workers 8 - 11
[10, 11],
[9, 11],
[9, 10],
[8, 10],
[8, 11],
]

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

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

# Constraints
# The total size of the tasks each worker takes on is at most total_size_max.
for worker in range(num_workers):

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

# Create variables for each worker, indicating whether they work on some task.
work = {}
for worker in range(num_workers):
work[worker] = solver.BoolVar(f"work[{worker}]")

for worker in range(num_workers):
)

# Group1
constraint_g1 = solver.Constraint(1, 1)
for index, _ in enumerate(group1):
# a*b can be transformed into 0 <= a + b - 2*p <= 1 with p in [0,1]
# p is True if a AND b, False otherwise
constraint = solver.Constraint(0, 1)
constraint.SetCoefficient(work[group1[index][0]], 1)
constraint.SetCoefficient(work[group1[index][1]], 1)
p = solver.BoolVar(f"g1_p{index}")
constraint.SetCoefficient(p, -2)

constraint_g1.SetCoefficient(p, 1)

# Group2
constraint_g2 = solver.Constraint(1, 1)
for index, _ in enumerate(group2):
# a*b can be transformed into 0 <= a + b - 2*p <= 1 with p in [0,1]
# p is True if a AND b, False otherwise
constraint = solver.Constraint(0, 1)
constraint.SetCoefficient(work[group2[index][0]], 1)
constraint.SetCoefficient(work[group2[index][1]], 1)
p = solver.BoolVar(f"g2_p{index}")
constraint.SetCoefficient(p, -2)

constraint_g2.SetCoefficient(p, 1)

# Group3
constraint_g3 = solver.Constraint(1, 1)
for index, _ in enumerate(group3):
# a*b can be transformed into 0 <= a + b - 2*p <= 1 with p in [0,1]
# p is True if a AND b, False otherwise
constraint = solver.Constraint(0, 1)
constraint.SetCoefficient(work[group3[index][0]], 1)
constraint.SetCoefficient(work[group3[index][1]], 1)
p = solver.BoolVar(f"g3_p{index}")
constraint.SetCoefficient(p, -2)

constraint_g3.SetCoefficient(p, 1)

# Objective
objective_terms = []
for worker in range(num_workers):
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 worker in range(num_workers):
if x[worker, task].solution_value() > 0.5:
print(
+ f" Cost: {costs[worker][task]}"
)
else:
print("No solution found.")

if __name__ == "__main__":
main()```

### C++

```// Solve a simple assignment problem.
#include <cstdint>
#include <memory>
#include <numeric>
#include <utility>
#include <vector>

#include "absl/strings/str_format.h"
#include "ortools/base/logging.h"
#include "ortools/linear_solver/linear_solver.h"

namespace operations_research {
void AssignmentTeamsMip() {
// Data
const std::vector<std::vector<int64_t>> costs = {{
{{90, 76, 75, 70, 50, 74}},
{{35, 85, 55, 65, 48, 101}},
{{125, 95, 90, 105, 59, 120}},
{{45, 110, 95, 115, 104, 83}},
{{60, 105, 80, 75, 59, 62}},
{{45, 65, 110, 95, 47, 31}},
{{38, 51, 107, 41, 69, 99}},
{{47, 85, 57, 71, 92, 77}},
{{39, 63, 97, 49, 118, 56}},
{{47, 101, 71, 60, 88, 109}},
{{17, 39, 103, 64, 61, 92}},
{{101, 45, 83, 59, 92, 27}},
}};
const int num_workers = costs.size();
std::vector<int> all_workers(num_workers);
std::iota(all_workers.begin(), all_workers.end(), 0);

const int num_tasks = costs[0].size();

// Allowed groups of workers:
using WorkerIndex = int;
using Binome = std::pair<WorkerIndex, WorkerIndex>;
using AllowedBinomes = std::vector<Binome>;
const AllowedBinomes group1 = {{
// group of worker 0-3
{2, 3},
{1, 3},
{1, 2},
{0, 1},
{0, 2},
}};

const AllowedBinomes group2 = {{
// group of worker 4-7
{6, 7},
{5, 7},
{5, 6},
{4, 5},
{4, 7},
}};

const AllowedBinomes group3 = {{
// group of worker 8-11
{10, 11},
{9, 11},
{9, 10},
{8, 10},
{8, 11},
}};

// 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 worker : all_workers) {
}
}

// Constraints
// Each worker is assigned to at most one task.
for (int worker : all_workers) {
LinearExpr worker_sum;
}
solver->MakeRowConstraint(worker_sum <= 1.0);
}
// Each task is assigned to exactly one worker.
for (int worker : all_workers) {
}
}

// Create variables for each worker, indicating whether they work on some
std::vector<const MPVariable*> work(num_workers);
for (int worker : all_workers) {
work[worker] = solver->MakeBoolVar(absl::StrFormat("work[%d]", worker));
}

for (int worker : all_workers) {
}
}

// Group1
{
MPConstraint* g1 = solver->MakeRowConstraint(1, 1);
for (int i = 0; i < group1.size(); ++i) {
// a*b can be transformed into 0 <= a + b - 2*p <= 1 with p in [0,1]
// p is true if a AND b, false otherwise
MPConstraint* tmp = solver->MakeRowConstraint(0, 1);
tmp->SetCoefficient(work[group1[i].first], 1);
tmp->SetCoefficient(work[group1[i].second], 1);
MPVariable* p = solver->MakeBoolVar(absl::StrFormat("g1_p%d", i));
tmp->SetCoefficient(p, -2);

g1->SetCoefficient(p, 1);
}
}
// Group2
{
MPConstraint* g2 = solver->MakeRowConstraint(1, 1);
for (int i = 0; i < group2.size(); ++i) {
// a*b can be transformed into 0 <= a + b - 2*p <= 1 with p in [0,1]
// p is true if a AND b, false otherwise
MPConstraint* tmp = solver->MakeRowConstraint(0, 1);
tmp->SetCoefficient(work[group2[i].first], 1);
tmp->SetCoefficient(work[group2[i].second], 1);
MPVariable* p = solver->MakeBoolVar(absl::StrFormat("g2_p%d", i));
tmp->SetCoefficient(p, -2);

g2->SetCoefficient(p, 1);
}
}
// Group3
{
MPConstraint* g3 = solver->MakeRowConstraint(1, 1);
for (int i = 0; i < group3.size(); ++i) {
// a*b can be transformed into 0 <= a + b - 2*p <= 1 with p in [0,1]
// p is true if a AND b, false otherwise
MPConstraint* tmp = solver->MakeRowConstraint(0, 1);
tmp->SetCoefficient(work[group3[i].first], 1);
tmp->SetCoefficient(work[group3[i].second], 1);
MPVariable* p = solver->MakeBoolVar(absl::StrFormat("g3_p%d", i));
tmp->SetCoefficient(p, -2);

g3->SetCoefficient(p, 1);
}
}

// Objective.
MPObjective* const objective = solver->MutableObjective();
for (int worker : all_workers) {
}
}
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 worker : all_workers) {
// Test if x[i][j] is 0 or 1 (with tolerance for floating point
// arithmetic).
if (x[worker][task]->solution_value() > 0.5) {
LOG(INFO) << "Worker " << worker << " assigned to task " << task
<< ".  Cost: " << costs[worker][task];
}
}
}
}
}  // namespace operations_research

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

### Java

```package com.google.ortools.linearsolver.samples;
import java.util.stream.IntStream;

/** MIP example that solves an assignment problem. */
public class AssignmentGroupsMip {
public static void main(String[] args) {
// Data
double[][] costs = {
{90, 76, 75, 70, 50, 74},
{35, 85, 55, 65, 48, 101},
{125, 95, 90, 105, 59, 120},
{45, 110, 95, 115, 104, 83},
{60, 105, 80, 75, 59, 62},
{45, 65, 110, 95, 47, 31},
{38, 51, 107, 41, 69, 99},
{47, 85, 57, 71, 92, 77},
{39, 63, 97, 49, 118, 56},
{47, 101, 71, 60, 88, 109},
{17, 39, 103, 64, 61, 92},
{101, 45, 83, 59, 92, 27},
};
int numWorkers = costs.length;
int numTasks = costs[0].length;

final int[] allWorkers = IntStream.range(0, numWorkers).toArray();

// Allowed groups of workers:
int[][] group1 = {
// group of worker 0-3
{2, 3},
{1, 3},
{1, 2},
{0, 1},
{0, 2},
};

int[][] group2 = {
// group of worker 4-7
{6, 7},
{5, 7},
{5, 6},
{4, 5},
{4, 7},
};

int[][] group3 = {
// group of worker 8-11
{10, 11},
{9, 11},
{9, 10},
{8, 10},
{8, 11},
};

// 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 worker : allWorkers) {
x[worker][task] = solver.makeBoolVar("x[" + worker + "," + task + "]");
}
}

// Constraints
// Each worker is assigned to at most one task.
for (int worker : allWorkers) {
MPConstraint constraint = solver.makeConstraint(0, 1, "");
}
}
// Each task is assigned to exactly one worker.
MPConstraint constraint = solver.makeConstraint(1, 1, "");
for (int worker : allWorkers) {
}
}

// Create variables for each worker, indicating whether they work on some task.
MPVariable[] work = new MPVariable[numWorkers];
for (int worker : allWorkers) {
work[worker] = solver.makeBoolVar("work[" + worker + "]");
}

for (int worker : allWorkers) {
// MPVariable[] vars = new MPVariable[numTasks];
MPConstraint constraint = solver.makeConstraint(0, 0, "");
}
constraint.setCoefficient(work[worker], -1);
}

// Group1
MPConstraint constraintG1 = solver.makeConstraint(1, 1, "");
for (int i = 0; i < group1.length; ++i) {
// a*b can be transformed into 0 <= a + b - 2*p <= 1 with p in [0,1]
// p is True if a AND b, False otherwise
MPConstraint constraint = solver.makeConstraint(0, 1, "");
constraint.setCoefficient(work[group1[i][0]], 1);
constraint.setCoefficient(work[group1[i][1]], 1);
MPVariable p = solver.makeBoolVar("g1_p" + i);
constraint.setCoefficient(p, -2);

constraintG1.setCoefficient(p, 1);
}
// Group2
MPConstraint constraintG2 = solver.makeConstraint(1, 1, "");
for (int i = 0; i < group2.length; ++i) {
// a*b can be transformed into 0 <= a + b - 2*p <= 1 with p in [0,1]
// p is True if a AND b, False otherwise
MPConstraint constraint = solver.makeConstraint(0, 1, "");
constraint.setCoefficient(work[group2[i][0]], 1);
constraint.setCoefficient(work[group2[i][1]], 1);
MPVariable p = solver.makeBoolVar("g2_p" + i);
constraint.setCoefficient(p, -2);

constraintG2.setCoefficient(p, 1);
}
// Group3
MPConstraint constraintG3 = solver.makeConstraint(1, 1, "");
for (int i = 0; i < group3.length; ++i) {
// a*b can be transformed into 0 <= a + b - 2*p <= 1 with p in [0,1]
// p is True if a AND b, False otherwise
MPConstraint constraint = solver.makeConstraint(0, 1, "");
constraint.setCoefficient(work[group3[i][0]], 1);
constraint.setCoefficient(work[group3[i][1]], 1);
MPVariable p = solver.makeBoolVar("g3_p" + i);
constraint.setCoefficient(p, -2);

constraintG3.setCoefficient(p, 1);
}

// Objective
MPObjective objective = solver.objective();
for (int worker : allWorkers) {
}
}
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 worker : allWorkers) {
// Test if x[i][j] is 0 or 1 (with tolerance for floating point
// arithmetic).
if (x[worker][task].solutionValue() > 0.5) {
System.out.println("Worker " + worker + " assigned to task " + task
+ ".  Cost: " + costs[worker][task]);
}
}
}
} else {
System.err.println("No solution found.");
}
}

private AssignmentGroupsMip() {}
}```

### C#

```using System;
using System.Collections.Generic;
using System.Linq;

public class AssignmentGroupsMip
{
static void Main()
{
// Data.
int[,] costs = {
{ 90, 76, 75, 70, 50, 74 },    { 35, 85, 55, 65, 48, 101 }, { 125, 95, 90, 105, 59, 120 },
{ 45, 110, 95, 115, 104, 83 }, { 60, 105, 80, 75, 59, 62 }, { 45, 65, 110, 95, 47, 31 },
{ 38, 51, 107, 41, 69, 99 },   { 47, 85, 57, 71, 92, 77 },  { 39, 63, 97, 49, 118, 56 },
{ 47, 101, 71, 60, 88, 109 },  { 17, 39, 103, 64, 61, 92 }, { 101, 45, 83, 59, 92, 27 },
};
int numWorkers = costs.GetLength(0);
int numTasks = costs.GetLength(1);

int[] allWorkers = Enumerable.Range(0, numWorkers).ToArray();

// Allowed groups of workers:
int[,] group1 = {
// group of worker 0-3
{ 2, 3 }, { 1, 3 }, { 1, 2 }, { 0, 1 }, { 0, 2 },
};

int[,] group2 = {
// group of worker 4-7
{ 6, 7 }, { 5, 7 }, { 5, 6 }, { 4, 5 }, { 4, 7 },
};

int[,] group3 = {
// group of worker 8-11
{ 10, 11 }, { 9, 11 }, { 9, 10 }, { 8, 10 }, { 8, 11 },
};

// 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];
foreach (int worker in allWorkers)
{
{
}
}

// Constraints
// Each worker is assigned to at most one task.
foreach (int worker in allWorkers)
{
Constraint constraint = solver.MakeConstraint(0, 1, "");
{
}
}
// Each task is assigned to exactly one worker.
{
Constraint constraint = solver.MakeConstraint(1, 1, "");
foreach (int worker in allWorkers)
{
}
}

// Create variables for each worker, indicating whether they work on some task.
Variable[] work = new Variable[numWorkers];
foreach (int worker in allWorkers)
{
work[worker] = solver.MakeBoolVar(\$"work[{worker}]");
}

foreach (int worker in allWorkers)
{
Variable[] vars = new Variable[numTasks];
{
}
}

// Group1
Constraint constraint_g1 = solver.MakeConstraint(1, 1, "");
for (int i = 0; i < group1.GetLength(0); ++i)
{
// a*b can be transformed into 0 <= a + b - 2*p <= 1 with p in [0,1]
// p is True if a AND b, False otherwise
Constraint constraint = solver.MakeConstraint(0, 1, "");
constraint.SetCoefficient(work[group1[i, 0]], 1);
constraint.SetCoefficient(work[group1[i, 1]], 1);
Variable p = solver.MakeBoolVar(\$"g1_p{i}");
constraint.SetCoefficient(p, -2);

constraint_g1.SetCoefficient(p, 1);
}
// Group2
Constraint constraint_g2 = solver.MakeConstraint(1, 1, "");
for (int i = 0; i < group2.GetLength(0); ++i)
{
// a*b can be transformed into 0 <= a + b - 2*p <= 1 with p in [0,1]
// p is True if a AND b, False otherwise
Constraint constraint = solver.MakeConstraint(0, 1, "");
constraint.SetCoefficient(work[group2[i, 0]], 1);
constraint.SetCoefficient(work[group2[i, 1]], 1);
Variable p = solver.MakeBoolVar(\$"g2_p{i}");
constraint.SetCoefficient(p, -2);

constraint_g2.SetCoefficient(p, 1);
}
// Group3
Constraint constraint_g3 = solver.MakeConstraint(1, 1, "");
for (int i = 0; i < group3.GetLength(0); ++i)
{
// a*b can be transformed into 0 <= a + b - 2*p <= 1 with p in [0,1]
// p is True if a AND b, False otherwise
Constraint constraint = solver.MakeConstraint(0, 1, "");
constraint.SetCoefficient(work[group3[i, 0]], 1);
constraint.SetCoefficient(work[group3[i, 1]], 1);
Variable p = solver.MakeBoolVar(\$"g3_p{i}");
constraint.SetCoefficient(p, -2);

constraint_g3.SetCoefficient(p, 1);
}

// Objective
Objective objective = solver.Objective();
foreach (int worker in allWorkers)
{
{
}
}
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");
foreach (int worker in allWorkers)
{
{
// Test if x[i, j] is 0 or 1 (with tolerance for floating point
// arithmetic).
if (x[worker, task].SolutionValue() > 0.5)
{
}
}
}
}
else
{
Console.WriteLine("No solution found.");
}
}
}```

## Solutions times

The solution times for the two solvers are as follows:

• CP-SAT: 0.0113 seconds
• MIP: 0.3281 seconds

CP-SAT is significantly faster than MIP for this problem.

[{ "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" }]
{ "lastModified": "Last updated 2024-08-28 UTC.", "confidential": False }