Chỉ định kích thước tác vụ

Phần này mô tả một bài tập, trong đó mỗi nhiệm vụ sẽ có một kích thước, thể hiện thời gian hoặc công sức mà bài tập đó cần. Tổng kích thước của các tác vụ mà mỗi worker thực hiện có một giới hạn cố định.

Chúng tôi sẽ trình bày các chương trình Python giải quyết vấn đề này thông qua trình giải quyết CP-SAT và trình giải mã MIP của chúng tôi.

Giải pháp CP-SAT

Trước tiên, hãy xem xét giải pháp CP-SAT cho vấn đề.

Nhập thư viện

Mã sau đây nhập thư viện bắt buộc.

Python

from ortools.sat.python import cp_model

C++

#include <stdlib.h>

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

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

Java

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

C#

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

Xác định dữ liệu

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

Python

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

task_sizes = [10, 7, 3, 12, 15, 4, 11, 5]
# Maximum total of task sizes for any worker
total_size_max = 15

C++

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

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

const std::vector<int64_t> task_sizes = {{10, 7, 3, 12, 15, 4, 11, 5}};
// Maximum total of task sizes for any worker
const int total_size_max = 15;

Java

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

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

final int[] taskSizes = {10, 7, 3, 12, 15, 4, 11, 5};
// Maximum total of task sizes for any worker
final int totalSizeMax = 15;

C#

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

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

int[] taskSizes = { 10, 7, 3, 12, 15, 4, 11, 5 };
// Maximum total of task sizes for any worker
int totalSizeMax = 15;

Như trong các ví dụ trước đó, ma trận chi phí cung cấp chi phí cho worker i để thực hiện tác vụ j. Vectơ sizes cho biết kích thước của mỗi tác vụ. total_size_max là giới hạn trên của tổng kích thước của việc cần làm do bất kỳ trình thực thi nào thực hiệ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];
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(
        sum(task_sizes[task] * x[worker, task] for task in range(num_tasks))
        <= total_size_max
    )

# 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) {
  LinearExpr task_sum;
  for (int task : all_tasks) {
    task_sum += x[worker][task] * task_sizes[task];
  }
  cp_model.AddLessOrEqual(task_sum, total_size_max);
}
// 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 has a maximum capacity.
for (int worker : allWorkers) {
  LinearExprBuilder expr = LinearExpr.newBuilder();
  for (int task : allTasks) {
    expr.addTerm(x[worker][task], taskSizes[task]);
  }
  model.addLessOrEqual(expr, totalSizeMax);
}

// 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 max task size.
foreach (int worker in allWorkers)
{
    BoolVar[] vars = new BoolVar[numTasks];
    foreach (int task in allTasks)
    {
        vars[task] = x[worker, task];
    }
    model.Add(LinearExpr.WeightedSum(vars, taskSizes) <= totalSizeMax);
}

// 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.

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: 326
Worker  0  assigned to task  6   Cost =  12
Worker  1  assigned to task  0   Cost =  35
Worker  1  assigned to task  2   Cost =  55
Worker  2  assigned to task  4   Cost =  59
Worker  5  assigned to task  5   Cost =  31
Worker  5  assigned to task  7   Cost =  34
Worker  6  assigned to task  1   Cost =  51
Worker  8  assigned to task  3   Cost =  49

Time =  2.2198 seconds

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

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

Python

"""Solves a simple assignment problem."""
from ortools.sat.python import cp_model


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

    task_sizes = [10, 7, 3, 12, 15, 4, 11, 5]
    # Maximum total of task sizes for any worker
    total_size_max = 15

    # 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(
            sum(task_sizes[task] * x[worker, task] for task in range(num_tasks))
            <= total_size_max
        )

    # 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))

    # 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.
#include <stdlib.h>

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

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

namespace operations_research {
namespace sat {

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

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

  const std::vector<int64_t> task_sizes = {{10, 7, 3, 12, 15, 4, 11, 5}};
  // Maximum total of task sizes for any worker
  const int total_size_max = 15;

  // 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) {
    LinearExpr task_sum;
    for (int task : all_tasks) {
      task_sum += x[worker][task] * task_sizes[task];
    }
    cp_model.AddLessOrEqual(task_sum, total_size_max);
  }
  // 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);
  }

  // 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::AssignmentTaskSizes();
  return EXIT_SUCCESS;
}

Java

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

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

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

    final int[] taskSizes = {10, 7, 3, 12, 15, 4, 11, 5};
    // Maximum total of task sizes for any worker
    final int totalSizeMax = 15;

    // 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 has a maximum capacity.
    for (int worker : allWorkers) {
      LinearExprBuilder expr = LinearExpr.newBuilder();
      for (int task : allTasks) {
        expr.addTerm(x[worker][task], taskSizes[task]);
      }
      model.addLessOrEqual(expr, totalSizeMax);
    }

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

    // 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 AssignmentTaskSizesSat() {}
}

C#

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

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

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

        int[] taskSizes = { 10, 7, 3, 12, 15, 4, 11, 5 };
        // Maximum total of task sizes for any worker
        int totalSizeMax = 15;

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

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

        // Constraints
        // Each worker is assigned to at most max task size.
        foreach (int worker in allWorkers)
        {
            BoolVar[] vars = new BoolVar[numTasks];
            foreach (int task in allTasks)
            {
                vars[task] = x[worker, task];
            }
            model.Add(LinearExpr.WeightedSum(vars, taskSizes) <= totalSizeMax);
        }

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

        // Objective
        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ả cách giải cho bài tập bằng trình giải MIP.

Nhập thư viện

Mã sau đây nhập thư viện bắt buộc.

Python

from ortools.linear_solver import pywraplp

C++

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

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

Java

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

C#

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

Xác định dữ liệu

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

Python

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

task_sizes = [10, 7, 3, 12, 15, 4, 11, 5]
# Maximum total of task sizes for any worker
total_size_max = 15

C++

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

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

const std::vector<int64_t> task_sizes = {{10, 7, 3, 12, 15, 4, 11, 5}};
// Maximum total of task sizes for any worker
const int total_size_max = 15;

Java

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

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

final int[] taskSizes = {10, 7, 3, 12, 15, 4, 11, 5};
// Maximum total of task sizes for any worker
final int totalSizeMax = 15;

C#

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

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

int[] taskSizes = { 10, 7, 3, 12, 15, 4, 11, 5 };
// Maximum total of task sizes for any worker
int totalSizeMax = 15;

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[i, j] is an array of 0-1 variables, which will be 1
# if worker i is assigned to task j.
x = {}
for worker in range(num_workers):
    for task in range(num_tasks):
        x[worker, task] = solver.BoolVar(f"x[{worker},{task}]")

C++

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

Java

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

C#

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

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

Mã sau đây tạo các 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(
            [task_sizes[task] * x[worker, task] for task in range(num_tasks)]
        )
        <= total_size_max
    )

# 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 += LinearExpr(x[worker][task]) * task_sizes[task];
  }
  solver->MakeRowConstraint(worker_sum <= total_size_max);
}
// 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 max task size.
for (int worker : allWorkers) {
  MPConstraint constraint = solver.makeConstraint(0, totalSizeMax, "");
  for (int task : allTasks) {
    constraint.setCoefficient(x[worker][task], taskSizes[task]);
  }
}
// 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 max task size.
foreach (int worker in allWorkers)
{
    Constraint constraint = solver.MakeConstraint(0, totalSizeMax, "");
    foreach (int task in allTasks)
    {
        constraint.SetCoefficient(x[worker, task], taskSizes[task]);
    }
}
// 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.");
}

Đây là kết quả của chương trình.

Minimum cost =  326.0

Worker 0  assigned to task 6   Cost =  12
Worker 1  assigned to task 0   Cost =  35
Worker 1  assigned to task 2   Cost =  55
Worker 4  assigned to task 4   Cost =  59
Worker 5  assigned to task 5   Cost =  31
Worker 5  assigned to task 7   Cost =  34
Worker 6  assigned to task 1   Cost =  51
Worker 8  assigned to task 3   Cost =  49

Time =  0.0167 seconds

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

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

Python

"""MIP example that solves an assignment problem."""
from ortools.linear_solver import pywraplp


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

    task_sizes = [10, 7, 3, 12, 15, 4, 11, 5]
    # Maximum total of task sizes for any worker
    total_size_max = 15

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

    if not solver:
        return

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

    # Constraints
    # 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(
                [task_sizes[task] * x[worker, task] for task in range(num_tasks)]
            )
            <= total_size_max
        )

    # 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)

    # 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 <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, 12, 68}},
      {{35, 85, 55, 65, 48, 101, 70, 83}},
      {{125, 95, 90, 105, 59, 120, 36, 73}},
      {{45, 110, 95, 115, 104, 83, 37, 71}},
      {{60, 105, 80, 75, 59, 62, 93, 88}},
      {{45, 65, 110, 95, 47, 31, 81, 34}},
      {{38, 51, 107, 41, 69, 99, 115, 48}},
      {{47, 85, 57, 71, 92, 77, 109, 36}},
      {{39, 63, 97, 49, 118, 56, 92, 61}},
      {{47, 101, 71, 60, 88, 109, 52, 90}},
  }};
  const int num_workers = costs.size();
  std::vector<int> all_workers(num_workers);
  std::iota(all_workers.begin(), all_workers.end(), 0);

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

  const std::vector<int64_t> task_sizes = {{10, 7, 3, 12, 15, 4, 11, 5}};
  // Maximum total of task sizes for any worker
  const int total_size_max = 15;

  // 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 += LinearExpr(x[worker][task]) * task_sizes[task];
    }
    solver->MakeRowConstraint(worker_sum <= total_size_max);
  }
  // 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);
  }

  // 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 AssignmentTaskSizesMip {
  public static void main(String[] args) {
    Loader.loadNativeLibraries();
    // Data
    double[][] costs = {
        {90, 76, 75, 70, 50, 74, 12, 68},
        {35, 85, 55, 65, 48, 101, 70, 83},
        {125, 95, 90, 105, 59, 120, 36, 73},
        {45, 110, 95, 115, 104, 83, 37, 71},
        {60, 105, 80, 75, 59, 62, 93, 88},
        {45, 65, 110, 95, 47, 31, 81, 34},
        {38, 51, 107, 41, 69, 99, 115, 48},
        {47, 85, 57, 71, 92, 77, 109, 36},
        {39, 63, 97, 49, 118, 56, 92, 61},
        {47, 101, 71, 60, 88, 109, 52, 90},
    };
    int numWorkers = costs.length;
    int numTasks = costs[0].length;

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

    final int[] taskSizes = {10, 7, 3, 12, 15, 4, 11, 5};
    // Maximum total of task sizes for any worker
    final int totalSizeMax = 15;

    // 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 max task size.
    for (int worker : allWorkers) {
      MPConstraint constraint = solver.makeConstraint(0, totalSizeMax, "");
      for (int task : allTasks) {
        constraint.setCoefficient(x[worker][task], taskSizes[task]);
      }
    }
    // 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);
      }
    }

    // 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 AssignmentTaskSizesMip() {}
}

C#

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

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

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

        int[] taskSizes = { 10, 7, 3, 12, 15, 4, 11, 5 };
        // Maximum total of task sizes for any worker
        int totalSizeMax = 15;

        // 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 max task size.
        foreach (int worker in allWorkers)
        {
            Constraint constraint = solver.MakeConstraint(0, totalSizeMax, "");
            foreach (int task in allTasks)
            {
                constraint.SetCoefficient(x[worker, task], taskSizes[task]);
            }
        }
        // Each task is assigned to exactly one worker.
        foreach (int task in allTasks)
        {
            Constraint constraint = solver.MakeConstraint(1, 1, "");
            foreach (int worker in allWorkers)
            {
                constraint.SetCoefficient(x[worker, task], 1);
            }
        }

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