این بخش نمونه ای را ارائه می دهد که نشان می دهد چگونه می توان یک مسئله انتساب را با استفاده از حل کننده MIP و حل کننده CP-SAT حل کرد.
مثال
در مثال پنج کارگر (با شماره 0-4) و چهار وظیفه (با شماره 0-3) وجود دارد. توجه داشته باشید که یک کارگر بیشتر از مثال در نمای کلی وجود دارد.
هزینه های انتساب کارگران به وظایف در جدول زیر نشان داده شده است.
| کارگر | وظیفه 0 | وظیفه 1 | وظیفه 2 | وظیفه 3 |
|---|---|---|---|---|
| 0 | 90 | 80 | 75 | 70 |
| 1 | 35 | 85 | 55 | 65 |
| 2 | 125 | 95 | 90 | 95 |
| 3 | 45 | 110 | 95 | 115 |
| 4 | 50 | 100 | 90 | 100 |
مشکل این است که هر کارگر را حداکثر به یک کار اختصاص دهید، بدون اینکه دو کارگر یک کار را انجام دهند، در حالی که هزینه کل را به حداقل می رساند. از آنجایی که تعداد کارگران بیش از وظایف است، به یک کارگر وظیفه ای واگذار نمی شود.
راه حل MIP
بخش‌های زیر نحوه حل مشکل با استفاده از پوشش MPSolver را شرح می‌دهند.
کتابخانه ها را وارد کنید
کد زیر کتابخانه های مورد نیاز را وارد می کند.
پایتون
from ortools.linear_solver import pywraplp
C++
#include <memory> #include <vector> #include "ortools/base/logging.h" #include "ortools/linear_solver/linear_solver.h"
جاوا
import com.google.ortools.Loader; import com.google.ortools.linearsolver.MPConstraint; import com.google.ortools.linearsolver.MPObjective; import com.google.ortools.linearsolver.MPSolver; import com.google.ortools.linearsolver.MPVariable;
سی شارپ
using System; using Google.OrTools.LinearSolver;
داده ها را ایجاد کنید
کد زیر داده های مشکل را ایجاد می کند.
پایتون
costs = [
[90, 80, 75, 70],
[35, 85, 55, 65],
[125, 95, 90, 95],
[45, 110, 95, 115],
[50, 100, 90, 100],
]
num_workers = len(costs)
num_tasks = len(costs[0])C++
const std::vector<std::vector<double>> costs{
{90, 80, 75, 70}, {35, 85, 55, 65}, {125, 95, 90, 95},
{45, 110, 95, 115}, {50, 100, 90, 100},
};
const int num_workers = costs.size();
const int num_tasks = costs[0].size();جاوا
double[][] costs = {
{90, 80, 75, 70},
{35, 85, 55, 65},
{125, 95, 90, 95},
{45, 110, 95, 115},
{50, 100, 90, 100},
};
int numWorkers = costs.length;
int numTasks = costs[0].length;سی شارپ
int[,] costs = {
{ 90, 80, 75, 70 }, { 35, 85, 55, 65 }, { 125, 95, 90, 95 }, { 45, 110, 95, 115 }, { 50, 100, 90, 100 },
};
int numWorkers = costs.GetLength(0);
int numTasks = costs.GetLength(1); آرایه costs مربوط به جدول هزینه ها برای تخصیص کارگران به وظایف است که در بالا نشان داده شده است.
حل کننده MIP را اعلام کنید
کد زیر حل کننده MIP را اعلام می کند.
پایتون
# Create the mip solver with the SCIP backend.
solver = pywraplp.Solver.CreateSolver("SCIP")
if not solver:
returnC++
// Create the mip solver with the SCIP backend.
std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("SCIP"));
if (!solver) {
LOG(WARNING) << "SCIP solver unavailable.";
return;
}جاوا
// Create the linear solver with the SCIP backend.
MPSolver solver = MPSolver.createSolver("SCIP");
if (solver == null) {
System.out.println("Could not create solver SCIP");
return;
}سی شارپ
Solver solver = Solver.CreateSolver("SCIP");
if (solver is null)
{
return;
}متغیرها را ایجاد کنید
کد زیر متغیرهای عدد صحیح باینری را برای مشکل ایجاد می کند.
پایتون
# x[i, j] is an array of 0-1 variables, which will be 1
# if worker i is assigned to task j.
x = {}
for i in range(num_workers):
for j in range(num_tasks):
x[i, j] = solver.IntVar(0, 1, "")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 i = 0; i < num_workers; ++i) {
for (int j = 0; j < num_tasks; ++j) {
x[i][j] = solver->MakeIntVar(0, 1, "");
}
}جاوا
// 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 i = 0; i < numWorkers; ++i) {
for (int j = 0; j < numTasks; ++j) {
x[i][j] = solver.makeIntVar(0, 1, "");
}
}سی شارپ
// 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];
for (int i = 0; i < numWorkers; ++i)
{
for (int j = 0; j < numTasks; ++j)
{
x[i, j] = solver.MakeIntVar(0, 1, $"worker_{i}_task_{j}");
}
}محدودیت ها را ایجاد کنید
کد زیر محدودیت هایی را برای مشکل ایجاد می کند.
پایتون
# Each worker is assigned to at most 1 task.
for i in range(num_workers):
solver.Add(solver.Sum([x[i, j] for j in range(num_tasks)]) <= 1)
# Each task is assigned to exactly one worker.
for j in range(num_tasks):
solver.Add(solver.Sum([x[i, j] for i in range(num_workers)]) == 1)C++
// Each worker is assigned to at most one task.
for (int i = 0; i < num_workers; ++i) {
LinearExpr worker_sum;
for (int j = 0; j < num_tasks; ++j) {
worker_sum += x[i][j];
}
solver->MakeRowConstraint(worker_sum <= 1.0);
}
// Each task is assigned to exactly one worker.
for (int j = 0; j < num_tasks; ++j) {
LinearExpr task_sum;
for (int i = 0; i < num_workers; ++i) {
task_sum += x[i][j];
}
solver->MakeRowConstraint(task_sum == 1.0);
}جاوا
// Each worker is assigned to at most one task.
for (int i = 0; i < numWorkers; ++i) {
MPConstraint constraint = solver.makeConstraint(0, 1, "");
for (int j = 0; j < numTasks; ++j) {
constraint.setCoefficient(x[i][j], 1);
}
}
// Each task is assigned to exactly one worker.
for (int j = 0; j < numTasks; ++j) {
MPConstraint constraint = solver.makeConstraint(1, 1, "");
for (int i = 0; i < numWorkers; ++i) {
constraint.setCoefficient(x[i][j], 1);
}
}سی شارپ
// Each worker is assigned to at most one task.
for (int i = 0; i < numWorkers; ++i)
{
Constraint constraint = solver.MakeConstraint(0, 1, "");
for (int j = 0; j < numTasks; ++j)
{
constraint.SetCoefficient(x[i, j], 1);
}
}
// Each task is assigned to exactly one worker.
for (int j = 0; j < numTasks; ++j)
{
Constraint constraint = solver.MakeConstraint(1, 1, "");
for (int i = 0; i < numWorkers; ++i)
{
constraint.SetCoefficient(x[i, j], 1);
}
}تابع هدف را ایجاد کنید
کد زیر تابع هدف مشکل را ایجاد می کند.
پایتون
objective_terms = []
for i in range(num_workers):
for j in range(num_tasks):
objective_terms.append(costs[i][j] * x[i, j])
solver.Minimize(solver.Sum(objective_terms))C++
MPObjective* const objective = solver->MutableObjective();
for (int i = 0; i < num_workers; ++i) {
for (int j = 0; j < num_tasks; ++j) {
objective->SetCoefficient(x[i][j], costs[i][j]);
}
}
objective->SetMinimization();جاوا
MPObjective objective = solver.objective();
for (int i = 0; i < numWorkers; ++i) {
for (int j = 0; j < numTasks; ++j) {
objective.setCoefficient(x[i][j], costs[i][j]);
}
}
objective.setMinimization();سی شارپ
Objective objective = solver.Objective();
for (int i = 0; i < numWorkers; ++i)
{
for (int j = 0; j < numTasks; ++j)
{
objective.SetCoefficient(x[i, j], costs[i, j]);
}
}
objective.SetMinimization();مقدار تابع هدف کل هزینه تمام متغیرهایی است که توسط حل کننده مقدار 1 به آنها اختصاص داده شده است.
حل کننده را فراخوانی کنید
کد زیر حل کننده را فراخوانی می کند.
پایتون
print(f"Solving with {solver.SolverVersion()}")
status = solver.Solve()C++
const MPSolver::ResultStatus result_status = solver->Solve();
جاوا
MPSolver.ResultStatus resultStatus = solver.solve();
سی شارپ
Solver.ResultStatus resultStatus = solver.Solve();
محلول را چاپ کنید
کد زیر راه حل مشکل را چاپ می کند.
پایتون
if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE:
print(f"Total cost = {solver.Objective().Value()}\n")
for i in range(num_workers):
for j in range(num_tasks):
# Test if x[i,j] is 1 (with tolerance for floating point arithmetic).
if x[i, j].solution_value() > 0.5:
print(f"Worker {i} assigned to task {j}." + f" Cost: {costs[i][j]}")
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 i = 0; i < num_workers; ++i) {
for (int j = 0; j < num_tasks; ++j) {
// Test if x[i][j] is 0 or 1 (with tolerance for floating point
// arithmetic).
if (x[i][j]->solution_value() > 0.5) {
LOG(INFO) << "Worker " << i << " assigned to task " << j
<< ". Cost = " << costs[i][j];
}
}
}جاوا
// 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 i = 0; i < numWorkers; ++i) {
for (int j = 0; j < numTasks; ++j) {
// Test if x[i][j] is 0 or 1 (with tolerance for floating point
// arithmetic).
if (x[i][j].solutionValue() > 0.5) {
System.out.println(
"Worker " + i + " assigned to task " + j + ". Cost = " + costs[i][j]);
}
}
}
} else {
System.err.println("No solution found.");
}سی شارپ
// 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");
for (int i = 0; i < numWorkers; ++i)
{
for (int j = 0; j < numTasks; ++j)
{
// Test if x[i, j] is 0 or 1 (with tolerance for floating point
// arithmetic).
if (x[i, j].SolutionValue() > 0.5)
{
Console.WriteLine($"Worker {i} assigned to task {j}. Cost: {costs[i, j]}");
}
}
}
}
else
{
Console.WriteLine("No solution found.");
}اینم خروجی برنامه
Total cost = 265.0 Worker 0 assigned to task 3. Cost = 70 Worker 1 assigned to task 2. Cost = 55 Worker 2 assigned to task 1. Cost = 95 Worker 3 assigned to task 0. Cost = 45
برنامه های کامل
در اینجا برنامه های کامل برای راه حل MIP آمده است.
پایتون
from ortools.linear_solver import pywraplp
def main():
# Data
costs = [
[90, 80, 75, 70],
[35, 85, 55, 65],
[125, 95, 90, 95],
[45, 110, 95, 115],
[50, 100, 90, 100],
]
num_workers = len(costs)
num_tasks = len(costs[0])
# 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 i in range(num_workers):
for j in range(num_tasks):
x[i, j] = solver.IntVar(0, 1, "")
# Constraints
# Each worker is assigned to at most 1 task.
for i in range(num_workers):
solver.Add(solver.Sum([x[i, j] for j in range(num_tasks)]) <= 1)
# Each task is assigned to exactly one worker.
for j in range(num_tasks):
solver.Add(solver.Sum([x[i, j] for i in range(num_workers)]) == 1)
# Objective
objective_terms = []
for i in range(num_workers):
for j in range(num_tasks):
objective_terms.append(costs[i][j] * x[i, j])
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 i in range(num_workers):
for j in range(num_tasks):
# Test if x[i,j] is 1 (with tolerance for floating point arithmetic).
if x[i, j].solution_value() > 0.5:
print(f"Worker {i} assigned to task {j}." + f" Cost: {costs[i][j]}")
else:
print("No solution found.")
if __name__ == "__main__":
main()C++
#include <memory>
#include <vector>
#include "ortools/base/logging.h"
#include "ortools/linear_solver/linear_solver.h"
namespace operations_research {
void AssignmentMip() {
// Data
const std::vector<std::vector<double>> costs{
{90, 80, 75, 70}, {35, 85, 55, 65}, {125, 95, 90, 95},
{45, 110, 95, 115}, {50, 100, 90, 100},
};
const int num_workers = costs.size();
const int num_tasks = costs[0].size();
// 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 i = 0; i < num_workers; ++i) {
for (int j = 0; j < num_tasks; ++j) {
x[i][j] = solver->MakeIntVar(0, 1, "");
}
}
// Constraints
// Each worker is assigned to at most one task.
for (int i = 0; i < num_workers; ++i) {
LinearExpr worker_sum;
for (int j = 0; j < num_tasks; ++j) {
worker_sum += x[i][j];
}
solver->MakeRowConstraint(worker_sum <= 1.0);
}
// Each task is assigned to exactly one worker.
for (int j = 0; j < num_tasks; ++j) {
LinearExpr task_sum;
for (int i = 0; i < num_workers; ++i) {
task_sum += x[i][j];
}
solver->MakeRowConstraint(task_sum == 1.0);
}
// Objective.
MPObjective* const objective = solver->MutableObjective();
for (int i = 0; i < num_workers; ++i) {
for (int j = 0; j < num_tasks; ++j) {
objective->SetCoefficient(x[i][j], costs[i][j]);
}
}
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 i = 0; i < num_workers; ++i) {
for (int j = 0; j < num_tasks; ++j) {
// Test if x[i][j] is 0 or 1 (with tolerance for floating point
// arithmetic).
if (x[i][j]->solution_value() > 0.5) {
LOG(INFO) << "Worker " << i << " assigned to task " << j
<< ". Cost = " << costs[i][j];
}
}
}
}
} // namespace operations_research
int main(int argc, char** argv) {
operations_research::AssignmentMip();
return EXIT_SUCCESS;
}جاوا
package com.google.ortools.linearsolver.samples;
import com.google.ortools.Loader;
import com.google.ortools.linearsolver.MPConstraint;
import com.google.ortools.linearsolver.MPObjective;
import com.google.ortools.linearsolver.MPSolver;
import com.google.ortools.linearsolver.MPVariable;
/** MIP example that solves an assignment problem. */
public class AssignmentMip {
public static void main(String[] args) {
Loader.loadNativeLibraries();
// Data
double[][] costs = {
{90, 80, 75, 70},
{35, 85, 55, 65},
{125, 95, 90, 95},
{45, 110, 95, 115},
{50, 100, 90, 100},
};
int numWorkers = costs.length;
int numTasks = costs[0].length;
// 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 i = 0; i < numWorkers; ++i) {
for (int j = 0; j < numTasks; ++j) {
x[i][j] = solver.makeIntVar(0, 1, "");
}
}
// Constraints
// Each worker is assigned to at most one task.
for (int i = 0; i < numWorkers; ++i) {
MPConstraint constraint = solver.makeConstraint(0, 1, "");
for (int j = 0; j < numTasks; ++j) {
constraint.setCoefficient(x[i][j], 1);
}
}
// Each task is assigned to exactly one worker.
for (int j = 0; j < numTasks; ++j) {
MPConstraint constraint = solver.makeConstraint(1, 1, "");
for (int i = 0; i < numWorkers; ++i) {
constraint.setCoefficient(x[i][j], 1);
}
}
// Objective
MPObjective objective = solver.objective();
for (int i = 0; i < numWorkers; ++i) {
for (int j = 0; j < numTasks; ++j) {
objective.setCoefficient(x[i][j], costs[i][j]);
}
}
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 i = 0; i < numWorkers; ++i) {
for (int j = 0; j < numTasks; ++j) {
// Test if x[i][j] is 0 or 1 (with tolerance for floating point
// arithmetic).
if (x[i][j].solutionValue() > 0.5) {
System.out.println(
"Worker " + i + " assigned to task " + j + ". Cost = " + costs[i][j]);
}
}
}
} else {
System.err.println("No solution found.");
}
}
private AssignmentMip() {}
}سی شارپ
using System;
using Google.OrTools.LinearSolver;
public class AssignmentMip
{
static void Main()
{
// Data.
int[,] costs = {
{ 90, 80, 75, 70 }, { 35, 85, 55, 65 }, { 125, 95, 90, 95 }, { 45, 110, 95, 115 }, { 50, 100, 90, 100 },
};
int numWorkers = costs.GetLength(0);
int numTasks = costs.GetLength(1);
// 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];
for (int i = 0; i < numWorkers; ++i)
{
for (int j = 0; j < numTasks; ++j)
{
x[i, j] = solver.MakeIntVar(0, 1, $"worker_{i}_task_{j}");
}
}
// Constraints
// Each worker is assigned to at most one task.
for (int i = 0; i < numWorkers; ++i)
{
Constraint constraint = solver.MakeConstraint(0, 1, "");
for (int j = 0; j < numTasks; ++j)
{
constraint.SetCoefficient(x[i, j], 1);
}
}
// Each task is assigned to exactly one worker.
for (int j = 0; j < numTasks; ++j)
{
Constraint constraint = solver.MakeConstraint(1, 1, "");
for (int i = 0; i < numWorkers; ++i)
{
constraint.SetCoefficient(x[i, j], 1);
}
}
// Objective
Objective objective = solver.Objective();
for (int i = 0; i < numWorkers; ++i)
{
for (int j = 0; j < numTasks; ++j)
{
objective.SetCoefficient(x[i, j], costs[i, j]);
}
}
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");
for (int i = 0; i < numWorkers; ++i)
{
for (int j = 0; j < numTasks; ++j)
{
// Test if x[i, j] is 0 or 1 (with tolerance for floating point
// arithmetic).
if (x[i, j].SolutionValue() > 0.5)
{
Console.WriteLine($"Worker {i} assigned to task {j}. Cost: {costs[i, j]}");
}
}
}
}
else
{
Console.WriteLine("No solution found.");
}
}
}راه حل CP SAT
بخش های زیر نحوه حل مشکل با استفاده از حل کننده CP-SAT را شرح می دهد.
کتابخانه ها را وارد کنید
کد زیر کتابخانه های مورد نیاز را وارد می کند.
پایتون
import io import pandas as pd from ortools.sat.python import cp_model
C++
#include <stdlib.h> #include <vector> #include "ortools/base/logging.h" #include "ortools/sat/cp_model.h" #include "ortools/sat/cp_model.pb.h" #include "ortools/sat/cp_model_solver.h"
جاوا
import com.google.ortools.Loader; import com.google.ortools.sat.CpModel; import com.google.ortools.sat.CpSolver; import com.google.ortools.sat.CpSolverStatus; import com.google.ortools.sat.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;
سی شارپ
using System; using System.Collections.Generic; using Google.OrTools.Sat;
مدل را اعلام کنید
کد زیر مدل CP-SAT را اعلام می کند.
پایتون
model = cp_model.CpModel()
C++
CpModelBuilder cp_model;
جاوا
CpModel model = new CpModel();
سی شارپ
CpModel model = new CpModel();
داده ها را ایجاد کنید
کد زیر داده های مشکل را تنظیم می کند.
پایتون
data_str = """
worker task cost
w1 t1 90
w1 t2 80
w1 t3 75
w1 t4 70
w2 t1 35
w2 t2 85
w2 t3 55
w2 t4 65
w3 t1 125
w3 t2 95
w3 t3 90
w3 t4 95
w4 t1 45
w4 t2 110
w4 t3 95
w4 t4 115
w5 t1 50
w5 t2 110
w5 t3 90
w5 t4 100
"""
data = pd.read_table(io.StringIO(data_str), sep=r"\s+")C++
const std::vector<std::vector<int>> costs{
{90, 80, 75, 70}, {35, 85, 55, 65}, {125, 95, 90, 95},
{45, 110, 95, 115}, {50, 100, 90, 100},
};
const int num_workers = static_cast<int>(costs.size());
const int num_tasks = static_cast<int>(costs[0].size());جاوا
int[][] costs = {
{90, 80, 75, 70},
{35, 85, 55, 65},
{125, 95, 90, 95},
{45, 110, 95, 115},
{50, 100, 90, 100},
};
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();سی شارپ
int[,] costs = {
{ 90, 80, 75, 70 }, { 35, 85, 55, 65 }, { 125, 95, 90, 95 }, { 45, 110, 95, 115 }, { 50, 100, 90, 100 },
};
int numWorkers = costs.GetLength(0);
int numTasks = costs.GetLength(1); آرایه costs مربوط به جدول هزینه ها برای تخصیص کارگران به وظایف است که در بالا نشان داده شده است.
متغیرها را ایجاد کنید
کد زیر متغیرهای عدد صحیح باینری را برای مشکل ایجاد می کند.
پایتون
x = model.new_bool_var_series(name="x", index=data.index)
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 i = 0; i < num_workers; ++i) {
for (int j = 0; j < num_tasks; ++j) {
x[i][j] = cp_model.NewBoolVar();
}
}جاوا
Literal[][] x = new Literal[numWorkers][numTasks];
for (int worker : allWorkers) {
for (int task : allTasks) {
x[worker][task] = model.newBoolVar("x[" + worker + "," + task + "]");
}
}سی شارپ
BoolVar[,] x = new BoolVar[numWorkers, numTasks];
// Variables in a 1-dim array.
for (int worker = 0; worker < numWorkers; ++worker)
{
for (int task = 0; task < numTasks; ++task)
{
x[worker, task] = model.NewBoolVar($"worker_{worker}_task_{task}");
}
}محدودیت ها را ایجاد کنید
کد زیر محدودیت هایی را برای مشکل ایجاد می کند.
پایتون
# Each worker is assigned to at most one task.
for unused_name, tasks in data.groupby("worker"):
model.add_at_most_one(x[tasks.index])
# Each task is assigned to exactly one worker.
for unused_name, workers in data.groupby("task"):
model.add_exactly_one(x[workers.index])C++
// Each worker is assigned to at most one task.
for (int i = 0; i < num_workers; ++i) {
cp_model.AddAtMostOne(x[i]);
}
// Each task is assigned to exactly one worker.
for (int j = 0; j < num_tasks; ++j) {
std::vector<BoolVar> tasks;
for (int i = 0; i < num_workers; ++i) {
tasks.push_back(x[i][j]);
}
cp_model.AddExactlyOne(tasks);
}جاوا
// Each worker is assigned to at most one task.
for (int worker : allWorkers) {
List<Literal> tasks = new ArrayList<>();
for (int task : allTasks) {
tasks.add(x[worker][task]);
}
model.addAtMostOne(tasks);
}
// Each task is assigned to exactly one worker.
for (int task : allTasks) {
List<Literal> workers = new ArrayList<>();
for (int worker : allWorkers) {
workers.add(x[worker][task]);
}
model.addExactlyOne(workers);
}سی شارپ
// Each worker is assigned to at most one task.
for (int worker = 0; worker < numWorkers; ++worker)
{
List<ILiteral> tasks = new List<ILiteral>();
for (int task = 0; task < numTasks; ++task)
{
tasks.Add(x[worker, task]);
}
model.AddAtMostOne(tasks);
}
// Each task is assigned to exactly one worker.
for (int task = 0; task < numTasks; ++task)
{
List<ILiteral> workers = new List<ILiteral>();
for (int worker = 0; worker < numWorkers; ++worker)
{
workers.Add(x[worker, task]);
}
model.AddExactlyOne(workers);
}تابع هدف را ایجاد کنید
کد زیر تابع هدف مشکل را ایجاد می کند.
پایتون
model.minimize(data.cost.dot(x))
C++
LinearExpr total_cost;
for (int i = 0; i < num_workers; ++i) {
for (int j = 0; j < num_tasks; ++j) {
total_cost += x[i][j] * costs[i][j];
}
}
cp_model.Minimize(total_cost);جاوا
LinearExprBuilder obj = LinearExpr.newBuilder();
for (int worker : allWorkers) {
for (int task : allTasks) {
obj.addTerm(x[worker][task], costs[worker][task]);
}
}
model.minimize(obj);سی شارپ
LinearExprBuilder obj = LinearExpr.NewBuilder();
for (int worker = 0; worker < numWorkers; ++worker)
{
for (int task = 0; task < numTasks; ++task)
{
obj.AddTerm((IntVar)x[worker, task], costs[worker, task]);
}
}
model.Minimize(obj);مقدار تابع هدف کل هزینه تمام متغیرهایی است که توسط حل کننده مقدار 1 به آنها اختصاص داده شده است.
حل کننده را فراخوانی کنید
کد زیر حل کننده را فراخوانی می کند.
پایتون
solver = cp_model.CpSolver() status = solver.solve(model)
C++
const CpSolverResponse response = Solve(cp_model.Build());
جاوا
CpSolver solver = new CpSolver(); CpSolverStatus status = solver.solve(model);
سی شارپ
CpSolver solver = new CpSolver();
CpSolverStatus status = solver.Solve(model);
Console.WriteLine($"Solve status: {status}");محلول را چاپ کنید
کد زیر راه حل مشکل را چاپ می کند.
پایتون
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
print(f"Total cost = {solver.objective_value}\n")
selected = data.loc[solver.boolean_values(x).loc[lambda x: x].index]
for unused_index, row in selected.iterrows():
print(f"{row.task} assigned to {row.worker} with a cost of {row.cost}")
elif status == cp_model.INFEASIBLE:
print("No solution found")
else:
print("Something is wrong, check the status and the log of the solve")C++
if (response.status() == CpSolverStatus::INFEASIBLE) {
LOG(FATAL) << "No solution found.";
}
LOG(INFO) << "Total cost: " << response.objective_value();
LOG(INFO);
for (int i = 0; i < num_workers; ++i) {
for (int j = 0; j < num_tasks; ++j) {
if (SolutionBooleanValue(response, x[i][j])) {
LOG(INFO) << "Task " << i << " assigned to worker " << j
<< ". Cost: " << costs[i][j];
}
}
}جاوا
// 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 i = 0; i < numWorkers; ++i) {
for (int j = 0; j < numTasks; ++j) {
if (solver.booleanValue(x[i][j])) {
System.out.println(
"Worker " + i + " assigned to task " + j + ". Cost: " + costs[i][j]);
}
}
}
} else {
System.err.println("No solution found.");
}سی شارپ
// Check that the problem has a feasible solution.
if (status == CpSolverStatus.Optimal || status == CpSolverStatus.Feasible)
{
Console.WriteLine($"Total cost: {solver.ObjectiveValue}\n");
for (int i = 0; i < numWorkers; ++i)
{
for (int j = 0; j < numTasks; ++j)
{
if (solver.Value(x[i, j]) > 0.5)
{
Console.WriteLine($"Worker {i} assigned to task {j}. Cost: {costs[i, j]}");
}
}
}
}
else
{
Console.WriteLine("No solution found.");
}اینم خروجی برنامه
Total cost = 265 Worker 0 assigned to task 3 Cost = 70 Worker 1 assigned to task 2 Cost = 55 Worker 2 assigned to task 1 Cost = 95 Worker 3 assigned to task 0 Cost = 45
برنامه های کامل
در اینجا برنامه های کامل برای راه حل CP-SAT آمده است.
پایتون
import io
import pandas as pd
from ortools.sat.python import cp_model
def main() -> None:
# Data
data_str = """
worker task cost
w1 t1 90
w1 t2 80
w1 t3 75
w1 t4 70
w2 t1 35
w2 t2 85
w2 t3 55
w2 t4 65
w3 t1 125
w3 t2 95
w3 t3 90
w3 t4 95
w4 t1 45
w4 t2 110
w4 t3 95
w4 t4 115
w5 t1 50
w5 t2 110
w5 t3 90
w5 t4 100
"""
data = pd.read_table(io.StringIO(data_str), sep=r"\s+")
# Model
model = cp_model.CpModel()
# Variables
x = model.new_bool_var_series(name="x", index=data.index)
# Constraints
# Each worker is assigned to at most one task.
for unused_name, tasks in data.groupby("worker"):
model.add_at_most_one(x[tasks.index])
# Each task is assigned to exactly one worker.
for unused_name, workers in data.groupby("task"):
model.add_exactly_one(x[workers.index])
# Objective
model.minimize(data.cost.dot(x))
# 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")
selected = data.loc[solver.boolean_values(x).loc[lambda x: x].index]
for unused_index, row in selected.iterrows():
print(f"{row.task} assigned to {row.worker} with a cost of {row.cost}")
elif status == cp_model.INFEASIBLE:
print("No solution found")
else:
print("Something is wrong, check the status and the log of the solve")
if __name__ == "__main__":
main()C++
#include <stdlib.h>
#include <vector>
#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 IntegerProgrammingExample() {
// Data
const std::vector<std::vector<int>> costs{
{90, 80, 75, 70}, {35, 85, 55, 65}, {125, 95, 90, 95},
{45, 110, 95, 115}, {50, 100, 90, 100},
};
const int num_workers = static_cast<int>(costs.size());
const int num_tasks = static_cast<int>(costs[0].size());
// 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 i = 0; i < num_workers; ++i) {
for (int j = 0; j < num_tasks; ++j) {
x[i][j] = cp_model.NewBoolVar();
}
}
// Constraints
// Each worker is assigned to at most one task.
for (int i = 0; i < num_workers; ++i) {
cp_model.AddAtMostOne(x[i]);
}
// Each task is assigned to exactly one worker.
for (int j = 0; j < num_tasks; ++j) {
std::vector<BoolVar> tasks;
for (int i = 0; i < num_workers; ++i) {
tasks.push_back(x[i][j]);
}
cp_model.AddExactlyOne(tasks);
}
// Objective
LinearExpr total_cost;
for (int i = 0; i < num_workers; ++i) {
for (int j = 0; j < num_tasks; ++j) {
total_cost += x[i][j] * costs[i][j];
}
}
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 i = 0; i < num_workers; ++i) {
for (int j = 0; j < num_tasks; ++j) {
if (SolutionBooleanValue(response, x[i][j])) {
LOG(INFO) << "Task " << i << " assigned to worker " << j
<< ". Cost: " << costs[i][j];
}
}
}
}
} // namespace sat
} // namespace operations_research
int main(int argc, char** argv) {
operations_research::sat::IntegerProgrammingExample();
return EXIT_SUCCESS;
}جاوا
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 AssignmentSat {
public static void main(String[] args) {
Loader.loadNativeLibraries();
// Data
int[][] costs = {
{90, 80, 75, 70},
{35, 85, 55, 65},
{125, 95, 90, 95},
{45, 110, 95, 115},
{50, 100, 90, 100},
};
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();
// Model
CpModel model = new CpModel();
// Variables
Literal[][] x = new Literal[numWorkers][numTasks];
for (int worker : allWorkers) {
for (int task : allTasks) {
x[worker][task] = model.newBoolVar("x[" + worker + "," + task + "]");
}
}
// Constraints
// Each worker is assigned to at most one task.
for (int worker : allWorkers) {
List<Literal> tasks = new ArrayList<>();
for (int task : allTasks) {
tasks.add(x[worker][task]);
}
model.addAtMostOne(tasks);
}
// Each task is assigned to exactly one worker.
for (int task : allTasks) {
List<Literal> workers = new ArrayList<>();
for (int worker : allWorkers) {
workers.add(x[worker][task]);
}
model.addExactlyOne(workers);
}
// 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 i = 0; i < numWorkers; ++i) {
for (int j = 0; j < numTasks; ++j) {
if (solver.booleanValue(x[i][j])) {
System.out.println(
"Worker " + i + " assigned to task " + j + ". Cost: " + costs[i][j]);
}
}
}
} else {
System.err.println("No solution found.");
}
}
private AssignmentSat() {}
}
سی شارپ
using System;
using System.Collections.Generic;
using Google.OrTools.Sat;
public class AssignmentSat
{
public static void Main(String[] args)
{
// Data.
int[,] costs = {
{ 90, 80, 75, 70 }, { 35, 85, 55, 65 }, { 125, 95, 90, 95 }, { 45, 110, 95, 115 }, { 50, 100, 90, 100 },
};
int numWorkers = costs.GetLength(0);
int numTasks = costs.GetLength(1);
// Model.
CpModel model = new CpModel();
// Variables.
BoolVar[,] x = new BoolVar[numWorkers, numTasks];
// Variables in a 1-dim array.
for (int worker = 0; worker < numWorkers; ++worker)
{
for (int task = 0; task < numTasks; ++task)
{
x[worker, task] = model.NewBoolVar($"worker_{worker}_task_{task}");
}
}
// Constraints
// Each worker is assigned to at most one task.
for (int worker = 0; worker < numWorkers; ++worker)
{
List<ILiteral> tasks = new List<ILiteral>();
for (int task = 0; task < numTasks; ++task)
{
tasks.Add(x[worker, task]);
}
model.AddAtMostOne(tasks);
}
// Each task is assigned to exactly one worker.
for (int task = 0; task < numTasks; ++task)
{
List<ILiteral> workers = new List<ILiteral>();
for (int worker = 0; worker < numWorkers; ++worker)
{
workers.Add(x[worker, task]);
}
model.AddExactlyOne(workers);
}
// Objective
LinearExprBuilder obj = LinearExpr.NewBuilder();
for (int worker = 0; worker < numWorkers; ++worker)
{
for (int task = 0; task < numTasks; ++task)
{
obj.AddTerm((IntVar)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");
for (int i = 0; i < numWorkers; ++i)
{
for (int j = 0; j < numTasks; ++j)
{
if (solver.Value(x[i, j]) > 0.5)
{
Console.WriteLine($"Worker {i} assigned to task {j}. Cost: {costs[i, j]}");
}
}
}
}
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");
}
}