本部分描述了一个分配问题，即只有特定 工作器组可以分配给任务。在此示例中， 工作器数量，编号为 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。
以下数组定义了允许的工作器组。
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）中每组的 id。
具体方法如下：
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] 是表示工作状态或
。也就是说，如果将 worker 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 快得多。