In diesem Abschnitt wird ein Zuweisungsproblem beschrieben, bei dem nur bestimmte zulässige Gruppen von Workern den Aufgaben zugewiesen werden können. Im Beispiel gibt es zwölf Worker, von 0 bis 11 nummeriert. Die zulässigen Gruppen sind Kombinationen der folgenden Worker-Paare:
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]]
Eine zulässige Gruppe kann eine beliebige Kombination aus drei Worker-Paaren, jeweils ein Paar aus Gruppe1, Gruppe2 und Gruppe3, sein.
Wenn Sie beispielsweise [2, 3], [6, 7] und [10, 11] kombinieren, wird die zulässige Gruppe [2, 3, 6, 7, 10, 11] erstellt.
Da jedes der drei Sets fünf Elemente enthält, sind insgesamt 5 * 5 * 5 = 125 Gruppen zulässig.
Beachten Sie, dass eine Gruppe von Workern eine Lösung für das Problem sein kann, wenn sie zu einer der zulässigen Gruppen gehört. Mit anderen Worten, der zulässige Satz besteht aus Punkten, für die eine der Einschränkungen erfüllt ist. Dies ist ein Beispiel für ein nicht konvexes Problem. Im Gegensatz dazu ist das zuvor beschriebene MIP-Beispiel ein konvexes Problem: Damit ein Punkt realisierbar ist, müssen alle Einschränkungen erfüllt sein.
Bei nicht konvexen Problemen wie diesem ist der CP-SAT-Resolver normalerweise schneller als ein MIP-Resolver. In den folgenden Abschnitten werden Lösungen für das Problem mit dem CP-SAT-Rechner und dem MIP-Beheber vorgestellt. Außerdem werden die Lösungszeiten für die beiden Solver verglichen.
CP-SAT-Lösung
Zuerst beschreiben wir eine Lösung für das Problem mithilfe des CP-SAT-Rechners.
Bibliotheken importieren
Mit dem folgenden Code wird die erforderliche Bibliothek importiert.
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 com.google.ortools.sat.CpModel; import com.google.ortools.sat.CpSolver; import com.google.ortools.sat.CpSolverStatus; import com.google.ortools.sat.IntVar; import com.google.ortools.sat.LinearExpr; import com.google.ortools.sat.LinearExprBuilder; import com.google.ortools.sat.Literal; import java.util.ArrayList; import java.util.List; import java.util.stream.IntStream;
C#
using System; using System.Collections.Generic; using System.Linq; using Google.OrTools.Sat;
Daten definieren
Mit dem folgenden Code werden die Daten für das Programm erstellt.
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)
num_tasks = len(costs[0])
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());
std::vector<int> all_tasks(num_tasks);
std::iota(all_tasks.begin(), all_tasks.end(), 0);
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();
final int[] allTasks = IntStream.range(0, numTasks).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();
int[] allTasks = Enumerable.Range(0, numTasks).ToArray();
Zulässige Gruppen erstellen
Zum Definieren der zulässigen Gruppen von Workern für den CP-SAT-Resolver erstellen Sie binäre Arrays, die angeben, welche Worker zu einer Gruppe gehören. Für group1 (Worker 0–3) gibt beispielsweise der Binärvektor [0, 0, 1, 1] die Gruppe mit den Workern 2 und 3 an.
Die folgenden Arrays definieren die zulässigen Gruppen von Workern.
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
};
Für CP-SAT ist es nicht erforderlich, alle 125 Kombinationen dieser Vektoren in einer Schleife zu erstellen. Der CP-SAT-Rechner bietet die Methode AllowedAssignments, mit der Sie die Einschränkungen für die zulässigen Gruppen für jede der drei Gruppen von Workern (0–3, 4–7 und 8–11) separat angeben können.
So funktionierts:
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):
for task in range(num_tasks):
model.add(work[worker] == sum(x[worker, task] for task in range(num_tasks)))
# 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
// task.
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) {
LinearExpr task_sum;
for (int task : all_tasks) {
task_sum += x[worker][task];
}
cp_model.AddEquality(work[worker], task_sum);
}
// Define the allowed groups of worders
auto table1 =
cp_model.AddAllowedAssignments({work[0], work[1], work[2], work[3]});
for (const auto& t : group1) {
table1.AddTuple(t);
}
auto table2 =
cp_model.AddAllowedAssignments({work[4], work[5], work[6], work[7]});
for (const auto& t : group2) {
table2.AddTuple(t);
}
auto table3 =
cp_model.AddAllowedAssignments({work[8], work[9], work[10], work[11]});
for (const auto& t : group3) {
table3.AddTuple(t);
}
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();
for (int task : allTasks) {
expr.add(x[worker][task]);
}
model.addEquality(work[worker], expr);
}
// 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);
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>();
foreach (int task in allTasks)
{
tasks.Add(x[worker, task]);
}
model.Add(work[worker] == LinearExpr.Sum(tasks));
}
// 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);
Die Variablen work[i] sind 0–1-Variablen, die den Arbeitsstatus oder die einzelnen Worker angeben. Das heißt, work[i] ist gleich 1, wenn Worker i einer Aufgabe zugewiesen ist, andernfalls ist 0. Die Zeile solver.Add(solver.AllowedAssignments([work[0], work[1], work[2], work[3]], group1)) definiert die Einschränkung, dass der Arbeitsstatus der Worker 0 bis 3 einem der Muster in group1 entsprechen muss. Die vollständigen Details des Codes finden Sie im nächsten Abschnitt.
Modell erstellen
Mit dem folgenden Code wird das Modell erstellt.
Python
model = cp_model.CpModel()
C++
CpModelBuilder cp_model;
Java
CpModel model = new CpModel();
C#
CpModel model = new CpModel();
Variablen erstellen
Mit dem folgenden Code wird ein Array von Variablen für das Problem erstellt.
Python
x = {}
for worker in range(num_workers):
for task in range(num_tasks):
x[worker, task] = model.new_bool_var(f"x[{worker},{task}]")
C++
// x[i][j] is an array of Boolean variables. x[i][j] is true
// if worker i is assigned to task j.
std::vector<std::vector<BoolVar>> x(num_workers,
std::vector<BoolVar>(num_tasks));
for (int worker : all_workers) {
for (int task : all_tasks) {
x[worker][task] = cp_model.NewBoolVar().WithName(
absl::StrFormat("x[%d,%d]", worker, task));
}
}
Java
Literal[][] x = new Literal[numWorkers][numTasks];
for (int worker : allWorkers) {
for (int task : allTasks) {
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)
{
foreach (int task in allTasks)
{
x[worker, task] = model.NewBoolVar($"x[{worker},{task}]");
}
}
Einschränkungen hinzufügen
Mit dem folgenden Code werden die Einschränkungen für das Programm erstellt.
Python
# Each worker is assigned to at most one task.
for worker in range(num_workers):
model.add_at_most_one(x[worker, task] for task in range(num_tasks))
# Each task is assigned to exactly one worker.
for task in range(num_tasks):
model.add_exactly_one(x[worker, task] for worker in range(num_workers))
C++
// Each worker is assigned to at most one task.
for (int worker : all_workers) {
cp_model.AddAtMostOne(x[worker]);
}
// Each task is assigned to exactly one worker.
for (int task : all_tasks) {
std::vector<BoolVar> tasks;
for (int worker : all_workers) {
tasks.push_back(x[worker][task]);
}
cp_model.AddExactlyOne(tasks);
}
Java
// Each worker is assigned to at most one task.
for (int worker : allWorkers) {
List<Literal> tasks = new ArrayList<>();
for (int task : allTasks) {
tasks.add(x[worker][task]);
}
model.addAtMostOne(tasks);
}
// Each task is assigned to exactly one worker.
for (int task : allTasks) {
List<Literal> workers = new ArrayList<>();
for (int worker : allWorkers) {
workers.add(x[worker][task]);
}
model.addExactlyOne(workers);
}
C#
// Each worker is assigned to at most one task.
foreach (int worker in allWorkers)
{
List<ILiteral> tasks = new List<ILiteral>();
foreach (int task in allTasks)
{
tasks.Add(x[worker, task]);
}
model.AddAtMostOne(tasks);
}
// Each task is assigned to exactly one worker.
foreach (int task in allTasks)
{
List<ILiteral> workers = new List<ILiteral>();
foreach (int worker in allWorkers)
{
workers.Add(x[worker, task]);
}
model.AddExactlyOne(workers);
}
Ziel erstellen
Mit dem folgenden Code wird die Zielfunktion erstellt.
Python
objective_terms = []
for worker in range(num_workers):
for task in range(num_tasks):
objective_terms.append(costs[worker][task] * x[worker, task])
model.minimize(sum(objective_terms))
C++
LinearExpr total_cost;
for (int worker : all_workers) {
for (int task : all_tasks) {
total_cost += x[worker][task] * costs[worker][task];
}
}
cp_model.Minimize(total_cost);
Java
LinearExprBuilder obj = LinearExpr.newBuilder();
for (int worker : allWorkers) {
for (int task : allTasks) {
obj.addTerm(x[worker][task], costs[worker][task]);
}
}
model.minimize(obj);
C#
LinearExprBuilder obj = LinearExpr.NewBuilder();
foreach (int worker in allWorkers)
{
foreach (int task in allTasks)
{
obj.AddTerm(x[worker, task], costs[worker, task]);
}
}
model.Minimize(obj);
Den Solver aufrufen
Der folgende Code ruft den Solver auf und zeigt die Ergebnisse an.
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}");
Ergebnisse anzeigen
Jetzt können wir die Lösung ausdrucken.
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):
for task in range(num_tasks):
if solver.boolean_value(x[worker, task]):
print(
f"Worker {worker} assigned to task {task}."
+ 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) {
for (int task : all_tasks) {
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) {
for (int task : allTasks) {
if (solver.booleanValue(x[worker][task])) {
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)
{
foreach (int task in allTasks)
{
if (solver.Value(x[worker, task]) > 0.5)
{
Console.WriteLine($"Worker {worker} assigned to task {task}. " +
$"Cost: {costs[worker, task]}");
}
}
}
}
else
{
Console.WriteLine("No solution found.");
}
Hier ist die Ausgabe des Programms.
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
Das gesamte Programm
Hier ist das gesamte Programm.
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)
num_tasks = len(costs[0])
# 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):
for task in range(num_tasks):
x[worker, task] = model.new_bool_var(f"x[{worker},{task}]")
# Constraints
# Each worker is assigned to at most one task.
for worker in range(num_workers):
model.add_at_most_one(x[worker, task] for task in range(num_tasks))
# Each task is assigned to exactly one worker.
for task in range(num_tasks):
model.add_exactly_one(x[worker, task] for worker in range(num_workers))
# 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):
for task in range(num_tasks):
model.add(work[worker] == sum(x[worker, task] for task in range(num_tasks)))
# 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):
for task in range(num_tasks):
objective_terms.append(costs[worker][task] * x[worker, task])
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):
for task in range(num_tasks):
if solver.boolean_value(x[worker, task]):
print(
f"Worker {worker} assigned to task {task}."
+ 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());
std::vector<int> all_tasks(num_tasks);
std::iota(all_tasks.begin(), all_tasks.end(), 0);
// 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,
std::vector<BoolVar>(num_tasks));
for (int worker : all_workers) {
for (int task : all_tasks) {
x[worker][task] = cp_model.NewBoolVar().WithName(
absl::StrFormat("x[%d,%d]", worker, task));
}
}
// Constraints
// Each worker is assigned to at most one task.
for (int worker : all_workers) {
cp_model.AddAtMostOne(x[worker]);
}
// Each task is assigned to exactly one worker.
for (int task : all_tasks) {
std::vector<BoolVar> tasks;
for (int worker : all_workers) {
tasks.push_back(x[worker][task]);
}
cp_model.AddExactlyOne(tasks);
}
// Create variables for each worker, indicating whether they work on some
// task.
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) {
LinearExpr task_sum;
for (int task : all_tasks) {
task_sum += x[worker][task];
}
cp_model.AddEquality(work[worker], task_sum);
}
// Define the allowed groups of worders
auto table1 =
cp_model.AddAllowedAssignments({work[0], work[1], work[2], work[3]});
for (const auto& t : group1) {
table1.AddTuple(t);
}
auto table2 =
cp_model.AddAllowedAssignments({work[4], work[5], work[6], work[7]});
for (const auto& t : group2) {
table2.AddTuple(t);
}
auto table3 =
cp_model.AddAllowedAssignments({work[8], work[9], work[10], work[11]});
for (const auto& t : group3) {
table3.AddTuple(t);
}
// Objective
LinearExpr total_cost;
for (int worker : all_workers) {
for (int task : all_tasks) {
total_cost += x[worker][task] * costs[worker][task];
}
}
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) {
for (int task : all_tasks) {
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.
package com.google.ortools.sat.samples;
import com.google.ortools.Loader;
import com.google.ortools.sat.CpModel;
import com.google.ortools.sat.CpSolver;
import com.google.ortools.sat.CpSolverStatus;
import com.google.ortools.sat.IntVar;
import com.google.ortools.sat.LinearExpr;
import com.google.ortools.sat.LinearExprBuilder;
import com.google.ortools.sat.Literal;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.IntStream;
/** Assignment problem. */
public class AssignmentGroupsSat {
public static void main(String[] args) {
Loader.loadNativeLibraries();
// 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();
final int[] allTasks = IntStream.range(0, numTasks).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) {
for (int task : allTasks) {
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<>();
for (int task : allTasks) {
tasks.add(x[worker][task]);
}
model.addAtMostOne(tasks);
}
// Each task is assigned to exactly one worker.
for (int task : allTasks) {
List<Literal> workers = new ArrayList<>();
for (int worker : allWorkers) {
workers.add(x[worker][task]);
}
model.addExactlyOne(workers);
}
// 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();
for (int task : allTasks) {
expr.add(x[worker][task]);
}
model.addEquality(work[worker], expr);
}
// 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();
for (int worker : allWorkers) {
for (int task : allTasks) {
obj.addTerm(x[worker][task], costs[worker][task]);
}
}
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) {
for (int task : allTasks) {
if (solver.booleanValue(x[worker][task])) {
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;
using Google.OrTools.Sat;
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();
int[] allTasks = Enumerable.Range(0, numTasks).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)
{
foreach (int task in allTasks)
{
x[worker, task] = model.NewBoolVar($"x[{worker},{task}]");
}
}
// Constraints
// Each worker is assigned to at most one task.
foreach (int worker in allWorkers)
{
List<ILiteral> tasks = new List<ILiteral>();
foreach (int task in allTasks)
{
tasks.Add(x[worker, task]);
}
model.AddAtMostOne(tasks);
}
// Each task is assigned to exactly one worker.
foreach (int task in allTasks)
{
List<ILiteral> workers = new List<ILiteral>();
foreach (int worker in allWorkers)
{
workers.Add(x[worker, task]);
}
model.AddExactlyOne(workers);
}
// 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>();
foreach (int task in allTasks)
{
tasks.Add(x[worker, task]);
}
model.Add(work[worker] == LinearExpr.Sum(tasks));
}
// 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)
{
foreach (int task in allTasks)
{
obj.AddTerm(x[worker, task], costs[worker, task]);
}
}
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)
{
foreach (int task in allTasks)
{
if (solver.Value(x[worker, task]) > 0.5)
{
Console.WriteLine($"Worker {worker} assigned to task {task}. " +
$"Cost: {costs[worker, 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-Lösung
Als Nächstes beschreiben wir eine Lösung für das Problem mithilfe des MIP Solver.
Bibliotheken importieren
Mit dem folgenden Code wird die erforderliche Bibliothek importiert.
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 com.google.ortools.linearsolver.MPConstraint; import com.google.ortools.linearsolver.MPObjective; import com.google.ortools.linearsolver.MPSolver; import com.google.ortools.linearsolver.MPVariable; import java.util.stream.IntStream;
C#
using System; using System.Collections.Generic; using System.Linq; using Google.OrTools.LinearSolver;
Daten definieren
Mit dem folgenden Code werden die Daten für das Programm erstellt.
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)
num_tasks = len(costs[0])
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();
std::vector<int> all_tasks(num_tasks);
std::iota(all_tasks.begin(), all_tasks.end(), 0);
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();
final int[] allTasks = IntStream.range(0, numTasks).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();
int[] allTasks = Enumerable.Range(0, numTasks).ToArray();
Zulässige Gruppen erstellen
Mit dem folgenden Code werden die zulässigen Gruppen erstellt, indem die drei oben gezeigten Untergruppen in einer Schleife durchlaufen werden.
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 },
};
Löser deklarieren
Mit dem folgenden Code wird der Solver erstellt.
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;
}
Variablen erstellen
Mit dem folgenden Code wird ein Array von Variablen für das Problem erstellt.
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):
for task in range(num_tasks):
x[worker, task] = solver.BoolVar(f"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.
std::vector<std::vector<const MPVariable*>> x(
num_workers, std::vector<const MPVariable*>(num_tasks));
for (int worker : all_workers) {
for (int task : all_tasks) {
x[worker][task] =
solver->MakeBoolVar(absl::StrFormat("x[%d,%d]", worker, task));
}
}
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) {
for (int task : allTasks) {
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)
{
foreach (int task in allTasks)
{
x[worker, task] = solver.MakeBoolVar($"x[{worker},{task}]");
}
}
Einschränkungen hinzufügen
Mit dem folgenden Code werden die Einschränkungen für das Programm erstellt.
Python
# The total size of the tasks each worker takes on is at most total_size_max.
for worker in range(num_workers):
solver.Add(solver.Sum([x[worker, task] for task in range(num_tasks)]) <= 1)
# Each task is assigned to exactly one worker.
for task in range(num_tasks):
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;
for (int task : all_tasks) {
worker_sum += x[worker][task];
}
solver->MakeRowConstraint(worker_sum <= 1.0);
}
// Each task is assigned to exactly one worker.
for (int task : all_tasks) {
LinearExpr task_sum;
for (int worker : all_workers) {
task_sum += x[worker][task];
}
solver->MakeRowConstraint(task_sum == 1.0);
}
Java
// Each worker is assigned to at most one task.
for (int worker : allWorkers) {
MPConstraint constraint = solver.makeConstraint(0, 1, "");
for (int task : allTasks) {
constraint.setCoefficient(x[worker][task], 1);
}
}
// Each task is assigned to exactly one worker.
for (int task : allTasks) {
MPConstraint constraint = solver.makeConstraint(1, 1, "");
for (int worker : allWorkers) {
constraint.setCoefficient(x[worker][task], 1);
}
}
C#
// Each worker is assigned to at most one task.
foreach (int worker in allWorkers)
{
Constraint constraint = solver.MakeConstraint(0, 1, "");
foreach (int task in allTasks)
{
constraint.SetCoefficient(x[worker, task], 1);
}
}
// Each task is assigned to exactly one worker.
foreach (int task in allTasks)
{
Constraint constraint = solver.MakeConstraint(1, 1, "");
foreach (int worker in allWorkers)
{
constraint.SetCoefficient(x[worker, task], 1);
}
}
Ziel erstellen
Mit dem folgenden Code wird die Zielfunktion erstellt.
Python
objective_terms = []
for worker in range(num_workers):
for task in range(num_tasks):
objective_terms.append(costs[worker][task] * x[worker, task])
solver.Minimize(solver.Sum(objective_terms))
C++
MPObjective* const objective = solver->MutableObjective();
for (int worker : all_workers) {
for (int task : all_tasks) {
objective->SetCoefficient(x[worker][task], costs[worker][task]);
}
}
objective->SetMinimization();
Java
MPObjective objective = solver.objective();
for (int worker : allWorkers) {
for (int task : allTasks) {
objective.setCoefficient(x[worker][task], costs[worker][task]);
}
}
objective.setMinimization();
C#
Objective objective = solver.Objective();
foreach (int worker in allWorkers)
{
foreach (int task in allTasks)
{
objective.SetCoefficient(x[worker, task], costs[worker, task]);
}
}
objective.SetMinimization();
Den Solver aufrufen
Der folgende Code ruft den Solver auf und zeigt die Ergebnisse an.
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();
Ergebnisse anzeigen
Jetzt können wir die Lösung ausdrucken.
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):
for task in range(num_tasks):
if x[worker, task].solution_value() > 0.5:
print(
f"Worker {worker} assigned to task {task}."
+ 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) {
for (int task : all_tasks) {
// 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) {
for (int task : allTasks) {
// 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)
{
foreach (int task in allTasks)
{
// Test if x[i, j] is 0 or 1 (with tolerance for floating point
// arithmetic).
if (x[worker, task].SolutionValue() > 0.5)
{
Console.WriteLine($"Worker {worker} assigned to task {task}. Cost: {costs[worker, task]}");
}
}
}
}
else
{
Console.WriteLine("No solution found.");
}
So sieht die Ausgabe des Programms aus:
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
Das gesamte Programm
Hier ist das gesamte Programm.
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)
num_tasks = len(costs[0])
# 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):
for task in range(num_tasks):
x[worker, task] = solver.BoolVar(f"x[{worker},{task}]")
# Constraints
# The total size of the tasks each worker takes on is at most total_size_max.
for worker in range(num_workers):
solver.Add(solver.Sum([x[worker, task] for task in range(num_tasks)]) <= 1)
# Each task is assigned to exactly one worker.
for task in range(num_tasks):
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):
solver.Add(
work[worker] == solver.Sum([x[worker, task] for task in range(num_tasks)])
)
# 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):
for task in range(num_tasks):
objective_terms.append(costs[worker][task] * x[worker, task])
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):
for task in range(num_tasks):
if x[worker, task].solution_value() > 0.5:
print(
f"Worker {worker} assigned to task {task}."
+ 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();
std::vector<int> all_tasks(num_tasks);
std::iota(all_tasks.begin(), all_tasks.end(), 0);
// 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(
num_workers, std::vector<const MPVariable*>(num_tasks));
for (int worker : all_workers) {
for (int task : all_tasks) {
x[worker][task] =
solver->MakeBoolVar(absl::StrFormat("x[%d,%d]", worker, task));
}
}
// Constraints
// Each worker is assigned to at most one task.
for (int worker : all_workers) {
LinearExpr worker_sum;
for (int task : all_tasks) {
worker_sum += x[worker][task];
}
solver->MakeRowConstraint(worker_sum <= 1.0);
}
// Each task is assigned to exactly one worker.
for (int task : all_tasks) {
LinearExpr task_sum;
for (int worker : all_workers) {
task_sum += x[worker][task];
}
solver->MakeRowConstraint(task_sum == 1.0);
}
// Create variables for each worker, indicating whether they work on some
// task.
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) {
LinearExpr task_sum;
for (int task : all_tasks) {
task_sum += x[worker][task];
}
solver->MakeRowConstraint(work[worker] == task_sum);
}
// 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) {
for (int task : all_tasks) {
objective->SetCoefficient(x[worker][task], costs[worker][task]);
}
}
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) {
for (int task : all_tasks) {
// 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 com.google.ortools.Loader;
import com.google.ortools.linearsolver.MPConstraint;
import com.google.ortools.linearsolver.MPObjective;
import com.google.ortools.linearsolver.MPSolver;
import com.google.ortools.linearsolver.MPVariable;
import java.util.stream.IntStream;
/** MIP example that solves an assignment problem. */
public class AssignmentGroupsMip {
public static void main(String[] args) {
Loader.loadNativeLibraries();
// 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();
final int[] allTasks = IntStream.range(0, numTasks).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) {
for (int task : allTasks) {
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, "");
for (int task : allTasks) {
constraint.setCoefficient(x[worker][task], 1);
}
}
// Each task is assigned to exactly one worker.
for (int task : allTasks) {
MPConstraint constraint = solver.makeConstraint(1, 1, "");
for (int worker : allWorkers) {
constraint.setCoefficient(x[worker][task], 1);
}
}
// 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, "");
for (int task : allTasks) {
// vars[task] = x[worker][task];
constraint.setCoefficient(x[worker][task], 1);
}
// solver.addEquality(work[worker], LinearExpr.sum(vars));
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) {
for (int task : allTasks) {
objective.setCoefficient(x[worker][task], costs[worker][task]);
}
}
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) {
for (int task : allTasks) {
// 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;
using Google.OrTools.LinearSolver;
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();
int[] allTasks = Enumerable.Range(0, numTasks).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)
{
foreach (int task in allTasks)
{
x[worker, task] = solver.MakeBoolVar($"x[{worker},{task}]");
}
}
// Constraints
// Each worker is assigned to at most one task.
foreach (int worker in allWorkers)
{
Constraint constraint = solver.MakeConstraint(0, 1, "");
foreach (int task in allTasks)
{
constraint.SetCoefficient(x[worker, task], 1);
}
}
// Each task is assigned to exactly one worker.
foreach (int task in allTasks)
{
Constraint constraint = solver.MakeConstraint(1, 1, "");
foreach (int worker in allWorkers)
{
constraint.SetCoefficient(x[worker, task], 1);
}
}
// 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];
foreach (int task in allTasks)
{
vars[task] = x[worker, task];
}
solver.Add(work[worker] == LinearExprArrayHelper.Sum(vars));
}
// 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)
{
foreach (int task in allTasks)
{
objective.SetCoefficient(x[worker, task], costs[worker, task]);
}
}
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)
{
foreach (int task in allTasks)
{
// Test if x[i, j] is 0 or 1 (with tolerance for floating point
// arithmetic).
if (x[worker, task].SolutionValue() > 0.5)
{
Console.WriteLine($"Worker {worker} assigned to task {task}. Cost: {costs[worker, task]}");
}
}
}
}
else
{
Console.WriteLine("No solution found.");
}
}
}
Lösungszeiten
Die Lösungszeiten für die beiden Solver sind wie folgt:
- CP-SAT: 0,0113 Sekunden
- MIP: 0,3281 Sekunden
Bei diesem Problem ist CP-SAT deutlich schneller als MIP.