Có nhiều phiên bản của vấn đề về chỉ định, có thêm những hạn chế đối với trình thực thi hoặc tác vụ. Trong ví dụ tiếp theo, 6 nhân viên được chia thành 2 nhóm và mỗi nhóm có thể thực hiện tối đa 2 nhiệm vụ.
Các phần sau đây trình bày một chương trình Python giải quyết vấn đề này bằng cách sử dụng CP-SAT hoặc trình giải MIP. Để tìm giải pháp sử dụng trình phân giải luồng chi phí tối thiểu, hãy xem phần Phân công với nhóm.
Giải pháp CP-SAT
Trước tiên, hãy cùng tìm hiểu giải pháp CP-SAT cho vấn đề.
Nhập thư viện
Mã sau đây nhập thư viện bắt buộc.
Python
from ortools.sat.python import cp_model
C++
#include <stdlib.h> #include <numeric> #include <vector> #include "absl/strings/str_format.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.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;
Xác định dữ liệu
Đoạn mã sau đây tạo dữ liệu cho chương trình.
Python
costs = [
[90, 76, 75, 70],
[35, 85, 55, 65],
[125, 95, 90, 105],
[45, 110, 95, 115],
[60, 105, 80, 75],
[45, 65, 110, 95],
]
num_workers = len(costs)
num_tasks = len(costs[0])
team1 = [0, 2, 4]
team2 = [1, 3, 5]
# Maximum total of tasks for any team
team_max = 2
C++
const std::vector<std::vector<int>> costs = {{
{{90, 76, 75, 70}},
{{35, 85, 55, 65}},
{{125, 95, 90, 105}},
{{45, 110, 95, 115}},
{{60, 105, 80, 75}},
{{45, 65, 110, 95}},
}};
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);
const std::vector<int> team1 = {{0, 2, 4}};
const std::vector<int> team2 = {{1, 3, 5}};
// Maximum total of tasks for any team
const int team_max = 2;
Java
int[][] costs = {
{90, 76, 75, 70},
{35, 85, 55, 65},
{125, 95, 90, 105},
{45, 110, 95, 115},
{60, 105, 80, 75},
{45, 65, 110, 95},
};
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();
final int[] team1 = {0, 2, 4};
final int[] team2 = {1, 3, 5};
// Maximum total of tasks for any team
final int teamMax = 2;
C#
int[,] costs = {
{ 90, 76, 75, 70 }, { 35, 85, 55, 65 }, { 125, 95, 90, 105 },
{ 45, 110, 95, 115 }, { 60, 105, 80, 75 }, { 45, 65, 110, 95 },
};
int numWorkers = costs.GetLength(0);
int numTasks = costs.GetLength(1);
int[] allWorkers = Enumerable.Range(0, numWorkers).ToArray();
int[] allTasks = Enumerable.Range(0, numTasks).ToArray();
int[] team1 = { 0, 2, 4 };
int[] team2 = { 1, 3, 5 };
// Maximum total of tasks for any team
int teamMax = 2;
Tạo mô hình
Mã sau đây sẽ tạo mô hình.
Python
model = cp_model.CpModel()
C++
CpModelBuilder cp_model;
Java
CpModel model = new CpModel();
C#
CpModel model = new CpModel();
Tạo các biến
Mã sau đây tạo một mảng biến cho bài toán.
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];
// Variables in a 1-dim array.
for (int worker : allWorkers) {
for (int task : allTasks) {
x[worker][task] = model.newBoolVar("x[" + worker + "," + task + "]");
}
}
C#
BoolVar[,] x = new BoolVar[numWorkers, numTasks];
foreach (int worker in allWorkers)
{
foreach (int task in allTasks)
{
x[worker, task] = model.NewBoolVar($"x[{worker},{task}]");
}
}
Mỗi cặp trình thực thi và tác vụ đều có một biến. Xin lưu ý rằng worker được đánh số 0 - 5, trong khi các nhiệm vụ được đánh số 0 - 3, không giống như trong ví dụ ban đầu, trong đó tất cả các nút phải được đánh số khác nhau, theo yêu cầu của trình phân giải luồng chi phí tối thiểu.
Thêm các điều kiện ràng buộc
Mã sau đây tạo các điều kiện ràng buộc cho chương trình.
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))
# Each team takes at most two tasks.
team1_tasks = []
for worker in team1:
for task in range(num_tasks):
team1_tasks.append(x[worker, task])
model.add(sum(team1_tasks) <= team_max)
team2_tasks = []
for worker in team2:
for task in range(num_tasks):
team2_tasks.append(x[worker, task])
model.add(sum(team2_tasks) <= team_max)
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 team takes at most two tasks.
LinearExpr team1_tasks;
for (int worker : team1) {
for (int task : all_tasks) {
team1_tasks += x[worker][task];
}
}
cp_model.AddLessOrEqual(team1_tasks, team_max);
LinearExpr team2_tasks;
for (int worker : team2) {
for (int task : all_tasks) {
team2_tasks += x[worker][task];
}
}
cp_model.AddLessOrEqual(team2_tasks, team_max);
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);
}
// Each team takes at most two tasks.
LinearExprBuilder team1Tasks = LinearExpr.newBuilder();
for (int worker : team1) {
for (int task : allTasks) {
team1Tasks.add(x[worker][task]);
}
}
model.addLessOrEqual(team1Tasks, teamMax);
LinearExprBuilder team2Tasks = LinearExpr.newBuilder();
for (int worker : team2) {
for (int task : allTasks) {
team2Tasks.add(x[worker][task]);
}
}
model.addLessOrEqual(team2Tasks, teamMax);
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);
}
// Each team takes at most two tasks.
List<IntVar> team1Tasks = new List<IntVar>();
foreach (int worker in team1)
{
foreach (int task in allTasks)
{
team1Tasks.Add(x[worker, task]);
}
}
model.Add(LinearExpr.Sum(team1Tasks.ToArray()) <= teamMax);
List<IntVar> team2Tasks = new List<IntVar>();
foreach (int worker in team2)
{
foreach (int task in allTasks)
{
team2Tasks.Add(x[worker, task]);
}
}
model.Add(LinearExpr.Sum(team2Tasks.ToArray()) <= teamMax);
Tạo mục tiêu
Mã sau đây tạo hàm mục tiêu.
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);
Giá trị của hàm mục tiêu là tổng chi phí cho tất cả biến được trình giải chỉ chỉ định giá trị 1.
Gọi trình giải
Mã sau đây gọi trình phân giải và hiển thị kết quả.
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}");
Hiện kết quả
Bây giờ, chúng ta có thể in giải pháp.
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.");
}
Đây là kết quả của chương trình.
Total cost: 250 Worker 0 assigned to task 2. Cost = 75 Worker 1 assigned to task 0. Cost = 35 Worker 4 assigned to task 3. Cost = 75 Worker 5 assigned to task 1. Cost = 65 Time = 6 milliseconds
Toàn bộ chương trình
Sau đây là toàn bộ chương trình.
Python
"""Solves a simple assignment problem."""
from ortools.sat.python import cp_model
def main() -> None:
# Data
costs = [
[90, 76, 75, 70],
[35, 85, 55, 65],
[125, 95, 90, 105],
[45, 110, 95, 115],
[60, 105, 80, 75],
[45, 65, 110, 95],
]
num_workers = len(costs)
num_tasks = len(costs[0])
team1 = [0, 2, 4]
team2 = [1, 3, 5]
# Maximum total of tasks for any team
team_max = 2
# 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))
# Each team takes at most two tasks.
team1_tasks = []
for worker in team1:
for task in range(num_tasks):
team1_tasks.append(x[worker, task])
model.add(sum(team1_tasks) <= team_max)
team2_tasks = []
for worker in team2:
for task in range(num_tasks):
team2_tasks.append(x[worker, task])
model.add(sum(team2_tasks) <= team_max)
# 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 a simple assignment problem.
#include <stdlib.h>
#include <numeric>
#include <vector>
#include "absl/strings/str_format.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 AssignmentTeamsSat() {
// Data
const std::vector<std::vector<int>> costs = {{
{{90, 76, 75, 70}},
{{35, 85, 55, 65}},
{{125, 95, 90, 105}},
{{45, 110, 95, 115}},
{{60, 105, 80, 75}},
{{45, 65, 110, 95}},
}};
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);
const std::vector<int> team1 = {{0, 2, 4}};
const std::vector<int> team2 = {{1, 3, 5}};
// Maximum total of tasks for any team
const int team_max = 2;
// 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);
}
// Each team takes at most two tasks.
LinearExpr team1_tasks;
for (int worker : team1) {
for (int task : all_tasks) {
team1_tasks += x[worker][task];
}
}
cp_model.AddLessOrEqual(team1_tasks, team_max);
LinearExpr team2_tasks;
for (int worker : team2) {
for (int task : all_tasks) {
team2_tasks += x[worker][task];
}
}
cp_model.AddLessOrEqual(team2_tasks, team_max);
// 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::AssignmentTeamsSat();
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.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 AssignmentTeamsSat {
public static void main(String[] args) {
Loader.loadNativeLibraries();
// Data
int[][] costs = {
{90, 76, 75, 70},
{35, 85, 55, 65},
{125, 95, 90, 105},
{45, 110, 95, 115},
{60, 105, 80, 75},
{45, 65, 110, 95},
};
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();
final int[] team1 = {0, 2, 4};
final int[] team2 = {1, 3, 5};
// Maximum total of tasks for any team
final int teamMax = 2;
// Model
CpModel model = new CpModel();
// Variables
Literal[][] x = new Literal[numWorkers][numTasks];
// Variables in a 1-dim array.
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);
}
// Each team takes at most two tasks.
LinearExprBuilder team1Tasks = LinearExpr.newBuilder();
for (int worker : team1) {
for (int task : allTasks) {
team1Tasks.add(x[worker][task]);
}
}
model.addLessOrEqual(team1Tasks, teamMax);
LinearExprBuilder team2Tasks = LinearExpr.newBuilder();
for (int worker : team2) {
for (int task : allTasks) {
team2Tasks.add(x[worker][task]);
}
}
model.addLessOrEqual(team2Tasks, teamMax);
// 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 AssignmentTeamsSat() {}
}
C#
using System;
using System.Collections.Generic;
using System.Linq;
using Google.OrTools.Sat;
public class AssignmentTeamsSat
{
public static void Main(String[] args)
{
// Data.
int[,] costs = {
{ 90, 76, 75, 70 }, { 35, 85, 55, 65 }, { 125, 95, 90, 105 },
{ 45, 110, 95, 115 }, { 60, 105, 80, 75 }, { 45, 65, 110, 95 },
};
int numWorkers = costs.GetLength(0);
int numTasks = costs.GetLength(1);
int[] allWorkers = Enumerable.Range(0, numWorkers).ToArray();
int[] allTasks = Enumerable.Range(0, numTasks).ToArray();
int[] team1 = { 0, 2, 4 };
int[] team2 = { 1, 3, 5 };
// Maximum total of tasks for any team
int teamMax = 2;
// Model.
CpModel model = new CpModel();
// Variables.
BoolVar[,] x = new BoolVar[numWorkers, numTasks];
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);
}
// Each team takes at most two tasks.
List<IntVar> team1Tasks = new List<IntVar>();
foreach (int worker in team1)
{
foreach (int task in allTasks)
{
team1Tasks.Add(x[worker, task]);
}
}
model.Add(LinearExpr.Sum(team1Tasks.ToArray()) <= teamMax);
List<IntVar> team2Tasks = new List<IntVar>();
foreach (int worker in team2)
{
foreach (int task in allTasks)
{
team2Tasks.Add(x[worker, task]);
}
}
model.Add(LinearExpr.Sum(team2Tasks.ToArray()) <= teamMax);
// 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");
}
}
Giải pháp MIP
Tiếp theo, chúng tôi sẽ mô tả giải pháp cho bài tập này bằng cách sử dụng trình giải MIP.
Nhập thư viện
Mã sau đây nhập thư viện bắt buộc.
Python
from ortools.linear_solver import pywraplp
C++
#include <cstdint> #include <memory> #include <numeric> #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;
Xác định dữ liệu
Đoạn mã sau đây tạo dữ liệu cho chương trình.
Python
costs = [
[90, 76, 75, 70],
[35, 85, 55, 65],
[125, 95, 90, 105],
[45, 110, 95, 115],
[60, 105, 80, 75],
[45, 65, 110, 95],
]
num_workers = len(costs)
num_tasks = len(costs[0])
team1 = [0, 2, 4]
team2 = [1, 3, 5]
# Maximum total of tasks for any team
team_max = 2
C++
const std::vector<std::vector<int64_t>> costs = {{
{{90, 76, 75, 70}},
{{35, 85, 55, 65}},
{{125, 95, 90, 105}},
{{45, 110, 95, 115}},
{{60, 105, 80, 75}},
{{45, 65, 110, 95}},
}};
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);
const std::vector<int64_t> team1 = {{0, 2, 4}};
const std::vector<int64_t> team2 = {{1, 3, 5}};
// Maximum total of tasks for any team
const int team_max = 2;
Java
double[][] costs = {
{90, 76, 75, 70},
{35, 85, 55, 65},
{125, 95, 90, 105},
{45, 110, 95, 115},
{60, 105, 80, 75},
{45, 65, 110, 95},
};
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();
final int[] team1 = {0, 2, 4};
final int[] team2 = {1, 3, 5};
// Maximum total of tasks for any team
final int teamMax = 2;
C#
int[,] costs = {
{ 90, 76, 75, 70 }, { 35, 85, 55, 65 }, { 125, 95, 90, 105 },
{ 45, 110, 95, 115 }, { 60, 105, 80, 75 }, { 45, 65, 110, 95 },
};
int numWorkers = costs.GetLength(0);
int numTasks = costs.GetLength(1);
int[] allWorkers = Enumerable.Range(0, numWorkers).ToArray();
int[] allTasks = Enumerable.Range(0, numTasks).ToArray();
int[] team1 = { 0, 2, 4 };
int[] team2 = { 1, 3, 5 };
// Maximum total of tasks for any team
int teamMax = 2;
Khai báo trình giải
Mã sau đây sẽ tạo trình giải.
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;
}
Tạo các biến
Mã sau đây tạo một mảng biến cho bài toán.
Python
# x[i, j] is an array of 0-1 variables, which will be 1
# if worker i is assigned to task j.
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}]");
}
}
Thêm các điều kiện ràng buộc
Mã sau đây tạo các điều kiện ràng buộc cho chương trình.
Python
# Each worker is assigned at most 1 task.
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)
# Each team takes at most two tasks.
team1_tasks = []
for worker in team1:
for task in range(num_tasks):
team1_tasks.append(x[worker, task])
solver.Add(solver.Sum(team1_tasks) <= team_max)
team2_tasks = []
for worker in team2:
for task in range(num_tasks):
team2_tasks.append(x[worker, task])
solver.Add(solver.Sum(team2_tasks) <= team_max)
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 team takes at most two tasks.
LinearExpr team1_tasks;
for (int worker : team1) {
for (int task : all_tasks) {
team1_tasks += x[worker][task];
}
}
solver->MakeRowConstraint(team1_tasks <= team_max);
LinearExpr team2_tasks;
for (int worker : team2) {
for (int task : all_tasks) {
team2_tasks += x[worker][task];
}
}
solver->MakeRowConstraint(team2_tasks <= team_max);
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);
}
}
// Each team takes at most two tasks.
MPConstraint team1Tasks = solver.makeConstraint(0, teamMax, "");
for (int worker : team1) {
for (int task : allTasks) {
team1Tasks.setCoefficient(x[worker][task], 1);
}
}
MPConstraint team2Tasks = solver.makeConstraint(0, teamMax, "");
for (int worker : team2) {
for (int task : allTasks) {
team2Tasks.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);
}
}
// Each team takes at most two tasks.
Constraint team1Tasks = solver.MakeConstraint(0, teamMax, "");
foreach (int worker in team1)
{
foreach (int task in allTasks)
{
team1Tasks.SetCoefficient(x[worker, task], 1);
}
}
Constraint team2Tasks = solver.MakeConstraint(0, teamMax, "");
foreach (int worker in team2)
{
foreach (int task in allTasks)
{
team2Tasks.SetCoefficient(x[worker, task], 1);
}
}
Tạo mục tiêu
Mã sau đây tạo hàm mục tiêu.
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();
Gọi trình giải
Mã sau đây gọi trình phân giải và hiển thị kết quả.
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();
Hiện kết quả
Bây giờ, chúng ta có thể in giải pháp.
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.")
print(f"Time = {solver.WallTime()} ms")
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.");
}
Đây là kết quả của chương trình.
Minimum cost assignment: 250.0 Worker 0 assigned to task 2. Cost = 75 Worker 1 assigned to task 0. Cost = 35 Worker 4 assigned to task 3. Cost = 75 Worker 5 assigned to task 1. Cost = 65 Time = 6 milliseconds
Toàn bộ chương trình
Sau đây là toàn bộ chương trình.
Python
"""MIP example that solves an assignment problem."""
from ortools.linear_solver import pywraplp
def main():
# Data
costs = [
[90, 76, 75, 70],
[35, 85, 55, 65],
[125, 95, 90, 105],
[45, 110, 95, 115],
[60, 105, 80, 75],
[45, 65, 110, 95],
]
num_workers = len(costs)
num_tasks = len(costs[0])
team1 = [0, 2, 4]
team2 = [1, 3, 5]
# Maximum total of tasks for any team
team_max = 2
# Solver
# Create the mip solver with the SCIP backend.
solver = pywraplp.Solver.CreateSolver("SCIP")
if not solver:
return
# Variables
# x[i, j] is an array of 0-1 variables, which will be 1
# if worker i is assigned to task j.
x = {}
for worker in range(num_workers):
for task in range(num_tasks):
x[worker, task] = solver.BoolVar(f"x[{worker},{task}]")
# Constraints
# Each worker is assigned at most 1 task.
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)
# Each team takes at most two tasks.
team1_tasks = []
for worker in team1:
for task in range(num_tasks):
team1_tasks.append(x[worker, task])
solver.Add(solver.Sum(team1_tasks) <= team_max)
team2_tasks = []
for worker in team2:
for task in range(num_tasks):
team2_tasks.append(x[worker, task])
solver.Add(solver.Sum(team2_tasks) <= team_max)
# 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.")
print(f"Time = {solver.WallTime()} ms")
if __name__ == "__main__":
main()
C++
// Solve a simple assignment problem.
#include <cstdint>
#include <memory>
#include <numeric>
#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}},
{{35, 85, 55, 65}},
{{125, 95, 90, 105}},
{{45, 110, 95, 115}},
{{60, 105, 80, 75}},
{{45, 65, 110, 95}},
}};
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);
const std::vector<int64_t> team1 = {{0, 2, 4}};
const std::vector<int64_t> team2 = {{1, 3, 5}};
// Maximum total of tasks for any team
const int team_max = 2;
// 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);
}
// Each team takes at most two tasks.
LinearExpr team1_tasks;
for (int worker : team1) {
for (int task : all_tasks) {
team1_tasks += x[worker][task];
}
}
solver->MakeRowConstraint(team1_tasks <= team_max);
LinearExpr team2_tasks;
for (int worker : team2) {
for (int task : all_tasks) {
team2_tasks += x[worker][task];
}
}
solver->MakeRowConstraint(team2_tasks <= team_max);
// 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 AssignmentTeamsMip {
public static void main(String[] args) {
Loader.loadNativeLibraries();
// Data
double[][] costs = {
{90, 76, 75, 70},
{35, 85, 55, 65},
{125, 95, 90, 105},
{45, 110, 95, 115},
{60, 105, 80, 75},
{45, 65, 110, 95},
};
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();
final int[] team1 = {0, 2, 4};
final int[] team2 = {1, 3, 5};
// Maximum total of tasks for any team
final int teamMax = 2;
// 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);
}
}
// Each team takes at most two tasks.
MPConstraint team1Tasks = solver.makeConstraint(0, teamMax, "");
for (int worker : team1) {
for (int task : allTasks) {
team1Tasks.setCoefficient(x[worker][task], 1);
}
}
MPConstraint team2Tasks = solver.makeConstraint(0, teamMax, "");
for (int worker : team2) {
for (int task : allTasks) {
team2Tasks.setCoefficient(x[worker][task], 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 AssignmentTeamsMip() {}
}
C#
using System;
using System.Collections.Generic;
using System.Linq;
using Google.OrTools.LinearSolver;
public class AssignmentTeamsMip
{
static void Main()
{
// Data.
int[,] costs = {
{ 90, 76, 75, 70 }, { 35, 85, 55, 65 }, { 125, 95, 90, 105 },
{ 45, 110, 95, 115 }, { 60, 105, 80, 75 }, { 45, 65, 110, 95 },
};
int numWorkers = costs.GetLength(0);
int numTasks = costs.GetLength(1);
int[] allWorkers = Enumerable.Range(0, numWorkers).ToArray();
int[] allTasks = Enumerable.Range(0, numTasks).ToArray();
int[] team1 = { 0, 2, 4 };
int[] team2 = { 1, 3, 5 };
// Maximum total of tasks for any team
int teamMax = 2;
// 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);
}
}
// Each team takes at most two tasks.
Constraint team1Tasks = solver.MakeConstraint(0, teamMax, "");
foreach (int worker in team1)
{
foreach (int task in allTasks)
{
team1Tasks.SetCoefficient(x[worker, task], 1);
}
}
Constraint team2Tasks = solver.MakeConstraint(0, teamMax, "");
foreach (int worker in team2)
{
foreach (int task in allTasks)
{
team2Tasks.SetCoefficient(x[worker, task], 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.");
}
}
}