การแก้ปัญหาเกี่ยวกับงาน

ส่วนนี้แสดงตัวอย่างที่แสดง วิธีแก้ปัญหางาน โดยใช้ทั้งตัวแก้โจทย์ MIP และตัวแก้โจทย์ CP-SAT

ตัวอย่าง

ในตัวอย่างมีผู้ปฏิบัติงาน 5 คน (ตัวเลข 0-4) และ 4 งาน (หมายเลข 0-3) โปรดทราบว่ามีผู้ปฏิบัติงานมากกว่า 1 คนในตัวอย่างใน ภาพรวม

ค่าใช้จ่ายของการมอบหมายงานให้ผู้ปฏิบัติงานจะปรากฏใน ตารางต่อไปนี้

ผู้ปฏิบัติงาน	งาน 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

ปัญหาคือมอบหมายงานให้ผู้ปฏิบัติงานแต่ละคนทำงานไม่เกิน 1 งาน ที่ไม่มีผู้ปฏิบัติงาน 2 คนทำงาน งานเดียวกันไปพร้อมๆ กับลดค่าใช้จ่ายโดยรวม เนื่องจากมีพนักงานมากกว่า งาน ผู้ปฏิบัติงาน 1 รายจะไม่ได้รับการมอบหมายงาน

โซลูชัน MIP

ส่วนต่อไปนี้จะอธิบายวิธีแก้ไขปัญหาโดยใช้ MPSolver Wrapper

นำเข้าไลบรารี

โค้ดต่อไปนี้นำเข้าไลบรารีที่จำเป็น

Python

from ortools.linear_solver import pywraplp

C++

#include <memory>
#include <vector>

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

C#

using System;
using Google.OrTools.LinearSolver;

สร้างข้อมูล

โค้ดต่อไปนี้จะสร้างข้อมูลของปัญหา

Python

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();

Java

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;

C#

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

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

สร้างตัวแปร

โค้ดต่อไปนี้จะสร้างตัวแปรจำนวนเต็มไบนารีสำหรับโจทย์

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

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 i = 0; i < numWorkers; ++i) {
  for (int j = 0; j < numTasks; ++j) {
    x[i][j] = solver.makeIntVar(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.
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}");
    }
}

สร้างข้อจำกัด

โค้ดต่อไปนี้จะสร้างข้อจำกัดสำหรับปัญหา

Python

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

Java

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

C#

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

สร้างฟังก์ชันวัตถุประสงค์

โค้ดต่อไปนี้จะสร้างฟังก์ชันวัตถุประสงค์สําหรับโจทย์

Python

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();

Java

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();

C#

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 โดยใช้ตัวแก้โจทย์

เรียกใช้เครื่องมือแก้โจทย์

โค้ดต่อไปนี้เรียกใช้เครื่องมือแก้โจทย์

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();

พิมพ์โซลูชัน

โค้ดต่อไปนี้จะพิมพ์วิธีแก้ปัญหา

Python

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

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

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");
    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 มีดังนี้

Python

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

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;

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

C#

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

นำเข้าไลบรารี

โค้ดต่อไปนี้นำเข้าไลบรารีที่จำเป็น

Python

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"

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 Google.OrTools.Sat;

ประกาศโมเดล

โค้ดต่อไปนี้แจ้งโมเดล CP-SAT

Python

model = cp_model.CpModel()

C++

CpModelBuilder cp_model;

Java

CpModel model = new CpModel();

C#

CpModel model = new CpModel();

สร้างข้อมูล

โค้ดต่อไปนี้เป็นการตั้งค่าข้อมูลของปัญหา

Python

  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());

Java

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();

C#

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 สอดคล้องกับ ตาราง ของค่าใช้จ่าย สำหรับการมอบหมายงานให้ผู้ปฏิบัติงานดังที่แสดงด้านบน

สร้างตัวแปร

โค้ดต่อไปนี้จะสร้างตัวแปรจำนวนเต็มไบนารีสำหรับโจทย์

Python

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

Java

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

C#

BoolVar[,] x = new BoolVar[numWorkers, numTasks];
// Variables in a 1-dim array.
for (int worker = 0; worker < numWorkers; ++worker)
{
    for (int task = 0; task < numTasks; ++task)
    {
        x[worker, task] = model.NewBoolVar($"worker_{worker}_task_{task}");
    }
}

สร้างข้อจำกัด

โค้ดต่อไปนี้จะสร้างข้อจำกัดสำหรับปัญหา

Python

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

Java

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

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

C#

// Each worker is assigned to at most one task.
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);
}

สร้างฟังก์ชันวัตถุประสงค์

โค้ดต่อไปนี้จะสร้างฟังก์ชันวัตถุประสงค์สําหรับโจทย์

Python

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

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();
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 โดยใช้ตัวแก้โจทย์

เรียกใช้เครื่องมือแก้โจทย์

โค้ดต่อไปนี้เรียกใช้เครื่องมือแก้โจทย์

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

พิมพ์โซลูชัน

โค้ดต่อไปนี้จะพิมพ์วิธีแก้ปัญหา

Python

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

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

C#

// 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 มีดังต่อไปนี้

Python

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

Java

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

C#

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