این بخش یک مشکل انتساب را توضیح می دهد که در آن فقط گروه های مجاز خاصی از کارگران می توانند به وظایف اختصاص داده شوند. در مثال دوازده کارگر وجود دارد که شماره آنها 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]]
یک گروه مجاز می تواند هر ترکیبی از سه جفت کارگر، یک جفت از هر گروه 1، گروه 2 و گروه 3 باشد. به عنوان مثال، ترکیب [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 شرح می دهیم.
کتابخانه ها را وارد کنید
کد زیر کتابخانه مورد نیاز را وارد می کند.
پایتون
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"
جاوا
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;
سی شارپ
using System; using System.Collections.Generic; using System.Linq; using Google.OrTools.Sat;
داده ها را تعریف کنید
کد زیر داده های برنامه را ایجاد می کند.
پایتون
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);جاوا
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();سی شارپ
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 را مشخص می کند.
آرایه های زیر گروه های مجاز کارگران را تعریف می کنند.
پایتون
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
}};جاوا
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
};سی شارپ
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) مشخص کنید. در اینجا نحوه کار آن آمده است:
پایتون
# 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);
}جاوا
// 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);سی شارپ
// 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 . در قسمت بعدی می توانید جزئیات کامل کد را مشاهده کنید.
مدل را ایجاد کنید
کد زیر مدل را ایجاد می کند.
پایتون
model = cp_model.CpModel()
C++
CpModelBuilder cp_model;
جاوا
CpModel model = new CpModel();
سی شارپ
CpModel model = new CpModel();
متغیرها را ایجاد کنید
کد زیر آرایه ای از متغیرها را برای مشکل ایجاد می کند.
پایتون
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));
}
}جاوا
Literal[][] x = new Literal[numWorkers][numTasks];
for (int worker : allWorkers) {
for (int task : allTasks) {
x[worker][task] = model.newBoolVar("x[" + worker + "," + task + "]");
}
}سی شارپ
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}]");
}
}محدودیت ها را اضافه کنید
کد زیر محدودیت هایی را برای برنامه ایجاد می کند.
پایتون
# 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);
}جاوا
// 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);
}سی شارپ
// 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);
}هدف را ایجاد کنید
کد زیر تابع هدف را ایجاد می کند.
پایتون
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);جاوا
LinearExprBuilder obj = LinearExpr.newBuilder();
for (int worker : allWorkers) {
for (int task : allTasks) {
obj.addTerm(x[worker][task], costs[worker][task]);
}
}
model.minimize(obj);سی شارپ
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);حل کننده را فراخوانی کنید
کد زیر حل کننده را فراخوانی می کند و نتایج را نمایش می دهد.
پایتون
solver = cp_model.CpSolver() status = solver.solve(model)
C++
const CpSolverResponse response = Solve(cp_model.Build());
جاوا
CpSolver solver = new CpSolver(); CpSolverStatus status = solver.solve(model);
سی شارپ
CpSolver solver = new CpSolver();
CpSolverStatus status = solver.Solve(model);
Console.WriteLine($"Solve status: {status}");نمایش نتایج
اکنون می توانیم راه حل را چاپ کنیم.
پایتون
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];
}
}
}جاوا
// 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.");
}سی شارپ
// 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
کل برنامه
در اینجا کل برنامه است.
پایتون
"""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;
}جاوا
// 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() {}
}
سی شارپ
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 توضیح می دهیم.
کتابخانه ها را وارد کنید
کد زیر کتابخانه مورد نیاز را وارد می کند.
پایتون
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"
جاوا
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;
سی شارپ
using System; using System.Collections.Generic; using System.Linq; using Google.OrTools.LinearSolver;
داده ها را تعریف کنید
کد زیر داده های برنامه را ایجاد می کند.
پایتون
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);جاوا
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();سی شارپ
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();گروه های مجاز را ایجاد کنید
کد زیر گروه های مجاز را با چرخش در سه مجموعه زیرگروه نشان داده شده در بالا ایجاد می کند.
پایتون
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},
}};جاوا
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},
};سی شارپ
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 },
};حل کننده را اعلام کنید
کد زیر حل کننده را ایجاد می کند.
پایتون
# Create the mip solver with the SCIP backend.
solver = pywraplp.Solver.CreateSolver("SCIP")
if not solver:
returnC++
// Create the mip solver with the SCIP backend.
std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("SCIP"));
if (!solver) {
LOG(WARNING) << "SCIP solver unavailable.";
return;
}جاوا
// 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;
}سی شارپ
Solver solver = Solver.CreateSolver("SCIP");
if (solver is null)
{
return;
}متغیرها را ایجاد کنید
کد زیر آرایه ای از متغیرها را برای مشکل ایجاد می کند.
پایتون
# 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));
}
}جاوا
// 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 + "]");
}
}سی شارپ
// 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}]");
}
}محدودیت ها را اضافه کنید
کد زیر محدودیت هایی را برای برنامه ایجاد می کند.
پایتون
# 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);
}جاوا
// 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);
}
}سی شارپ
// 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);
}
}هدف را ایجاد کنید
کد زیر تابع هدف را ایجاد می کند.
پایتون
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();جاوا
MPObjective objective = solver.objective();
for (int worker : allWorkers) {
for (int task : allTasks) {
objective.setCoefficient(x[worker][task], costs[worker][task]);
}
}
objective.setMinimization();سی شارپ
Objective objective = solver.Objective();
foreach (int worker in allWorkers)
{
foreach (int task in allTasks)
{
objective.SetCoefficient(x[worker, task], costs[worker, task]);
}
}
objective.SetMinimization();حل کننده را فراخوانی کنید
کد زیر حل کننده را فراخوانی می کند و نتایج را نمایش می دهد.
پایتون
print(f"Solving with {solver.SolverVersion()}")
status = solver.Solve()C++
const MPSolver::ResultStatus result_status = solver->Solve();
جاوا
MPSolver.ResultStatus resultStatus = solver.solve();
سی شارپ
Solver.ResultStatus resultStatus = solver.Solve();
نمایش نتایج
اکنون می توانیم راه حل را چاپ کنیم.
پایتون
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];
}
}
}جاوا
// 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.");
}سی شارپ
// 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
کل برنامه
در اینجا کل برنامه است.
پایتون
"""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;
}جاوا
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() {}
}سی شارپ
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 است.