Bu bölümde, her görevin ne kadar zaman veya çaba gerektirdiğini gösteren bir boyuta sahip olduğu bir ödev sorunu açıklanmaktadır. Her çalışanın gerçekleştirdiği görevlerin toplam boyutunun sabit bir sınırı vardır.
CP-SAT çözücüyü ve MIP çözücüyü kullanarak bu sorunu çözen Python programları sunacağız.
CP-SAT çözümü
İlk olarak, bu soruna yönelik CP-SAT çözümüne göz atalım.
Kitaplıkları içe aktarın
Aşağıdaki kod gerekli kitaplığı içe aktarır.
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;
Verileri tanımlama
Aşağıdaki kod, program verilerini oluşturur.
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;
Önceki örneklerde olduğu gibi maliyet matrisi, i çalışanının j görevini gerçekleştirme maliyetini belirtir.
sizes vektörü her görevin boyutunu verir.
total_size_max, herhangi bir çalışan tarafından gerçekleştirilen görevlerin toplam boyutunun üst sınırıdır.
Model oluşturma
Aşağıdaki kod modeli oluşturur.
Python
model = cp_model.CpModel()
C++
CpModelBuilder cp_model;
Java
CpModel model = new CpModel();
C#
CpModel model = new CpModel();
Değişkenleri oluşturma
Aşağıdaki kod, problem için bir değişken dizisi oluşturur.
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}]");
}
}
Kısıtlamaları ekleme
Aşağıdaki kod, program için kısıtlamalar oluşturur.
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);
}
Hedefi oluşturun
Aşağıdaki kod hedef işlevini oluşturur.
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);
Çözücüyü çağır
Aşağıdaki kod çözücüyü çağırır.
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}");
Sonuçları görüntüleyin
Artık çözümü yazdırabiliriz.
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.");
}
Programın sonucunu burada bulabilirsiniz.
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
Programın tamamı
Programın tamamını burada bulabilirsiniz.
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");
}
}
MIP çözümü
Sıradaki videoda, MIP çözücüyü kullanarak ödev problemine yönelik bir çözüm açıklıyoruz.
Kitaplıkları içe aktarın
Aşağıdaki kod gerekli kitaplığı içe aktarır.
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;
Verileri tanımlama
Aşağıdaki kod, program verilerini oluşturur.
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;
Çözücüyü bildirme
Aşağıdaki kod çözücüyü oluşturur.
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;
}
Değişkenleri oluşturma
Aşağıdaki kod, problem için bir değişken dizisi oluşturur.
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}]");
}
}
Sınırlamaları ekleme
Aşağıdaki kod, program için kısıtlamalar oluşturur.
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);
}
}
Hedefi oluşturun
Aşağıdaki kod hedef işlevini oluşturur.
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();
Çözücüyü çağır
Aşağıdaki kod çözücüyü çağırır ve sonuçları görüntüler.
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();
Sonuçları görüntüleyin
Artık çözümü yazdırabiliriz.
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.");
}
Programın sonucunu burada bulabilirsiniz.
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
Programın tamamı
Programın tamamını burada bulabilirsiniz.
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.");
}
}
}