허용된 그룹이 있는 할당

이 섹션에서는 특정 텍스트만 허용되는 할당 문제를 설명합니다. 작업자 그룹을 태스크에 할당할 수 있습니다. 이 예에서는 0 - 11의 번호를 지정합니다. 허용되는 그룹은 다음 작업자 쌍의 조합입니다.

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


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

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

허용되는 그룹은 작업자 쌍 세 개, 즉 한 쌍의 작업자 조합일 수 있습니다. 각각 group1, group2, group3의 역할을 합니다. 예를 들어 [2, 3], [6, 7], [10, 11]를 결합하면 다음과 같은 결과가 허용됩니다. 그룹 [2, 3, 6, 7, 10, 11] 세 세트 각각에는 다섯 개의 요소가 포함되어 있으므로 허용된 그룹은 5 * 5 * 5 = 125입니다.

작업자 그룹이 조직 외부의 작업자 그룹에 속한 경우 허용된 그룹 중 하나여야 합니다. 즉, 가능한 집합은 제약 조건 중 하나라도 충족되는 지점을 나타냅니다. 이 문제는 볼록하지 않은 문제의 예입니다. 이에 반해, MIP 예시는 는 볼록 문제입니다. 점을 사용하려면 모든 제약 조건이 충족해야 합니다.

이와 같이 볼록하지 않은 문제의 경우 CP-SAT 솔버는 일반적으로 MIP 솔버를 사용합니다 다음 섹션에서는 CP-SAT 솔버를 사용한 문제 해결 방법을 보여줍니다. 두 솔버의 해답 시간을 비교합니다.

CP-SAT 솔루션

먼저 CP-SAT 솔버를 사용하여 문제 해결 방법을 설명하겠습니다.

라이브러리 가져오기

다음 코드는 필요한 라이브러리를 가져옵니다.

Python

from ortools.sat.python import cp_model

C++

#include <stdlib.h>

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

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

자바

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

C#

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

데이터 정의

다음 코드는 프로그램의 데이터를 생성합니다.

Python

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

C++

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

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

자바

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

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

C#

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

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

허용된 그룹 만들기

CP-SAT 솔버에 허용되는 작업자 그룹을 정의하려면 바이너리를 만듭니다. 그룹에 속하는 작업자를 나타내는 배열입니다. 예를 들어 group1의 경우 (작업자 0~3)에서 바이너리 벡터 [0, 0, 1, 1]은 작업자 2와 3.

참고: 이렇게 하면 그룹을 지정하는 것과 는 MIP 솔루션에 명시되어 있지만 동일한 것과 같습니다.

다음 배열은 허용되는 작업자 그룹을 정의합니다.

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
}};

자바

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

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

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

C#

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

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

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

CP-SAT의 경우 이러한 벡터의 125개 조합을 모두 만들 필요는 없습니다. 반복됩니다. CP-SAT 솔버는 AllowedAssignments 메서드를 제공합니다. 이렇게 하면 허용되는 그룹에 대한 제약조건을 별도로 지정할 수 있습니다. 각각 3개의 작업자 집합 (0~3, 4~7, 8~11)을 실행합니다. 방법은 다음과 같습니다.

Python

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

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

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

C++

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

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

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

자바

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

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

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

C#

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

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

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

변수 work[i]는 작업 상태를 나타내는 0~1 변수입니다. 자동화합니다 즉, 작업자 i가 작업에 할당되면 work[i]은 1입니다. 그 이외의 경우에는 0입니다. 라인 solver.Add(solver.AllowedAssignments([work[0], work[1], work[2], work[3]], group1)) 는 작업자 0 - 3의 작업 상태가 다음 중 하나와 일치해야 한다는 제약 조건을 정의합니다. group1의 패턴을 알아냅니다. 코드의 전체 세부정보는 섹션으로 이동합니다.

모델 만들기

다음 코드는 모델을 만듭니다.

Python

model = cp_model.CpModel()

C++

CpModelBuilder cp_model;

자바

CpModel model = new CpModel();

C#

CpModel model = new CpModel();

변수 만들기

다음 코드는 문제에 대한 변수 배열을 생성합니다.

Python

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

C++

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

자바

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

C#

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

제약 조건 추가

다음 코드는 프로그램의 제약 조건을 생성합니다.

Python

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

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

C++

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

자바

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

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

C#

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

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

목표 만들기

다음 코드는 목적 함수를 생성합니다.

Python

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

C++

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

자바

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

C#

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

솔버 호출

다음 코드는 솔버를 호출하고 결과를 표시합니다.

Python

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

C++

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

자바

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

C#

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

결과 표시

이제 솔루션을 출력할 수 있습니다.

Python

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

C++

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

자바

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

C#

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

프로그램의 출력은 다음과 같습니다.

Minimum cost = 239

Worker  0  assigned to task  4   Cost =  50
Worker  1  assigned to task  2   Cost =  55
Worker  5  assigned to task  5   Cost =  31
Worker  6  assigned to task  3   Cost =  41
Worker  10  assigned to task  0   Cost =  17
Worker  11  assigned to task  1   Cost =  45

Time =  0.0113 seconds

전체 프로그램

전체 프로그램은 다음과 같습니다.

Python

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


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

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

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

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

    # Model
    model = cp_model.CpModel()

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

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

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

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

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

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

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

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

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


if __name__ == "__main__":
    main()

C++

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

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

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

namespace operations_research {
namespace sat {

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

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

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

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

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

  // Model
  CpModelBuilder cp_model;

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

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

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

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

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

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

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

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

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

자바

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

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

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

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

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

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

    // Model
    CpModel model = new CpModel();

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

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

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

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

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

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

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

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

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

  private AssignmentGroupsSat() {}
}

C#

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

MIP 솔루션

다음으로 MIP 솔버를 사용하여 문제 해결 방법을 설명합니다.

라이브러리 가져오기

다음 코드는 필요한 라이브러리를 가져옵니다.

Python

from ortools.linear_solver import pywraplp

C++

#include <cstdint>
#include <memory>
#include <numeric>
#include <utility>
#include <vector>

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

자바

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

C#

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

데이터 정의

다음 코드는 프로그램의 데이터를 생성합니다.

Python

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

C++

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

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

자바

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

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

C#

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

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

허용된 그룹 만들기

다음 코드는 세 세트를 반복하면서 허용된 그룹을 만듭니다. 개의 하위 그룹이 있습니다.

Python

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

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

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

C++

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

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

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

자바

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

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

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

C#

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

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

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

문제 해결사 선언

다음 코드는 솔버를 만듭니다.

Python

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

C++

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

자바

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

C#

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

변수 만들기

다음 코드는 문제에 대한 변수 배열을 생성합니다.

Python

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

C++

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

자바

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

C#

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

제약 조건 추가

다음 코드는 프로그램의 제약 조건을 생성합니다.

Python

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

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

C++

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

자바

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

C#

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

목표 만들기

다음 코드는 목적 함수를 생성합니다.

Python

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

C++

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

자바

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

C#

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

솔버 호출

다음 코드는 솔버를 호출하고 결과를 표시합니다.

Python

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

C++

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

자바

MPSolver.ResultStatus resultStatus = solver.solve();

C#

Solver.ResultStatus resultStatus = solver.Solve();

결과 표시

이제 솔루션을 출력할 수 있습니다.

Python

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

C++

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

자바

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

C#

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

프로그램의 출력은 다음과 같습니다.

Minimum cost =  239.0

Worker 0  assigned to task 4   Cost =  50
Worker 1  assigned to task 2   Cost =  55
Worker 5  assigned to task 5   Cost =  31
Worker 6  assigned to task 3   Cost =  41
Worker 10  assigned to task 0   Cost =  17
Worker 11  assigned to task 1   Cost =  45

Time =  0.3281 seconds

전체 프로그램

전체 프로그램은 다음과 같습니다.

Python

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


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

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

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

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

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

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

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

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

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

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

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

        constraint_g1.SetCoefficient(p, 1)

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

        constraint_g2.SetCoefficient(p, 1)

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

        constraint_g3.SetCoefficient(p, 1)

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

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

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


if __name__ == "__main__":
    main()

C++

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

자바

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

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

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

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

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

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

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

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

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

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

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

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

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

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

      constraintG3.setCoefficient(p, 1);
    }

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

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

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

  private AssignmentGroupsMip() {}
}

C#

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

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

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

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

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

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

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

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

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

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

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

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

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

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

            constraint_g3.SetCoefficient(p, 1);
        }

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

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

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

솔루션 시간

두 솔버의 해답 시간은 다음과 같습니다.

• CP-SAT: 0.0113초
• MIP: 0.3281초

이 문제에서는 CP-SAT가 MIP보다 훨씬 빠릅니다.