Chỉ định bằng Nhóm được phép

Phần này mô tả một sự cố bài tập trong đó chỉ một số bài tập được cho phép có thể chỉ định nhóm nhân viên cho nhiệm vụ. Trong ví dụ này, có 12 nhân viên, được đánh số từ 0 đến 11. Các nhóm được phép là sự kết hợp của các cặp worker sau.

  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]]

Một nhóm được phép có thể là bất kỳ tổ hợp nào của 3 cặp worker, một cặp từ từng thuộc tính group1, group2 và group3. Ví dụ: kết hợp [2, 3], [6, 7] và [10, 11] sẽ dẫn đến kết quả được phép nhóm [2, 3, 6, 7, 10, 11]. Do mỗi tập hợp đều chứa năm phần tử, nên tổng số giá trị được phép nhóm là 5 * 5 * 5 = 125.

Lưu ý rằng một nhóm worker có thể là giải pháp cho vấn đề nếu nhóm đó thuộc về bất kỳ nhóm nào trong số các nhóm được phép. Nói cách khác, tập hợp khả thi bao gồm các điểm thỏa mãn bất kỳ điều kiện ràng buộc nào. Đây là một ví dụ về bài toán không lồi. Ngược lại, Ví dụ về MIP được mô tả trước đây, là bài toán lồi: để một điểm khả thi, tất cả điều kiện ràng buộc phải được hài lòng.

Đối với các bài toán không lồi như bài tập này, trình giải CP-SAT thường nhanh hơn một trình giải quyết MIP (MIP). Các phần sau đây trình bày giải pháp cho vấn đề bằng trình giải quyết CP-SAT và trình giải MIP, đồng thời so sánh thời gian giải của hai cách giải.

Giải pháp CP-SAT

Trước tiên, chúng tôi sẽ mô tả cách giải cho vấn đề đó bằng trình giải quyết CP-SAT.

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 <cstdint>
#include <numeric>
#include <vector>

#include "absl/strings/str_format.h"
#include "absl/types/span.h"
#include "ortools/base/logging.h"
#include "ortools/sat/cp_model.h"
#include "ortools/sat/cp_model.pb.h"
#include "ortools/sat/cp_model_solver.h"

Java

import com.google.ortools.Loader;
import com.google.ortools.sat.CpModel;
import com.google.ortools.sat.CpSolver;
import com.google.ortools.sat.CpSolverStatus;
import com.google.ortools.sat.IntVar;
import com.google.ortools.sat.LinearExpr;
import com.google.ortools.sat.LinearExprBuilder;
import com.google.ortools.sat.Literal;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.IntStream;

C#

using System;
using System.Collections.Generic;
using System.Linq;
using Google.OrTools.Sat;

Xác định dữ liệu

Đoạn mã sau đây sẽ tạo dữ liệu cho chương trình.

Python

costs = [
    [90, 76, 75, 70, 50, 74],
    [35, 85, 55, 65, 48, 101],
    [125, 95, 90, 105, 59, 120],
    [45, 110, 95, 115, 104, 83],
    [60, 105, 80, 75, 59, 62],
    [45, 65, 110, 95, 47, 31],
    [38, 51, 107, 41, 69, 99],
    [47, 85, 57, 71, 92, 77],
    [39, 63, 97, 49, 118, 56],
    [47, 101, 71, 60, 88, 109],
    [17, 39, 103, 64, 61, 92],
    [101, 45, 83, 59, 92, 27],
]
num_workers = len(costs)
num_tasks = len(costs[0])

C++

const std::vector<std::vector<int>> costs = {{
    {{90, 76, 75, 70, 50, 74}},
    {{35, 85, 55, 65, 48, 101}},
    {{125, 95, 90, 105, 59, 120}},
    {{45, 110, 95, 115, 104, 83}},
    {{60, 105, 80, 75, 59, 62}},
    {{45, 65, 110, 95, 47, 31}},
    {{38, 51, 107, 41, 69, 99}},
    {{47, 85, 57, 71, 92, 77}},
    {{39, 63, 97, 49, 118, 56}},
    {{47, 101, 71, 60, 88, 109}},
    {{17, 39, 103, 64, 61, 92}},
    {{101, 45, 83, 59, 92, 27}},
}};
const int num_workers = static_cast<int>(costs.size());
std::vector<int> all_workers(num_workers);
std::iota(all_workers.begin(), all_workers.end(), 0);

const int num_tasks = static_cast<int>(costs[0].size());
std::vector<int> all_tasks(num_tasks);
std::iota(all_tasks.begin(), all_tasks.end(), 0);

Java

int[][] costs = {
    {90, 76, 75, 70, 50, 74},
    {35, 85, 55, 65, 48, 101},
    {125, 95, 90, 105, 59, 120},
    {45, 110, 95, 115, 104, 83},
    {60, 105, 80, 75, 59, 62},
    {45, 65, 110, 95, 47, 31},
    {38, 51, 107, 41, 69, 99},
    {47, 85, 57, 71, 92, 77},
    {39, 63, 97, 49, 118, 56},
    {47, 101, 71, 60, 88, 109},
    {17, 39, 103, 64, 61, 92},
    {101, 45, 83, 59, 92, 27},
};
final int numWorkers = costs.length;
final int numTasks = costs[0].length;

final int[] allWorkers = IntStream.range(0, numWorkers).toArray();
final int[] allTasks = IntStream.range(0, numTasks).toArray();

C#

int[,] costs = {
    { 90, 76, 75, 70, 50, 74 },    { 35, 85, 55, 65, 48, 101 }, { 125, 95, 90, 105, 59, 120 },
    { 45, 110, 95, 115, 104, 83 }, { 60, 105, 80, 75, 59, 62 }, { 45, 65, 110, 95, 47, 31 },
    { 38, 51, 107, 41, 69, 99 },   { 47, 85, 57, 71, 92, 77 },  { 39, 63, 97, 49, 118, 56 },
    { 47, 101, 71, 60, 88, 109 },  { 17, 39, 103, 64, 61, 92 }, { 101, 45, 83, 59, 92, 27 },
};
int numWorkers = costs.GetLength(0);
int numTasks = costs.GetLength(1);

int[] allWorkers = Enumerable.Range(0, numWorkers).ToArray();
int[] allTasks = Enumerable.Range(0, numTasks).ToArray();

Tạo các nhóm được phép

Để xác định các nhóm worker được phép cho trình giải CP-SAT, bạn hãy tạo tệp nhị phân các mảng cho biết worker nào thuộc một nhóm. Ví dụ: đối với group1 (worker 0 - 3), vectơ nhị phân [0, 0, 1, 1] chỉ định nhóm chứa nhân viên 2 và 3.

Lưu ý: Bằng cách này, việc chỉ định nhóm sẽ hơi khác so với cách được chỉ định trong giải pháp MIP, nhưng tương tự như vậy.

Các mảng sau đây xác định các nhóm worker được phép.

Python

group1 = [
    [0, 0, 1, 1],  # Workers 2, 3
    [0, 1, 0, 1],  # Workers 1, 3
    [0, 1, 1, 0],  # Workers 1, 2
    [1, 1, 0, 0],  # Workers 0, 1
    [1, 0, 1, 0],  # Workers 0, 2
]

group2 = [
    [0, 0, 1, 1],  # Workers 6, 7
    [0, 1, 0, 1],  # Workers 5, 7
    [0, 1, 1, 0],  # Workers 5, 6
    [1, 1, 0, 0],  # Workers 4, 5
    [1, 0, 0, 1],  # Workers 4, 7
]

group3 = [
    [0, 0, 1, 1],  # Workers 10, 11
    [0, 1, 0, 1],  # Workers 9, 11
    [0, 1, 1, 0],  # Workers 9, 10
    [1, 0, 1, 0],  # Workers 8, 10
    [1, 0, 0, 1],  # Workers 8, 11
]

C++

const std::vector<std::vector<int64_t>> group1 = {{
    {{0, 0, 1, 1}},  // Workers 2, 3
    {{0, 1, 0, 1}},  // Workers 1, 3
    {{0, 1, 1, 0}},  // Workers 1, 2
    {{1, 1, 0, 0}},  // Workers 0, 1
    {{1, 0, 1, 0}},  // Workers 0, 2
}};

const std::vector<std::vector<int64_t>> group2 = {{
    {{0, 0, 1, 1}},  // Workers 6, 7
    {{0, 1, 0, 1}},  // Workers 5, 7
    {{0, 1, 1, 0}},  // Workers 5, 6
    {{1, 1, 0, 0}},  // Workers 4, 5
    {{1, 0, 0, 1}},  // Workers 4, 7
}};

const std::vector<std::vector<int64_t>> group3 = {{
    {{0, 0, 1, 1}},  // Workers 10, 11
    {{0, 1, 0, 1}},  // Workers 9, 11
    {{0, 1, 1, 0}},  // Workers 9, 10
    {{1, 0, 1, 0}},  // Workers 8, 10
    {{1, 0, 0, 1}},  // Workers 8, 11
}};

Java

int[][] group1 = {
    {0, 0, 1, 1}, // Workers 2, 3
    {0, 1, 0, 1}, // Workers 1, 3
    {0, 1, 1, 0}, // Workers 1, 2
    {1, 1, 0, 0}, // Workers 0, 1
    {1, 0, 1, 0}, // Workers 0, 2
};

int[][] group2 = {
    {0, 0, 1, 1}, // Workers 6, 7
    {0, 1, 0, 1}, // Workers 5, 7
    {0, 1, 1, 0}, // Workers 5, 6
    {1, 1, 0, 0}, // Workers 4, 5
    {1, 0, 0, 1}, // Workers 4, 7
};

int[][] group3 = {
    {0, 0, 1, 1}, // Workers 10, 11
    {0, 1, 0, 1}, // Workers 9, 11
    {0, 1, 1, 0}, // Workers 9, 10
    {1, 0, 1, 0}, // Workers 8, 10
    {1, 0, 0, 1}, // Workers 8, 11
};

C#

long[,] group1 = {
    { 0, 0, 1, 1 }, // Workers 2, 3
    { 0, 1, 0, 1 }, // Workers 1, 3
    { 0, 1, 1, 0 }, // Workers 1, 2
    { 1, 1, 0, 0 }, // Workers 0, 1
    { 1, 0, 1, 0 }, // Workers 0, 2
};

long[,] group2 = {
    { 0, 0, 1, 1 }, // Workers 6, 7
    { 0, 1, 0, 1 }, // Workers 5, 7
    { 0, 1, 1, 0 }, // Workers 5, 6
    { 1, 1, 0, 0 }, // Workers 4, 5
    { 1, 0, 0, 1 }, // Workers 4, 7
};

long[,] group3 = {
    { 0, 0, 1, 1 }, // Workers 10, 11
    { 0, 1, 0, 1 }, // Workers 9, 11
    { 0, 1, 1, 0 }, // Workers 9, 10
    { 1, 0, 1, 0 }, // Workers 8, 10
    { 1, 0, 0, 1 }, // Workers 8, 11
};

Đối với CP-SAT, không cần thiết phải tạo tất cả 125 tổ hợp của các vectơ này trong một vòng lặp. Trình giải CP-SAT cung cấp một phương pháp, AllowedAssignments, cho phép bạn chỉ định riêng các hạn chế cho các nhóm được phép cho mỗi nhóm trong số ba nhóm công nhân (0 – 3, 4 – 7 và 8 – 11). Cách hoạt động như sau:

Python

# Create variables for each worker, indicating whether they work on some task.
work = {}
for worker in range(num_workers):
    work[worker] = model.new_bool_var(f"work[{worker}]")

for worker in range(num_workers):
    for task in range(num_tasks):
        model.add(work[worker] == sum(x[worker, task] for task in range(num_tasks)))

# Define the allowed groups of worders
model.add_allowed_assignments([work[0], work[1], work[2], work[3]], group1)
model.add_allowed_assignments([work[4], work[5], work[6], work[7]], group2)
model.add_allowed_assignments([work[8], work[9], work[10], work[11]], group3)

C++

// Create variables for each worker, indicating whether they work on some
// task.
std::vector<IntVar> work(num_workers);
for (int worker : all_workers) {
  work[worker] = IntVar(
      cp_model.NewBoolVar().WithName(absl::StrFormat("work[%d]", worker)));
}

for (int worker : all_workers) {
  LinearExpr task_sum;
  for (int task : all_tasks) {
    task_sum += x[worker][task];
  }
  cp_model.AddEquality(work[worker], task_sum);
}

// Define the allowed groups of worders
auto table1 =
    cp_model.AddAllowedAssignments({work[0], work[1], work[2], work[3]});
for (const auto& t : group1) {
  table1.AddTuple(t);
}
auto table2 =
    cp_model.AddAllowedAssignments({work[4], work[5], work[6], work[7]});
for (const auto& t : group2) {
  table2.AddTuple(t);
}
auto table3 =
    cp_model.AddAllowedAssignments({work[8], work[9], work[10], work[11]});
for (const auto& t : group3) {
  table3.AddTuple(t);
}

Java

// Create variables for each worker, indicating whether they work on some task.
IntVar[] work = new IntVar[numWorkers];
for (int worker : allWorkers) {
  work[worker] = model.newBoolVar("work[" + worker + "]");
}

for (int worker : allWorkers) {
  LinearExprBuilder expr = LinearExpr.newBuilder();
  for (int task : allTasks) {
    expr.add(x[worker][task]);
  }
  model.addEquality(work[worker], expr);
}

// Define the allowed groups of worders
model.addAllowedAssignments(new IntVar[] {work[0], work[1], work[2], work[3]})
    .addTuples(group1);
model.addAllowedAssignments(new IntVar[] {work[4], work[5], work[6], work[7]})
    .addTuples(group2);
model.addAllowedAssignments(new IntVar[] {work[8], work[9], work[10], work[11]})
    .addTuples(group3);

C#

// Create variables for each worker, indicating whether they work on some task.
BoolVar[] work = new BoolVar[numWorkers];
foreach (int worker in allWorkers)
{
    work[worker] = model.NewBoolVar($"work[{worker}]");
}

foreach (int worker in allWorkers)
{
    List<ILiteral> tasks = new List<ILiteral>();
    foreach (int task in allTasks)
    {
        tasks.Add(x[worker, task]);
    }
    model.Add(work[worker] == LinearExpr.Sum(tasks));
}

// Define the allowed groups of worders
model.AddAllowedAssignments(new IntVar[] { work[0], work[1], work[2], work[3] }).AddTuples(group1);
model.AddAllowedAssignments(new IntVar[] { work[4], work[5], work[6], work[7] }).AddTuples(group2);
model.AddAllowedAssignments(new IntVar[] { work[8], work[9], work[10], work[11] }).AddTuples(group3);

Biến work[i] là các biến 0-1 cho biết trạng thái công việc hoặc mỗi worker. Tức là work[i] bằng 1 nếu worker i được giao cho một tác vụ, và 0. Đường kẻ solver.Add(solver.AllowedAssignments([work[0], work[1], work[2], work[3]], group1)) xác định ràng buộc mà trạng thái công việc của worker 0 - 3 phải phù hợp với một trong các mẫu trong group1. Bạn có thể xem toàn bộ thông tin chi tiết về mã trong phần .

Tạo mô hình

Đoạn 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 biến

Mã sau đây sẽ tạo một mảng các biến cho bài toán này.

Python

x = {}
for worker in range(num_workers):
    for task in range(num_tasks):
        x[worker, task] = model.new_bool_var(f"x[{worker},{task}]")

C++

// x[i][j] is an array of Boolean variables. x[i][j] is true
// if worker i is assigned to task j.
std::vector<std::vector<BoolVar>> x(num_workers,
                                    std::vector<BoolVar>(num_tasks));
for (int worker : all_workers) {
  for (int task : all_tasks) {
    x[worker][task] = cp_model.NewBoolVar().WithName(
        absl::StrFormat("x[%d,%d]", worker, task));
  }
}

Java

Literal[][] x = new Literal[numWorkers][numTasks];
for (int worker : allWorkers) {
  for (int task : allTasks) {
    x[worker][task] = model.newBoolVar("x[" + worker + "," + task + "]");
  }
}

C#

BoolVar[,] x = new BoolVar[numWorkers, numTasks];
// Variables in a 1-dim array.
foreach (int worker in allWorkers)
{
    foreach (int task in allTasks)
    {
        x[worker, task] = model.NewBoolVar($"x[{worker},{task}]");
    }
}

Thêm các điều kiện ràng buộc

Mã sau đây tạo các quy tắc 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))

C++

// Each worker is assigned to at most one task.
for (int worker : all_workers) {
  cp_model.AddAtMostOne(x[worker]);
}
// Each task is assigned to exactly one worker.
for (int task : all_tasks) {
  std::vector<BoolVar> tasks;
  for (int worker : all_workers) {
    tasks.push_back(x[worker][task]);
  }
  cp_model.AddExactlyOne(tasks);
}

Java

// Each worker is assigned to at most one task.
for (int worker : allWorkers) {
  List<Literal> tasks = new ArrayList<>();
  for (int task : allTasks) {
    tasks.add(x[worker][task]);
  }
  model.addAtMostOne(tasks);
}

// Each task is assigned to exactly one worker.
for (int task : allTasks) {
  List<Literal> workers = new ArrayList<>();
  for (int worker : allWorkers) {
    workers.add(x[worker][task]);
  }
  model.addExactlyOne(workers);
}

C#

// Each worker is assigned to at most one task.
foreach (int worker in allWorkers)
{
    List<ILiteral> tasks = new List<ILiteral>();
    foreach (int task in allTasks)
    {
        tasks.Add(x[worker, task]);
    }
    model.AddAtMostOne(tasks);
}

// Each task is assigned to exactly one worker.
foreach (int task in allTasks)
{
    List<ILiteral> workers = new List<ILiteral>();
    foreach (int worker in allWorkers)
    {
        workers.Add(x[worker, task]);
    }
    model.AddExactlyOne(workers);
}

Tạo mục tiêu

Mã sau đây sẽ 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);

Gọi trình giải

Mã sau đây gọi trình 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 thị 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.

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

Toàn bộ chương trình

Sau đây là toàn bộ chương trình.

Python

"""Solves an assignment problem for given group of workers."""
from ortools.sat.python import cp_model


def main() -> None:
    # Data
    costs = [
        [90, 76, 75, 70, 50, 74],
        [35, 85, 55, 65, 48, 101],
        [125, 95, 90, 105, 59, 120],
        [45, 110, 95, 115, 104, 83],
        [60, 105, 80, 75, 59, 62],
        [45, 65, 110, 95, 47, 31],
        [38, 51, 107, 41, 69, 99],
        [47, 85, 57, 71, 92, 77],
        [39, 63, 97, 49, 118, 56],
        [47, 101, 71, 60, 88, 109],
        [17, 39, 103, 64, 61, 92],
        [101, 45, 83, 59, 92, 27],
    ]
    num_workers = len(costs)
    num_tasks = len(costs[0])

    # Allowed groups of workers:
    group1 = [
        [0, 0, 1, 1],  # Workers 2, 3
        [0, 1, 0, 1],  # Workers 1, 3
        [0, 1, 1, 0],  # Workers 1, 2
        [1, 1, 0, 0],  # Workers 0, 1
        [1, 0, 1, 0],  # Workers 0, 2
    ]

    group2 = [
        [0, 0, 1, 1],  # Workers 6, 7
        [0, 1, 0, 1],  # Workers 5, 7
        [0, 1, 1, 0],  # Workers 5, 6
        [1, 1, 0, 0],  # Workers 4, 5
        [1, 0, 0, 1],  # Workers 4, 7
    ]

    group3 = [
        [0, 0, 1, 1],  # Workers 10, 11
        [0, 1, 0, 1],  # Workers 9, 11
        [0, 1, 1, 0],  # Workers 9, 10
        [1, 0, 1, 0],  # Workers 8, 10
        [1, 0, 0, 1],  # Workers 8, 11
    ]

    # Model
    model = cp_model.CpModel()

    # Variables
    x = {}
    for worker in range(num_workers):
        for task in range(num_tasks):
            x[worker, task] = model.new_bool_var(f"x[{worker},{task}]")

    # Constraints
    # Each worker is assigned to at most one task.
    for worker in range(num_workers):
        model.add_at_most_one(x[worker, task] for task in range(num_tasks))

    # Each task is assigned to exactly one worker.
    for task in range(num_tasks):
        model.add_exactly_one(x[worker, task] for worker in range(num_workers))

    # Create variables for each worker, indicating whether they work on some task.
    work = {}
    for worker in range(num_workers):
        work[worker] = model.new_bool_var(f"work[{worker}]")

    for worker in range(num_workers):
        for task in range(num_tasks):
            model.add(work[worker] == sum(x[worker, task] for task in range(num_tasks)))

    # Define the allowed groups of worders
    model.add_allowed_assignments([work[0], work[1], work[2], work[3]], group1)
    model.add_allowed_assignments([work[4], work[5], work[6], work[7]], group2)
    model.add_allowed_assignments([work[8], work[9], work[10], work[11]], group3)

    # Objective
    objective_terms = []
    for worker in range(num_workers):
        for task in range(num_tasks):
            objective_terms.append(costs[worker][task] * x[worker, task])
    model.minimize(sum(objective_terms))

    # Solve
    solver = cp_model.CpSolver()
    status = solver.solve(model)

    # Print solution.
    if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
        print(f"Total cost = {solver.objective_value}\n")
        for worker in range(num_workers):
            for task in range(num_tasks):
                if solver.boolean_value(x[worker, task]):
                    print(
                        f"Worker {worker} assigned to task {task}."
                        + f" Cost = {costs[worker][task]}"
                    )
    else:
        print("No solution found.")


if __name__ == "__main__":
    main()

C++

// Solve assignment problem for given group of workers.
#include <stdlib.h>

#include <cstdint>
#include <numeric>
#include <vector>

#include "absl/strings/str_format.h"
#include "absl/types/span.h"
#include "ortools/base/logging.h"
#include "ortools/sat/cp_model.h"
#include "ortools/sat/cp_model.pb.h"
#include "ortools/sat/cp_model_solver.h"

namespace operations_research {
namespace sat {

void AssignmentGroups() {
  // Data
  const std::vector<std::vector<int>> costs = {{
      {{90, 76, 75, 70, 50, 74}},
      {{35, 85, 55, 65, 48, 101}},
      {{125, 95, 90, 105, 59, 120}},
      {{45, 110, 95, 115, 104, 83}},
      {{60, 105, 80, 75, 59, 62}},
      {{45, 65, 110, 95, 47, 31}},
      {{38, 51, 107, 41, 69, 99}},
      {{47, 85, 57, 71, 92, 77}},
      {{39, 63, 97, 49, 118, 56}},
      {{47, 101, 71, 60, 88, 109}},
      {{17, 39, 103, 64, 61, 92}},
      {{101, 45, 83, 59, 92, 27}},
  }};
  const int num_workers = static_cast<int>(costs.size());
  std::vector<int> all_workers(num_workers);
  std::iota(all_workers.begin(), all_workers.end(), 0);

  const int num_tasks = static_cast<int>(costs[0].size());
  std::vector<int> all_tasks(num_tasks);
  std::iota(all_tasks.begin(), all_tasks.end(), 0);

  // Allowed groups of workers:
  const std::vector<std::vector<int64_t>> group1 = {{
      {{0, 0, 1, 1}},  // Workers 2, 3
      {{0, 1, 0, 1}},  // Workers 1, 3
      {{0, 1, 1, 0}},  // Workers 1, 2
      {{1, 1, 0, 0}},  // Workers 0, 1
      {{1, 0, 1, 0}},  // Workers 0, 2
  }};

  const std::vector<std::vector<int64_t>> group2 = {{
      {{0, 0, 1, 1}},  // Workers 6, 7
      {{0, 1, 0, 1}},  // Workers 5, 7
      {{0, 1, 1, 0}},  // Workers 5, 6
      {{1, 1, 0, 0}},  // Workers 4, 5
      {{1, 0, 0, 1}},  // Workers 4, 7
  }};

  const std::vector<std::vector<int64_t>> group3 = {{
      {{0, 0, 1, 1}},  // Workers 10, 11
      {{0, 1, 0, 1}},  // Workers 9, 11
      {{0, 1, 1, 0}},  // Workers 9, 10
      {{1, 0, 1, 0}},  // Workers 8, 10
      {{1, 0, 0, 1}},  // Workers 8, 11
  }};

  // Model
  CpModelBuilder cp_model;

  // Variables
  // x[i][j] is an array of Boolean variables. x[i][j] is true
  // if worker i is assigned to task j.
  std::vector<std::vector<BoolVar>> x(num_workers,
                                      std::vector<BoolVar>(num_tasks));
  for (int worker : all_workers) {
    for (int task : all_tasks) {
      x[worker][task] = cp_model.NewBoolVar().WithName(
          absl::StrFormat("x[%d,%d]", worker, task));
    }
  }

  // Constraints
  // Each worker is assigned to at most one task.
  for (int worker : all_workers) {
    cp_model.AddAtMostOne(x[worker]);
  }
  // Each task is assigned to exactly one worker.
  for (int task : all_tasks) {
    std::vector<BoolVar> tasks;
    for (int worker : all_workers) {
      tasks.push_back(x[worker][task]);
    }
    cp_model.AddExactlyOne(tasks);
  }

  // Create variables for each worker, indicating whether they work on some
  // task.
  std::vector<IntVar> work(num_workers);
  for (int worker : all_workers) {
    work[worker] = IntVar(
        cp_model.NewBoolVar().WithName(absl::StrFormat("work[%d]", worker)));
  }

  for (int worker : all_workers) {
    LinearExpr task_sum;
    for (int task : all_tasks) {
      task_sum += x[worker][task];
    }
    cp_model.AddEquality(work[worker], task_sum);
  }

  // Define the allowed groups of worders
  auto table1 =
      cp_model.AddAllowedAssignments({work[0], work[1], work[2], work[3]});
  for (const auto& t : group1) {
    table1.AddTuple(t);
  }
  auto table2 =
      cp_model.AddAllowedAssignments({work[4], work[5], work[6], work[7]});
  for (const auto& t : group2) {
    table2.AddTuple(t);
  }
  auto table3 =
      cp_model.AddAllowedAssignments({work[8], work[9], work[10], work[11]});
  for (const auto& t : group3) {
    table3.AddTuple(t);
  }

  // Objective
  LinearExpr total_cost;
  for (int worker : all_workers) {
    for (int task : all_tasks) {
      total_cost += x[worker][task] * costs[worker][task];
    }
  }
  cp_model.Minimize(total_cost);

  // Solve
  const CpSolverResponse response = Solve(cp_model.Build());

  // Print solution.
  if (response.status() == CpSolverStatus::INFEASIBLE) {
    LOG(FATAL) << "No solution found.";
  }
  LOG(INFO) << "Total cost: " << response.objective_value();
  LOG(INFO);
  for (int worker : all_workers) {
    for (int task : all_tasks) {
      if (SolutionBooleanValue(response, x[worker][task])) {
        LOG(INFO) << "Worker " << worker << " assigned to task " << task
                  << ".  Cost: " << costs[worker][task];
      }
    }
  }
}
}  // namespace sat
}  // namespace operations_research

int main(int argc, char** argv) {
  operations_research::sat::AssignmentGroups();
  return EXIT_SUCCESS;
}

Java

// CP-SAT example that solves an assignment problem.
package com.google.ortools.sat.samples;
import com.google.ortools.Loader;
import com.google.ortools.sat.CpModel;
import com.google.ortools.sat.CpSolver;
import com.google.ortools.sat.CpSolverStatus;
import com.google.ortools.sat.IntVar;
import com.google.ortools.sat.LinearExpr;
import com.google.ortools.sat.LinearExprBuilder;
import com.google.ortools.sat.Literal;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.IntStream;

/** Assignment problem. */
public class AssignmentGroupsSat {
  public static void main(String[] args) {
    Loader.loadNativeLibraries();
    // Data
    int[][] costs = {
        {90, 76, 75, 70, 50, 74},
        {35, 85, 55, 65, 48, 101},
        {125, 95, 90, 105, 59, 120},
        {45, 110, 95, 115, 104, 83},
        {60, 105, 80, 75, 59, 62},
        {45, 65, 110, 95, 47, 31},
        {38, 51, 107, 41, 69, 99},
        {47, 85, 57, 71, 92, 77},
        {39, 63, 97, 49, 118, 56},
        {47, 101, 71, 60, 88, 109},
        {17, 39, 103, 64, 61, 92},
        {101, 45, 83, 59, 92, 27},
    };
    final int numWorkers = costs.length;
    final int numTasks = costs[0].length;

    final int[] allWorkers = IntStream.range(0, numWorkers).toArray();
    final int[] allTasks = IntStream.range(0, numTasks).toArray();

    // Allowed groups of workers:
    int[][] group1 = {
        {0, 0, 1, 1}, // Workers 2, 3
        {0, 1, 0, 1}, // Workers 1, 3
        {0, 1, 1, 0}, // Workers 1, 2
        {1, 1, 0, 0}, // Workers 0, 1
        {1, 0, 1, 0}, // Workers 0, 2
    };

    int[][] group2 = {
        {0, 0, 1, 1}, // Workers 6, 7
        {0, 1, 0, 1}, // Workers 5, 7
        {0, 1, 1, 0}, // Workers 5, 6
        {1, 1, 0, 0}, // Workers 4, 5
        {1, 0, 0, 1}, // Workers 4, 7
    };

    int[][] group3 = {
        {0, 0, 1, 1}, // Workers 10, 11
        {0, 1, 0, 1}, // Workers 9, 11
        {0, 1, 1, 0}, // Workers 9, 10
        {1, 0, 1, 0}, // Workers 8, 10
        {1, 0, 0, 1}, // Workers 8, 11
    };

    // Model
    CpModel model = new CpModel();

    // Variables
    Literal[][] x = new Literal[numWorkers][numTasks];
    for (int worker : allWorkers) {
      for (int task : allTasks) {
        x[worker][task] = model.newBoolVar("x[" + worker + "," + task + "]");
      }
    }

    // Constraints
    // Each worker is assigned to at most one task.
    for (int worker : allWorkers) {
      List<Literal> tasks = new ArrayList<>();
      for (int task : allTasks) {
        tasks.add(x[worker][task]);
      }
      model.addAtMostOne(tasks);
    }

    // Each task is assigned to exactly one worker.
    for (int task : allTasks) {
      List<Literal> workers = new ArrayList<>();
      for (int worker : allWorkers) {
        workers.add(x[worker][task]);
      }
      model.addExactlyOne(workers);
    }

    // Create variables for each worker, indicating whether they work on some task.
    IntVar[] work = new IntVar[numWorkers];
    for (int worker : allWorkers) {
      work[worker] = model.newBoolVar("work[" + worker + "]");
    }

    for (int worker : allWorkers) {
      LinearExprBuilder expr = LinearExpr.newBuilder();
      for (int task : allTasks) {
        expr.add(x[worker][task]);
      }
      model.addEquality(work[worker], expr);
    }

    // Define the allowed groups of worders
    model.addAllowedAssignments(new IntVar[] {work[0], work[1], work[2], work[3]})
        .addTuples(group1);
    model.addAllowedAssignments(new IntVar[] {work[4], work[5], work[6], work[7]})
        .addTuples(group2);
    model.addAllowedAssignments(new IntVar[] {work[8], work[9], work[10], work[11]})
        .addTuples(group3);

    // Objective
    LinearExprBuilder obj = LinearExpr.newBuilder();
    for (int worker : allWorkers) {
      for (int task : allTasks) {
        obj.addTerm(x[worker][task], costs[worker][task]);
      }
    }
    model.minimize(obj);

    // Solve
    CpSolver solver = new CpSolver();
    CpSolverStatus status = solver.solve(model);

    // Print solution.
    // Check that the problem has a feasible solution.
    if (status == CpSolverStatus.OPTIMAL || status == CpSolverStatus.FEASIBLE) {
      System.out.println("Total cost: " + solver.objectiveValue() + "\n");
      for (int worker : allWorkers) {
        for (int task : allTasks) {
          if (solver.booleanValue(x[worker][task])) {
            System.out.println("Worker " + worker + " assigned to task " + task
                + ".  Cost: " + costs[worker][task]);
          }
        }
      }
    } else {
      System.err.println("No solution found.");
    }
  }

  private AssignmentGroupsSat() {}
}

C#

using System;
using System.Collections.Generic;
using System.Linq;
using Google.OrTools.Sat;

public class AssignmentGroupsSat
{
    public static void Main(String[] args)
    {
        // Data.
        int[,] costs = {
            { 90, 76, 75, 70, 50, 74 },    { 35, 85, 55, 65, 48, 101 }, { 125, 95, 90, 105, 59, 120 },
            { 45, 110, 95, 115, 104, 83 }, { 60, 105, 80, 75, 59, 62 }, { 45, 65, 110, 95, 47, 31 },
            { 38, 51, 107, 41, 69, 99 },   { 47, 85, 57, 71, 92, 77 },  { 39, 63, 97, 49, 118, 56 },
            { 47, 101, 71, 60, 88, 109 },  { 17, 39, 103, 64, 61, 92 }, { 101, 45, 83, 59, 92, 27 },
        };
        int numWorkers = costs.GetLength(0);
        int numTasks = costs.GetLength(1);

        int[] allWorkers = Enumerable.Range(0, numWorkers).ToArray();
        int[] allTasks = Enumerable.Range(0, numTasks).ToArray();

        // Allowed groups of workers:
        long[,] group1 = {
            { 0, 0, 1, 1 }, // Workers 2, 3
            { 0, 1, 0, 1 }, // Workers 1, 3
            { 0, 1, 1, 0 }, // Workers 1, 2
            { 1, 1, 0, 0 }, // Workers 0, 1
            { 1, 0, 1, 0 }, // Workers 0, 2
        };

        long[,] group2 = {
            { 0, 0, 1, 1 }, // Workers 6, 7
            { 0, 1, 0, 1 }, // Workers 5, 7
            { 0, 1, 1, 0 }, // Workers 5, 6
            { 1, 1, 0, 0 }, // Workers 4, 5
            { 1, 0, 0, 1 }, // Workers 4, 7
        };

        long[,] group3 = {
            { 0, 0, 1, 1 }, // Workers 10, 11
            { 0, 1, 0, 1 }, // Workers 9, 11
            { 0, 1, 1, 0 }, // Workers 9, 10
            { 1, 0, 1, 0 }, // Workers 8, 10
            { 1, 0, 0, 1 }, // Workers 8, 11
        };

        // Model.
        CpModel model = new CpModel();

        // Variables.
        BoolVar[,] x = new BoolVar[numWorkers, numTasks];
        // Variables in a 1-dim array.
        foreach (int worker in allWorkers)
        {
            foreach (int task in allTasks)
            {
                x[worker, task] = model.NewBoolVar($"x[{worker},{task}]");
            }
        }

        // Constraints
        // Each worker is assigned to at most one task.
        foreach (int worker in allWorkers)
        {
            List<ILiteral> tasks = new List<ILiteral>();
            foreach (int task in allTasks)
            {
                tasks.Add(x[worker, task]);
            }
            model.AddAtMostOne(tasks);
        }

        // Each task is assigned to exactly one worker.
        foreach (int task in allTasks)
        {
            List<ILiteral> workers = new List<ILiteral>();
            foreach (int worker in allWorkers)
            {
                workers.Add(x[worker, task]);
            }
            model.AddExactlyOne(workers);
        }

        // Create variables for each worker, indicating whether they work on some task.
        BoolVar[] work = new BoolVar[numWorkers];
        foreach (int worker in allWorkers)
        {
            work[worker] = model.NewBoolVar($"work[{worker}]");
        }

        foreach (int worker in allWorkers)
        {
            List<ILiteral> tasks = new List<ILiteral>();
            foreach (int task in allTasks)
            {
                tasks.Add(x[worker, task]);
            }
            model.Add(work[worker] == LinearExpr.Sum(tasks));
        }

        // Define the allowed groups of worders
        model.AddAllowedAssignments(new IntVar[] { work[0], work[1], work[2], work[3] }).AddTuples(group1);
        model.AddAllowedAssignments(new IntVar[] { work[4], work[5], work[6], work[7] }).AddTuples(group2);
        model.AddAllowedAssignments(new IntVar[] { work[8], work[9], work[10], work[11] }).AddTuples(group3);

        // Objective
        LinearExprBuilder obj = LinearExpr.NewBuilder();
        foreach (int worker in allWorkers)
        {
            foreach (int task in allTasks)
            {
                obj.AddTerm(x[worker, task], costs[worker, task]);
            }
        }
        model.Minimize(obj);

        // Solve
        CpSolver solver = new CpSolver();
        CpSolverStatus status = solver.Solve(model);
        Console.WriteLine($"Solve status: {status}");

        // Print solution.
        // Check that the problem has a feasible solution.
        if (status == CpSolverStatus.Optimal || status == CpSolverStatus.Feasible)
        {
            Console.WriteLine($"Total cost: {solver.ObjectiveValue}\n");
            foreach (int worker in allWorkers)
            {
                foreach (int task in allTasks)
                {
                    if (solver.Value(x[worker, task]) > 0.5)
                    {
                        Console.WriteLine($"Worker {worker} assigned to task {task}. " +
                                          $"Cost: {costs[worker, task]}");
                    }
                }
            }
        }
        else
        {
            Console.WriteLine("No solution found.");
        }

        Console.WriteLine("Statistics");
        Console.WriteLine($"  - conflicts : {solver.NumConflicts()}");
        Console.WriteLine($"  - branches  : {solver.NumBranches()}");
        Console.WriteLine($"  - wall time : {solver.WallTime()}s");
    }
}

Giải pháp MIP

Tiếp theo, chúng tôi sẽ mô tả một giải pháp cho bài toán đó bằng trình giải quyết MIP (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 <utility>
#include <vector>

#include "absl/strings/str_format.h"
#include "ortools/base/logging.h"
#include "ortools/linear_solver/linear_solver.h"

Java

import com.google.ortools.Loader;
import com.google.ortools.linearsolver.MPConstraint;
import com.google.ortools.linearsolver.MPObjective;
import com.google.ortools.linearsolver.MPSolver;
import com.google.ortools.linearsolver.MPVariable;
import java.util.stream.IntStream;

C#

using System;
using System.Collections.Generic;
using System.Linq;
using Google.OrTools.LinearSolver;

Xác định dữ liệu

Đoạn mã sau đây sẽ tạo dữ liệu cho chương trình.

Python

costs = [
    [90, 76, 75, 70, 50, 74],
    [35, 85, 55, 65, 48, 101],
    [125, 95, 90, 105, 59, 120],
    [45, 110, 95, 115, 104, 83],
    [60, 105, 80, 75, 59, 62],
    [45, 65, 110, 95, 47, 31],
    [38, 51, 107, 41, 69, 99],
    [47, 85, 57, 71, 92, 77],
    [39, 63, 97, 49, 118, 56],
    [47, 101, 71, 60, 88, 109],
    [17, 39, 103, 64, 61, 92],
    [101, 45, 83, 59, 92, 27],
]
num_workers = len(costs)
num_tasks = len(costs[0])

C++

const std::vector<std::vector<int64_t>> costs = {{
    {{90, 76, 75, 70, 50, 74}},
    {{35, 85, 55, 65, 48, 101}},
    {{125, 95, 90, 105, 59, 120}},
    {{45, 110, 95, 115, 104, 83}},
    {{60, 105, 80, 75, 59, 62}},
    {{45, 65, 110, 95, 47, 31}},
    {{38, 51, 107, 41, 69, 99}},
    {{47, 85, 57, 71, 92, 77}},
    {{39, 63, 97, 49, 118, 56}},
    {{47, 101, 71, 60, 88, 109}},
    {{17, 39, 103, 64, 61, 92}},
    {{101, 45, 83, 59, 92, 27}},
}};
const int num_workers = costs.size();
std::vector<int> all_workers(num_workers);
std::iota(all_workers.begin(), all_workers.end(), 0);

const int num_tasks = costs[0].size();
std::vector<int> all_tasks(num_tasks);
std::iota(all_tasks.begin(), all_tasks.end(), 0);

Java

double[][] costs = {
    {90, 76, 75, 70, 50, 74},
    {35, 85, 55, 65, 48, 101},
    {125, 95, 90, 105, 59, 120},
    {45, 110, 95, 115, 104, 83},
    {60, 105, 80, 75, 59, 62},
    {45, 65, 110, 95, 47, 31},
    {38, 51, 107, 41, 69, 99},
    {47, 85, 57, 71, 92, 77},
    {39, 63, 97, 49, 118, 56},
    {47, 101, 71, 60, 88, 109},
    {17, 39, 103, 64, 61, 92},
    {101, 45, 83, 59, 92, 27},
};
int numWorkers = costs.length;
int numTasks = costs[0].length;

final int[] allWorkers = IntStream.range(0, numWorkers).toArray();
final int[] allTasks = IntStream.range(0, numTasks).toArray();

C#

int[,] costs = {
    { 90, 76, 75, 70, 50, 74 },    { 35, 85, 55, 65, 48, 101 }, { 125, 95, 90, 105, 59, 120 },
    { 45, 110, 95, 115, 104, 83 }, { 60, 105, 80, 75, 59, 62 }, { 45, 65, 110, 95, 47, 31 },
    { 38, 51, 107, 41, 69, 99 },   { 47, 85, 57, 71, 92, 77 },  { 39, 63, 97, 49, 118, 56 },
    { 47, 101, 71, 60, 88, 109 },  { 17, 39, 103, 64, 61, 92 }, { 101, 45, 83, 59, 92, 27 },
};
int numWorkers = costs.GetLength(0);
int numTasks = costs.GetLength(1);

int[] allWorkers = Enumerable.Range(0, numWorkers).ToArray();
int[] allTasks = Enumerable.Range(0, numTasks).ToArray();

Tạo các nhóm được phép

Mã sau đây tạo các nhóm được phép bằng cách lặp qua 3 nhóm nhóm con được hiển thị ở trên.

Python

group1 = [  # Subgroups of workers 0 - 3
    [2, 3],
    [1, 3],
    [1, 2],
    [0, 1],
    [0, 2],
]

group2 = [  # Subgroups of workers 4 - 7
    [6, 7],
    [5, 7],
    [5, 6],
    [4, 5],
    [4, 7],
]

group3 = [  # Subgroups of workers 8 - 11
    [10, 11],
    [9, 11],
    [9, 10],
    [8, 10],
    [8, 11],
]

C++

using WorkerIndex = int;
using Binome = std::pair<WorkerIndex, WorkerIndex>;
using AllowedBinomes = std::vector<Binome>;
const AllowedBinomes group1 = {{
    // group of worker 0-3
    {2, 3},
    {1, 3},
    {1, 2},
    {0, 1},
    {0, 2},
}};

const AllowedBinomes group2 = {{
    // group of worker 4-7
    {6, 7},
    {5, 7},
    {5, 6},
    {4, 5},
    {4, 7},
}};

const AllowedBinomes group3 = {{
    // group of worker 8-11
    {10, 11},
    {9, 11},
    {9, 10},
    {8, 10},
    {8, 11},
}};

Java

int[][] group1 = {
    // group of worker 0-3
    {2, 3},
    {1, 3},
    {1, 2},
    {0, 1},
    {0, 2},
};

int[][] group2 = {
    // group of worker 4-7
    {6, 7},
    {5, 7},
    {5, 6},
    {4, 5},
    {4, 7},
};

int[][] group3 = {
    // group of worker 8-11
    {10, 11},
    {9, 11},
    {9, 10},
    {8, 10},
    {8, 11},
};

C#

int[,] group1 = {
    // group of worker 0-3
    { 2, 3 }, { 1, 3 }, { 1, 2 }, { 0, 1 }, { 0, 2 },
};

int[,] group2 = {
    // group of worker 4-7
    { 6, 7 }, { 5, 7 }, { 5, 6 }, { 4, 5 }, { 4, 7 },
};

int[,] group3 = {
    // group of worker 8-11
    { 10, 11 }, { 9, 11 }, { 9, 10 }, { 8, 10 }, { 8, 11 },
};

Khai báo trình giải

Mã sau đây sẽ tạo trình giải toán.

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 biến

Mã sau đây sẽ tạo một mảng các biến cho bài toán này.

Python

# x[worker, task] is an array of 0-1 variables, which will be 1
# if the worker is assigned to the task.
x = {}
for worker in range(num_workers):
    for task in range(num_tasks):
        x[worker, task] = solver.BoolVar(f"x[{worker},{task}]")

C++

// x[i][j] is an array of 0-1 variables, which will be 1
// if worker i is assigned to task j.
std::vector<std::vector<const MPVariable*>> x(
    num_workers, std::vector<const MPVariable*>(num_tasks));
for (int worker : all_workers) {
  for (int task : all_tasks) {
    x[worker][task] =
        solver->MakeBoolVar(absl::StrFormat("x[%d,%d]", worker, task));
  }
}

Java

// x[i][j] is an array of 0-1 variables, which will be 1
// if worker i is assigned to task j.
MPVariable[][] x = new MPVariable[numWorkers][numTasks];
for (int worker : allWorkers) {
  for (int task : allTasks) {
    x[worker][task] = solver.makeBoolVar("x[" + worker + "," + task + "]");
  }
}

C#

// x[i, j] is an array of 0-1 variables, which will be 1
// if worker i is assigned to task j.
Variable[,] x = new Variable[numWorkers, numTasks];
foreach (int worker in allWorkers)
{
    foreach (int task in allTasks)
    {
        x[worker, task] = solver.MakeBoolVar($"x[{worker},{task}]");
    }
}

Thêm các điều kiện ràng buộc

Mã sau đây tạo các quy tắc ràng buộc cho chương trình.

Python

# The total size of the tasks each worker takes on is at most total_size_max.
for worker in range(num_workers):
    solver.Add(solver.Sum([x[worker, task] for task in range(num_tasks)]) <= 1)

# Each task is assigned to exactly one worker.
for task in range(num_tasks):
    solver.Add(solver.Sum([x[worker, task] for worker in range(num_workers)]) == 1)

C++

// Each worker is assigned to at most one task.
for (int worker : all_workers) {
  LinearExpr worker_sum;
  for (int task : all_tasks) {
    worker_sum += x[worker][task];
  }
  solver->MakeRowConstraint(worker_sum <= 1.0);
}
// Each task is assigned to exactly one worker.
for (int task : all_tasks) {
  LinearExpr task_sum;
  for (int worker : all_workers) {
    task_sum += x[worker][task];
  }
  solver->MakeRowConstraint(task_sum == 1.0);
}

Java

// Each worker is assigned to at most one task.
for (int worker : allWorkers) {
  MPConstraint constraint = solver.makeConstraint(0, 1, "");
  for (int task : allTasks) {
    constraint.setCoefficient(x[worker][task], 1);
  }
}
// Each task is assigned to exactly one worker.
for (int task : allTasks) {
  MPConstraint constraint = solver.makeConstraint(1, 1, "");
  for (int worker : allWorkers) {
    constraint.setCoefficient(x[worker][task], 1);
  }
}

C#

// Each worker is assigned to at most one task.
foreach (int worker in allWorkers)
{
    Constraint constraint = solver.MakeConstraint(0, 1, "");
    foreach (int task in allTasks)
    {
        constraint.SetCoefficient(x[worker, task], 1);
    }
}
// Each task is assigned to exactly one worker.
foreach (int task in allTasks)
{
    Constraint constraint = solver.MakeConstraint(1, 1, "");
    foreach (int worker in allWorkers)
    {
        constraint.SetCoefficient(x[worker, task], 1);
    }
}

Tạo mục tiêu

Mã sau đây sẽ 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 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 thị 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.")

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.");
}

Dưới đây là kết quả của chương trình:

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

Toàn bộ chương trình

Sau đây là toàn bộ chương trình.

Python

"""Solve assignment problem for given group of workers."""
from ortools.linear_solver import pywraplp


def main():
    # Data
    costs = [
        [90, 76, 75, 70, 50, 74],
        [35, 85, 55, 65, 48, 101],
        [125, 95, 90, 105, 59, 120],
        [45, 110, 95, 115, 104, 83],
        [60, 105, 80, 75, 59, 62],
        [45, 65, 110, 95, 47, 31],
        [38, 51, 107, 41, 69, 99],
        [47, 85, 57, 71, 92, 77],
        [39, 63, 97, 49, 118, 56],
        [47, 101, 71, 60, 88, 109],
        [17, 39, 103, 64, 61, 92],
        [101, 45, 83, 59, 92, 27],
    ]
    num_workers = len(costs)
    num_tasks = len(costs[0])

    # Allowed groups of workers:
    group1 = [  # Subgroups of workers 0 - 3
        [2, 3],
        [1, 3],
        [1, 2],
        [0, 1],
        [0, 2],
    ]

    group2 = [  # Subgroups of workers 4 - 7
        [6, 7],
        [5, 7],
        [5, 6],
        [4, 5],
        [4, 7],
    ]

    group3 = [  # Subgroups of workers 8 - 11
        [10, 11],
        [9, 11],
        [9, 10],
        [8, 10],
        [8, 11],
    ]

    # Solver.
    # Create the mip solver with the SCIP backend.
    solver = pywraplp.Solver.CreateSolver("SCIP")
    if not solver:
        return

    # Variables
    # x[worker, task] is an array of 0-1 variables, which will be 1
    # if the worker is assigned to the task.
    x = {}
    for worker in range(num_workers):
        for task in range(num_tasks):
            x[worker, task] = solver.BoolVar(f"x[{worker},{task}]")

    # Constraints
    # The total size of the tasks each worker takes on is at most total_size_max.
    for worker in range(num_workers):
        solver.Add(solver.Sum([x[worker, task] for task in range(num_tasks)]) <= 1)

    # Each task is assigned to exactly one worker.
    for task in range(num_tasks):
        solver.Add(solver.Sum([x[worker, task] for worker in range(num_workers)]) == 1)

    # Create variables for each worker, indicating whether they work on some task.
    work = {}
    for worker in range(num_workers):
        work[worker] = solver.BoolVar(f"work[{worker}]")

    for worker in range(num_workers):
        solver.Add(
            work[worker] == solver.Sum([x[worker, task] for task in range(num_tasks)])
        )

    # Group1
    constraint_g1 = solver.Constraint(1, 1)
    for index, _ in enumerate(group1):
        # a*b can be transformed into 0 <= a + b - 2*p <= 1 with p in [0,1]
        # p is True if a AND b, False otherwise
        constraint = solver.Constraint(0, 1)
        constraint.SetCoefficient(work[group1[index][0]], 1)
        constraint.SetCoefficient(work[group1[index][1]], 1)
        p = solver.BoolVar(f"g1_p{index}")
        constraint.SetCoefficient(p, -2)

        constraint_g1.SetCoefficient(p, 1)

    # Group2
    constraint_g2 = solver.Constraint(1, 1)
    for index, _ in enumerate(group2):
        # a*b can be transformed into 0 <= a + b - 2*p <= 1 with p in [0,1]
        # p is True if a AND b, False otherwise
        constraint = solver.Constraint(0, 1)
        constraint.SetCoefficient(work[group2[index][0]], 1)
        constraint.SetCoefficient(work[group2[index][1]], 1)
        p = solver.BoolVar(f"g2_p{index}")
        constraint.SetCoefficient(p, -2)

        constraint_g2.SetCoefficient(p, 1)

    # Group3
    constraint_g3 = solver.Constraint(1, 1)
    for index, _ in enumerate(group3):
        # a*b can be transformed into 0 <= a + b - 2*p <= 1 with p in [0,1]
        # p is True if a AND b, False otherwise
        constraint = solver.Constraint(0, 1)
        constraint.SetCoefficient(work[group3[index][0]], 1)
        constraint.SetCoefficient(work[group3[index][1]], 1)
        p = solver.BoolVar(f"g3_p{index}")
        constraint.SetCoefficient(p, -2)

        constraint_g3.SetCoefficient(p, 1)

    # Objective
    objective_terms = []
    for worker in range(num_workers):
        for task in range(num_tasks):
            objective_terms.append(costs[worker][task] * x[worker, task])
    solver.Minimize(solver.Sum(objective_terms))

    # Solve
    print(f"Solving with {solver.SolverVersion()}")
    status = solver.Solve()

    # Print solution.
    if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE:
        print(f"Total cost = {solver.Objective().Value()}\n")
        for worker in range(num_workers):
            for task in range(num_tasks):
                if x[worker, task].solution_value() > 0.5:
                    print(
                        f"Worker {worker} assigned to task {task}."
                        + f" Cost: {costs[worker][task]}"
                    )
    else:
        print("No solution found.")


if __name__ == "__main__":
    main()

C++

// Solve a simple assignment problem.
#include <cstdint>
#include <memory>
#include <numeric>
#include <utility>
#include <vector>

#include "absl/strings/str_format.h"
#include "ortools/base/logging.h"
#include "ortools/linear_solver/linear_solver.h"

namespace operations_research {
void AssignmentTeamsMip() {
  // Data
  const std::vector<std::vector<int64_t>> costs = {{
      {{90, 76, 75, 70, 50, 74}},
      {{35, 85, 55, 65, 48, 101}},
      {{125, 95, 90, 105, 59, 120}},
      {{45, 110, 95, 115, 104, 83}},
      {{60, 105, 80, 75, 59, 62}},
      {{45, 65, 110, 95, 47, 31}},
      {{38, 51, 107, 41, 69, 99}},
      {{47, 85, 57, 71, 92, 77}},
      {{39, 63, 97, 49, 118, 56}},
      {{47, 101, 71, 60, 88, 109}},
      {{17, 39, 103, 64, 61, 92}},
      {{101, 45, 83, 59, 92, 27}},
  }};
  const int num_workers = costs.size();
  std::vector<int> all_workers(num_workers);
  std::iota(all_workers.begin(), all_workers.end(), 0);

  const int num_tasks = costs[0].size();
  std::vector<int> all_tasks(num_tasks);
  std::iota(all_tasks.begin(), all_tasks.end(), 0);

  // Allowed groups of workers:
  using WorkerIndex = int;
  using Binome = std::pair<WorkerIndex, WorkerIndex>;
  using AllowedBinomes = std::vector<Binome>;
  const AllowedBinomes group1 = {{
      // group of worker 0-3
      {2, 3},
      {1, 3},
      {1, 2},
      {0, 1},
      {0, 2},
  }};

  const AllowedBinomes group2 = {{
      // group of worker 4-7
      {6, 7},
      {5, 7},
      {5, 6},
      {4, 5},
      {4, 7},
  }};

  const AllowedBinomes group3 = {{
      // group of worker 8-11
      {10, 11},
      {9, 11},
      {9, 10},
      {8, 10},
      {8, 11},
  }};

  // Solver
  // Create the mip solver with the SCIP backend.
  std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("SCIP"));
  if (!solver) {
    LOG(WARNING) << "SCIP solver unavailable.";
    return;
  }

  // Variables
  // x[i][j] is an array of 0-1 variables, which will be 1
  // if worker i is assigned to task j.
  std::vector<std::vector<const MPVariable*>> x(
      num_workers, std::vector<const MPVariable*>(num_tasks));
  for (int worker : all_workers) {
    for (int task : all_tasks) {
      x[worker][task] =
          solver->MakeBoolVar(absl::StrFormat("x[%d,%d]", worker, task));
    }
  }

  // Constraints
  // Each worker is assigned to at most one task.
  for (int worker : all_workers) {
    LinearExpr worker_sum;
    for (int task : all_tasks) {
      worker_sum += x[worker][task];
    }
    solver->MakeRowConstraint(worker_sum <= 1.0);
  }
  // Each task is assigned to exactly one worker.
  for (int task : all_tasks) {
    LinearExpr task_sum;
    for (int worker : all_workers) {
      task_sum += x[worker][task];
    }
    solver->MakeRowConstraint(task_sum == 1.0);
  }

  // Create variables for each worker, indicating whether they work on some
  // task.
  std::vector<const MPVariable*> work(num_workers);
  for (int worker : all_workers) {
    work[worker] = solver->MakeBoolVar(absl::StrFormat("work[%d]", worker));
  }

  for (int worker : all_workers) {
    LinearExpr task_sum;
    for (int task : all_tasks) {
      task_sum += x[worker][task];
    }
    solver->MakeRowConstraint(work[worker] == task_sum);
  }

  // Group1
  {
    MPConstraint* g1 = solver->MakeRowConstraint(1, 1);
    for (int i = 0; i < group1.size(); ++i) {
      // a*b can be transformed into 0 <= a + b - 2*p <= 1 with p in [0,1]
      // p is true if a AND b, false otherwise
      MPConstraint* tmp = solver->MakeRowConstraint(0, 1);
      tmp->SetCoefficient(work[group1[i].first], 1);
      tmp->SetCoefficient(work[group1[i].second], 1);
      MPVariable* p = solver->MakeBoolVar(absl::StrFormat("g1_p%d", i));
      tmp->SetCoefficient(p, -2);

      g1->SetCoefficient(p, 1);
    }
  }
  // Group2
  {
    MPConstraint* g2 = solver->MakeRowConstraint(1, 1);
    for (int i = 0; i < group2.size(); ++i) {
      // a*b can be transformed into 0 <= a + b - 2*p <= 1 with p in [0,1]
      // p is true if a AND b, false otherwise
      MPConstraint* tmp = solver->MakeRowConstraint(0, 1);
      tmp->SetCoefficient(work[group2[i].first], 1);
      tmp->SetCoefficient(work[group2[i].second], 1);
      MPVariable* p = solver->MakeBoolVar(absl::StrFormat("g2_p%d", i));
      tmp->SetCoefficient(p, -2);

      g2->SetCoefficient(p, 1);
    }
  }
  // Group3
  {
    MPConstraint* g3 = solver->MakeRowConstraint(1, 1);
    for (int i = 0; i < group3.size(); ++i) {
      // a*b can be transformed into 0 <= a + b - 2*p <= 1 with p in [0,1]
      // p is true if a AND b, false otherwise
      MPConstraint* tmp = solver->MakeRowConstraint(0, 1);
      tmp->SetCoefficient(work[group3[i].first], 1);
      tmp->SetCoefficient(work[group3[i].second], 1);
      MPVariable* p = solver->MakeBoolVar(absl::StrFormat("g3_p%d", i));
      tmp->SetCoefficient(p, -2);

      g3->SetCoefficient(p, 1);
    }
  }

  // Objective.
  MPObjective* const objective = solver->MutableObjective();
  for (int worker : all_workers) {
    for (int task : all_tasks) {
      objective->SetCoefficient(x[worker][task], costs[worker][task]);
    }
  }
  objective->SetMinimization();

  // Solve
  const MPSolver::ResultStatus result_status = solver->Solve();

  // Print solution.
  // Check that the problem has a feasible solution.
  if (result_status != MPSolver::OPTIMAL &&
      result_status != MPSolver::FEASIBLE) {
    LOG(FATAL) << "No solution found.";
  }
  LOG(INFO) << "Total cost = " << objective->Value() << "\n\n";
  for (int worker : all_workers) {
    for (int task : all_tasks) {
      // Test if x[i][j] is 0 or 1 (with tolerance for floating point
      // arithmetic).
      if (x[worker][task]->solution_value() > 0.5) {
        LOG(INFO) << "Worker " << worker << " assigned to task " << task
                  << ".  Cost: " << costs[worker][task];
      }
    }
  }
}
}  // namespace operations_research

int main(int argc, char** argv) {
  operations_research::AssignmentTeamsMip();
  return EXIT_SUCCESS;
}

Java

package com.google.ortools.linearsolver.samples;
import com.google.ortools.Loader;
import com.google.ortools.linearsolver.MPConstraint;
import com.google.ortools.linearsolver.MPObjective;
import com.google.ortools.linearsolver.MPSolver;
import com.google.ortools.linearsolver.MPVariable;
import java.util.stream.IntStream;

/** MIP example that solves an assignment problem. */
public class AssignmentGroupsMip {
  public static void main(String[] args) {
    Loader.loadNativeLibraries();
    // Data
    double[][] costs = {
        {90, 76, 75, 70, 50, 74},
        {35, 85, 55, 65, 48, 101},
        {125, 95, 90, 105, 59, 120},
        {45, 110, 95, 115, 104, 83},
        {60, 105, 80, 75, 59, 62},
        {45, 65, 110, 95, 47, 31},
        {38, 51, 107, 41, 69, 99},
        {47, 85, 57, 71, 92, 77},
        {39, 63, 97, 49, 118, 56},
        {47, 101, 71, 60, 88, 109},
        {17, 39, 103, 64, 61, 92},
        {101, 45, 83, 59, 92, 27},
    };
    int numWorkers = costs.length;
    int numTasks = costs[0].length;

    final int[] allWorkers = IntStream.range(0, numWorkers).toArray();
    final int[] allTasks = IntStream.range(0, numTasks).toArray();

    // Allowed groups of workers:
    int[][] group1 = {
        // group of worker 0-3
        {2, 3},
        {1, 3},
        {1, 2},
        {0, 1},
        {0, 2},
    };

    int[][] group2 = {
        // group of worker 4-7
        {6, 7},
        {5, 7},
        {5, 6},
        {4, 5},
        {4, 7},
    };

    int[][] group3 = {
        // group of worker 8-11
        {10, 11},
        {9, 11},
        {9, 10},
        {8, 10},
        {8, 11},
    };

    // Solver
    // Create the linear solver with the SCIP backend.
    MPSolver solver = MPSolver.createSolver("SCIP");
    if (solver == null) {
      System.out.println("Could not create solver SCIP");
      return;
    }

    // Variables
    // x[i][j] is an array of 0-1 variables, which will be 1
    // if worker i is assigned to task j.
    MPVariable[][] x = new MPVariable[numWorkers][numTasks];
    for (int worker : allWorkers) {
      for (int task : allTasks) {
        x[worker][task] = solver.makeBoolVar("x[" + worker + "," + task + "]");
      }
    }

    // Constraints
    // Each worker is assigned to at most one task.
    for (int worker : allWorkers) {
      MPConstraint constraint = solver.makeConstraint(0, 1, "");
      for (int task : allTasks) {
        constraint.setCoefficient(x[worker][task], 1);
      }
    }
    // Each task is assigned to exactly one worker.
    for (int task : allTasks) {
      MPConstraint constraint = solver.makeConstraint(1, 1, "");
      for (int worker : allWorkers) {
        constraint.setCoefficient(x[worker][task], 1);
      }
    }

    // Create variables for each worker, indicating whether they work on some task.
    MPVariable[] work = new MPVariable[numWorkers];
    for (int worker : allWorkers) {
      work[worker] = solver.makeBoolVar("work[" + worker + "]");
    }

    for (int worker : allWorkers) {
      // MPVariable[] vars = new MPVariable[numTasks];
      MPConstraint constraint = solver.makeConstraint(0, 0, "");
      for (int task : allTasks) {
        // vars[task] = x[worker][task];
        constraint.setCoefficient(x[worker][task], 1);
      }
      // solver.addEquality(work[worker], LinearExpr.sum(vars));
      constraint.setCoefficient(work[worker], -1);
    }

    // Group1
    MPConstraint constraintG1 = solver.makeConstraint(1, 1, "");
    for (int i = 0; i < group1.length; ++i) {
      // a*b can be transformed into 0 <= a + b - 2*p <= 1 with p in [0,1]
      // p is True if a AND b, False otherwise
      MPConstraint constraint = solver.makeConstraint(0, 1, "");
      constraint.setCoefficient(work[group1[i][0]], 1);
      constraint.setCoefficient(work[group1[i][1]], 1);
      MPVariable p = solver.makeBoolVar("g1_p" + i);
      constraint.setCoefficient(p, -2);

      constraintG1.setCoefficient(p, 1);
    }
    // Group2
    MPConstraint constraintG2 = solver.makeConstraint(1, 1, "");
    for (int i = 0; i < group2.length; ++i) {
      // a*b can be transformed into 0 <= a + b - 2*p <= 1 with p in [0,1]
      // p is True if a AND b, False otherwise
      MPConstraint constraint = solver.makeConstraint(0, 1, "");
      constraint.setCoefficient(work[group2[i][0]], 1);
      constraint.setCoefficient(work[group2[i][1]], 1);
      MPVariable p = solver.makeBoolVar("g2_p" + i);
      constraint.setCoefficient(p, -2);

      constraintG2.setCoefficient(p, 1);
    }
    // Group3
    MPConstraint constraintG3 = solver.makeConstraint(1, 1, "");
    for (int i = 0; i < group3.length; ++i) {
      // a*b can be transformed into 0 <= a + b - 2*p <= 1 with p in [0,1]
      // p is True if a AND b, False otherwise
      MPConstraint constraint = solver.makeConstraint(0, 1, "");
      constraint.setCoefficient(work[group3[i][0]], 1);
      constraint.setCoefficient(work[group3[i][1]], 1);
      MPVariable p = solver.makeBoolVar("g3_p" + i);
      constraint.setCoefficient(p, -2);

      constraintG3.setCoefficient(p, 1);
    }

    // Objective
    MPObjective objective = solver.objective();
    for (int worker : allWorkers) {
      for (int task : allTasks) {
        objective.setCoefficient(x[worker][task], costs[worker][task]);
      }
    }
    objective.setMinimization();

    // Solve
    MPSolver.ResultStatus resultStatus = solver.solve();

    // Print solution.
    // Check that the problem has a feasible solution.
    if (resultStatus == MPSolver.ResultStatus.OPTIMAL
        || resultStatus == MPSolver.ResultStatus.FEASIBLE) {
      System.out.println("Total cost: " + objective.value() + "\n");
      for (int worker : allWorkers) {
        for (int task : allTasks) {
          // Test if x[i][j] is 0 or 1 (with tolerance for floating point
          // arithmetic).
          if (x[worker][task].solutionValue() > 0.5) {
            System.out.println("Worker " + worker + " assigned to task " + task
                + ".  Cost: " + costs[worker][task]);
          }
        }
      }
    } else {
      System.err.println("No solution found.");
    }
  }

  private AssignmentGroupsMip() {}
}

C#

using System;
using System.Collections.Generic;
using System.Linq;
using Google.OrTools.LinearSolver;

public class AssignmentGroupsMip
{
    static void Main()
    {
        // Data.
        int[,] costs = {
            { 90, 76, 75, 70, 50, 74 },    { 35, 85, 55, 65, 48, 101 }, { 125, 95, 90, 105, 59, 120 },
            { 45, 110, 95, 115, 104, 83 }, { 60, 105, 80, 75, 59, 62 }, { 45, 65, 110, 95, 47, 31 },
            { 38, 51, 107, 41, 69, 99 },   { 47, 85, 57, 71, 92, 77 },  { 39, 63, 97, 49, 118, 56 },
            { 47, 101, 71, 60, 88, 109 },  { 17, 39, 103, 64, 61, 92 }, { 101, 45, 83, 59, 92, 27 },
        };
        int numWorkers = costs.GetLength(0);
        int numTasks = costs.GetLength(1);

        int[] allWorkers = Enumerable.Range(0, numWorkers).ToArray();
        int[] allTasks = Enumerable.Range(0, numTasks).ToArray();

        // Allowed groups of workers:
        int[,] group1 = {
            // group of worker 0-3
            { 2, 3 }, { 1, 3 }, { 1, 2 }, { 0, 1 }, { 0, 2 },
        };

        int[,] group2 = {
            // group of worker 4-7
            { 6, 7 }, { 5, 7 }, { 5, 6 }, { 4, 5 }, { 4, 7 },
        };

        int[,] group3 = {
            // group of worker 8-11
            { 10, 11 }, { 9, 11 }, { 9, 10 }, { 8, 10 }, { 8, 11 },
        };

        // Solver.
        Solver solver = Solver.CreateSolver("SCIP");
        if (solver is null)
        {
            return;
        }

        // Variables.
        // x[i, j] is an array of 0-1 variables, which will be 1
        // if worker i is assigned to task j.
        Variable[,] x = new Variable[numWorkers, numTasks];
        foreach (int worker in allWorkers)
        {
            foreach (int task in allTasks)
            {
                x[worker, task] = solver.MakeBoolVar($"x[{worker},{task}]");
            }
        }

        // Constraints
        // Each worker is assigned to at most one task.
        foreach (int worker in allWorkers)
        {
            Constraint constraint = solver.MakeConstraint(0, 1, "");
            foreach (int task in allTasks)
            {
                constraint.SetCoefficient(x[worker, task], 1);
            }
        }
        // Each task is assigned to exactly one worker.
        foreach (int task in allTasks)
        {
            Constraint constraint = solver.MakeConstraint(1, 1, "");
            foreach (int worker in allWorkers)
            {
                constraint.SetCoefficient(x[worker, task], 1);
            }
        }

        // Create variables for each worker, indicating whether they work on some task.
        Variable[] work = new Variable[numWorkers];
        foreach (int worker in allWorkers)
        {
            work[worker] = solver.MakeBoolVar($"work[{worker}]");
        }

        foreach (int worker in allWorkers)
        {
            Variable[] vars = new Variable[numTasks];
            foreach (int task in allTasks)
            {
                vars[task] = x[worker, task];
            }
            solver.Add(work[worker] == LinearExprArrayHelper.Sum(vars));
        }

        // Group1
        Constraint constraint_g1 = solver.MakeConstraint(1, 1, "");
        for (int i = 0; i < group1.GetLength(0); ++i)
        {
            // a*b can be transformed into 0 <= a + b - 2*p <= 1 with p in [0,1]
            // p is True if a AND b, False otherwise
            Constraint constraint = solver.MakeConstraint(0, 1, "");
            constraint.SetCoefficient(work[group1[i, 0]], 1);
            constraint.SetCoefficient(work[group1[i, 1]], 1);
            Variable p = solver.MakeBoolVar($"g1_p{i}");
            constraint.SetCoefficient(p, -2);

            constraint_g1.SetCoefficient(p, 1);
        }
        // Group2
        Constraint constraint_g2 = solver.MakeConstraint(1, 1, "");
        for (int i = 0; i < group2.GetLength(0); ++i)
        {
            // a*b can be transformed into 0 <= a + b - 2*p <= 1 with p in [0,1]
            // p is True if a AND b, False otherwise
            Constraint constraint = solver.MakeConstraint(0, 1, "");
            constraint.SetCoefficient(work[group2[i, 0]], 1);
            constraint.SetCoefficient(work[group2[i, 1]], 1);
            Variable p = solver.MakeBoolVar($"g2_p{i}");
            constraint.SetCoefficient(p, -2);

            constraint_g2.SetCoefficient(p, 1);
        }
        // Group3
        Constraint constraint_g3 = solver.MakeConstraint(1, 1, "");
        for (int i = 0; i < group3.GetLength(0); ++i)
        {
            // a*b can be transformed into 0 <= a + b - 2*p <= 1 with p in [0,1]
            // p is True if a AND b, False otherwise
            Constraint constraint = solver.MakeConstraint(0, 1, "");
            constraint.SetCoefficient(work[group3[i, 0]], 1);
            constraint.SetCoefficient(work[group3[i, 1]], 1);
            Variable p = solver.MakeBoolVar($"g3_p{i}");
            constraint.SetCoefficient(p, -2);

            constraint_g3.SetCoefficient(p, 1);
        }

        // Objective
        Objective objective = solver.Objective();
        foreach (int worker in allWorkers)
        {
            foreach (int task in allTasks)
            {
                objective.SetCoefficient(x[worker, task], costs[worker, task]);
            }
        }
        objective.SetMinimization();

        // Solve
        Solver.ResultStatus resultStatus = solver.Solve();

        // Print solution.
        // Check that the problem has a feasible solution.
        if (resultStatus == Solver.ResultStatus.OPTIMAL || resultStatus == Solver.ResultStatus.FEASIBLE)
        {
            Console.WriteLine($"Total cost: {solver.Objective().Value()}\n");
            foreach (int worker in allWorkers)
            {
                foreach (int task in allTasks)
                {
                    // Test if x[i, j] is 0 or 1 (with tolerance for floating point
                    // arithmetic).
                    if (x[worker, task].SolutionValue() > 0.5)
                    {
                        Console.WriteLine($"Worker {worker} assigned to task {task}. Cost: {costs[worker, task]}");
                    }
                }
            }
        }
        else
        {
            Console.WriteLine("No solution found.");
        }
    }
}

Thời gian giải pháp

Thời gian giải cho hai trình giải như sau:

• CP-SAT: 0,0113 giây
• MIP: 0,3281 giây

Trong vấn đề này, CP-SAT nhanh hơn đáng kể so với MIP.