本部分介绍了一个分配问题，即只能将某些允许的工作器组分配给任务。在此示例中，有 12 个工作器，编号为 0 - 11。允许的组是以下几对工作器的组合。
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]]
允许的组可以是三对工作器的任意组合，它们分别来自 group1、group2 和 group3。例如，将 [2, 3]、[6, 7] 和 [10, 11] 组合使用可生成允许的组 [2, 3, 6, 7, 10, 11]。由于这三个集合中的每个元素都包含五个元素，因此允许的组总数为 5 * 5 * 5 = 125。
请注意，如果一组工作器属于任何一个允许的组，则可以解决该问题。换言之，可行集由满足任一约束条件的点组成。这是一个非凸问题的示例。 相比之下，上文所述的 MIP 示例则是一个凸形问题：要使点变得可行，必须满足所有约束条件。
对于诸如此类的非凸问题，CP-SAT 求解器通常比 MIP 求解器更快。以下部分介绍了使用 CP-SAT 求解器和 MIP 求解器的求解时间，并比较了这两种求解器的求解时间。
CP-SAT 解决方案
首先，我们将介绍一个使用 CP-SAT 求解器求解该题的方法。
导入库
以下代码会导入所需的库。
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;
定义数据
以下代码会为程序创建数据。
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();
创建允许的群组
如需定义 CP-SAT 求解器允许的工作器组，您可以创建二元数组来指示哪些工作器属于该组。例如，对于 group1（工作器 0 - 3），二进制矢量 [0, 0, 1, 1] 指定包含工作器 2 和 3 的组。
以下数组定义了允许的 worker 组。
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
};
对于 CP-SAT，没有必要在一个循环中创建这些向量的全部 125 个组合。CP-SAT 求解器提供了 AllowedAssignments 方法，您可以通过该方法为三个工作器集（0 - 3、4 - 7 和 8 - 11）分别指定允许的组的约束条件。具体方法如下：
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);
变量 work[i] 是 0-1 变量，表示工作状态或每个工作器。也就是说，如果将工作器 i 分配给任务，则 work[i] 等于 1，否则等于 0。solver.Add(solver.AllowedAssignments([work[0], work[1], work[2], work[3]], group1)) 行定义了工作器 0-3 的工作状态必须与 group1 中的模式之一匹配的约束条件。您可以在下一部分中查看代码的完整详细信息。
创建模型
以下代码会创建该模型。
Python
model = cp_model.CpModel()
C++
CpModelBuilder cp_model;
Java
CpModel model = new CpModel();
C#
CpModel model = new CpModel();
创建变量
以下代码会为该问题创建变量数组。
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}]");
}
}
添加约束条件
以下代码会为程序创建约束条件。
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);
}
创建目标
以下代码会创建目标函数。
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);
调用求解器
以下代码会调用求解器并显示结果。
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}");
显示结果
现在，我们可以输出解决方案了。
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.");
}
以下是程序的输出。
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
整个计划
完整内容如下。
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 解决方案
接下来，我们将介绍使用 MIP 求解器解决这个问题的方法。
导入库
以下代码会导入所需的库。
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;
定义数据
以下代码会为程序创建数据。
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();
创建允许的群组
以下代码通过循环遍历上面显示的三组子组，从而创建允许的组。
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 },
};
声明求解器
以下代码会创建求解器。
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;
}
创建变量
以下代码会为该问题创建变量数组。
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}]");
}
}
添加约束条件
以下代码会为程序创建约束条件。
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);
}
}
创建目标
以下代码会创建目标函数。
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();
调用求解器
以下代码会调用求解器并显示结果。
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();
显示结果
现在，我们可以输出解决方案了。
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.");
}
程序的输出如下所示：
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
整个计划
完整内容如下。
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.");
}
}
}
解决方案时间
这两种求解器的求解时间如下所示：
- CP-SAT：0.0113 秒
- MIP：0.3281 秒
对于此问题，CP-SAT 比 MIP 快得多。