حل کننده CP اصلی

این بخش حل کننده اصلی برنامه نویسی محدودیت را توضیح می دهد که با حل کننده برتر CP-SAT جایگزین شده است.

توجه: ما قویاً توصیه می کنیم از حل کننده CP-SAT به جای حل کننده اصلی CP استفاده کنید.

بخش های زیر نحوه حل مثال توضیح داده شده در بخش CP-SAT را توضیح می دهند، این بار با استفاده از حل کننده اصلی CP. اگر اصرار دارید از حل‌کننده اصلی CP استفاده کنید، می‌توانید مرجع API را مرور کنید. توجه داشته باشید که حل کننده اصلی CP پایه و اساس کتابخانه مسیریابی است و API آن ممکن است برای سفارشی کردن یک مدل مسیریابی ضروری باشد.

کتابخانه ها را وارد کنید

کد زیر کتابخانه مورد نیاز را وارد می کند.

پایتون

from ortools.constraint_solver import pywrapcp

C++

#include <ostream>
#include <string>

#include "ortools/constraint_solver/constraint_solver.h"

جاوا

import com.google.ortools.Loader;
import com.google.ortools.constraintsolver.DecisionBuilder;
import com.google.ortools.constraintsolver.IntVar;
import com.google.ortools.constraintsolver.Solver;
import java.util.logging.Logger;

سی شارپ

using System;
using Google.OrTools.ConstraintSolver;

حل کننده را اعلام کنید

کد زیر حل کننده را اعلام می کند.

پایتون

solver = pywrapcp.Solver("CPSimple")

C++

Solver solver("CpSimple");

جاوا

Solver solver = new Solver("CpSimple");

سی شارپ

Solver solver = new Solver("CpSimple");

متغیرها را ایجاد کنید

کد زیر متغیرهای مشکل را ایجاد می کند.

حل کننده سه متغیر x، y و z ایجاد می کند که هر کدام می توانند مقادیر 0، 1 یا 2 را داشته باشند.

پایتون

num_vals = 3
x = solver.IntVar(0, num_vals - 1, "x")
y = solver.IntVar(0, num_vals - 1, "y")
z = solver.IntVar(0, num_vals - 1, "z")

C++

const int64_t num_vals = 3;
IntVar* const x = solver.MakeIntVar(0, num_vals - 1, "x");
IntVar* const y = solver.MakeIntVar(0, num_vals - 1, "y");
IntVar* const z = solver.MakeIntVar(0, num_vals - 1, "z");

جاوا

final long numVals = 3;
final IntVar x = solver.makeIntVar(0, numVals - 1, "x");
final IntVar y = solver.makeIntVar(0, numVals - 1, "y");
final IntVar z = solver.makeIntVar(0, numVals - 1, "z");

سی شارپ

const long numVals = 3;
IntVar x = solver.MakeIntVar(0, numVals - 1, "x");
IntVar y = solver.MakeIntVar(0, numVals - 1, "y");
IntVar z = solver.MakeIntVar(0, numVals - 1, "z");

محدودیت ایجاد کنید

کد زیر محدودیت x ≠ y

پایتون

solver.Add(x != y)
print("Number of constraints: ", solver.Constraints())

C++

solver.AddConstraint(solver.MakeAllDifferent({x, y}));
LOG(INFO) << "Number of constraints: "
          << std::to_string(solver.constraints());

جاوا

solver.addConstraint(solver.makeAllDifferent(new IntVar[] {x, y}));
logger.info("Number of constraints: " + solver.constraints());

سی شارپ

solver.Add(solver.MakeAllDifferent(new IntVar[] { x, y }));
Console.WriteLine($"Number of constraints: {solver.Constraints()}");

با حل کننده تماس بگیرید

کد زیر حل کننده را فراخوانی می کند.

تصمیم ساز ورودی اصلی حل کننده CP اصلی است. این شامل موارد زیر است:

• vars - آرایه ای حاوی متغیرهای مسئله.
• یک قانون برای انتخاب متغیر بعدی برای تخصیص یک مقدار.
• یک قانون برای انتخاب مقدار بعدی برای تخصیص به آن متغیر.

برای جزئیات بیشتر به Decision builder مراجعه کنید.

پایتون

decision_builder = solver.Phase(
    [x, y, z], solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE
)

C++

DecisionBuilder* const db = solver.MakePhase(
    {x, y, z}, Solver::CHOOSE_FIRST_UNBOUND, Solver::ASSIGN_MIN_VALUE);

جاوا

final DecisionBuilder db = solver.makePhase(
    new IntVar[] {x, y, z}, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE);

سی شارپ

DecisionBuilder db =
    solver.MakePhase(new IntVar[] { x, y, z }, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE);

محلول را چاپ کنید

کد چاپگر راه حل، که هر راه حل را همانطور که حل کننده آن را پیدا می کند، نمایش می دهد، در بخش زیر نشان داده شده است.

از آنجایی که بیش از یک راه حل برای مشکل ما وجود دارد، می توان از طریق راه حل ها با حلقه while solver.NextSolution() تکرار کرد. (توجه داشته باشید که این کار با چاپگر راه حل برای حل کننده CP-SAT متفاوت است).

پایتون

count = 0
solver.NewSearch(decision_builder)
while solver.NextSolution():
    count += 1
    solution = f"Solution {count}:\n"
    for var in [x, y, z]:
        solution += f" {var.Name()} = {var.Value()}"
    print(solution)
solver.EndSearch()
print(f"Number of solutions found: {count}")

C++

int count = 0;
solver.NewSearch(db);
while (solver.NextSolution()) {
  ++count;
  LOG(INFO) << "Solution " << count << ":" << std::endl
            << " x=" << x->Value() << " y=" << y->Value()
            << " z=" << z->Value();
}
solver.EndSearch();
LOG(INFO) << "Number of solutions found: " << solver.solutions();

جاوا

int count = 0;
solver.newSearch(db);
while (solver.nextSolution()) {
  ++count;
  logger.info(
      String.format("Solution: %d\n x=%d y=%d z=%d", count, x.value(), y.value(), z.value()));
}
solver.endSearch();
logger.info("Number of solutions found: " + solver.solutions());

سی شارپ

int count = 0;
solver.NewSearch(db);
while (solver.NextSolution())
{
    ++count;
    Console.WriteLine($"Solution: {count}\n x={x.Value()} y={y.Value()} z={z.Value()}");
}
solver.EndSearch();
Console.WriteLine($"Number of solutions found: {solver.Solutions()}");

نتایج توسط حل کننده برگردانده شده است

در اینجا 18 راه حل یافت شده توسط حل کننده آورده شده است:

Number of constraints:  1
Solution 1:
 x = 0 y = 1 z = 0
Solution 2:
 x = 0 y = 1 z = 1
Solution 3:
 x = 0 y = 1 z = 2
Solution 4:
 x = 0 y = 2 z = 0
Solution 5:
 x = 0 y = 2 z = 1
Solution 6:
 x = 0 y = 2 z = 2
Solution 7:
 x = 1 y = 0 z = 0
Solution 8:
 x = 1 y = 0 z = 1
Solution 9:
 x = 1 y = 0 z = 2
Solution 10:
 x = 1 y = 2 z = 0
Solution 11:
 x = 1 y = 2 z = 1
Solution 12:
 x = 1 y = 2 z = 2
Solution 13:
 x = 2 y = 0 z = 0
Solution 14:
 x = 2 y = 0 z = 1
Solution 15:
 x = 2 y = 0 z = 2
Solution 16:
 x = 2 y = 1 z = 0
Solution 17:
 x = 2 y = 1 z = 1
Solution 18:
 x = 2 y = 1 z = 2
Number of solutions found:  18
Advanced usage:
Problem solved in  2 ms
Memory usage:  13918208 bytes

برنامه کامل

در اینجا برنامه های کامل برای مثال با استفاده از حل کننده اصلی CP آورده شده است.

پایتون

"""Simple Constraint optimization example."""

from ortools.constraint_solver import pywrapcp


def main():
    """Entry point of the program."""
    # Instantiate the solver.
    solver = pywrapcp.Solver("CPSimple")

    # Create the variables.
    num_vals = 3
    x = solver.IntVar(0, num_vals - 1, "x")
    y = solver.IntVar(0, num_vals - 1, "y")
    z = solver.IntVar(0, num_vals - 1, "z")

    # Constraint 0: x != y.
    solver.Add(x != y)
    print("Number of constraints: ", solver.Constraints())

    # Solve the problem.
    decision_builder = solver.Phase(
        [x, y, z], solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE
    )

    # Print solution on console.
    count = 0
    solver.NewSearch(decision_builder)
    while solver.NextSolution():
        count += 1
        solution = f"Solution {count}:\n"
        for var in [x, y, z]:
            solution += f" {var.Name()} = {var.Value()}"
        print(solution)
    solver.EndSearch()
    print(f"Number of solutions found: {count}")

    print("Advanced usage:")
    print(f"Problem solved in {solver.WallTime()}ms")
    print(f"Memory usage: {pywrapcp.Solver.MemoryUsage()}bytes")


if __name__ == "__main__":
    main()

C++

#include <ostream>
#include <string>

#include "ortools/constraint_solver/constraint_solver.h"

namespace operations_research {

void SimpleCpProgram() {
  // Instantiate the solver.
  Solver solver("CpSimple");

  // Create the variables.
  const int64_t num_vals = 3;
  IntVar* const x = solver.MakeIntVar(0, num_vals - 1, "x");
  IntVar* const y = solver.MakeIntVar(0, num_vals - 1, "y");
  IntVar* const z = solver.MakeIntVar(0, num_vals - 1, "z");

  // Constraint 0: x != y..
  solver.AddConstraint(solver.MakeAllDifferent({x, y}));
  LOG(INFO) << "Number of constraints: "
            << std::to_string(solver.constraints());

  // Solve the problem.
  DecisionBuilder* const db = solver.MakePhase(
      {x, y, z}, Solver::CHOOSE_FIRST_UNBOUND, Solver::ASSIGN_MIN_VALUE);

  // Print solution on console.
  int count = 0;
  solver.NewSearch(db);
  while (solver.NextSolution()) {
    ++count;
    LOG(INFO) << "Solution " << count << ":" << std::endl
              << " x=" << x->Value() << " y=" << y->Value()
              << " z=" << z->Value();
  }
  solver.EndSearch();
  LOG(INFO) << "Number of solutions found: " << solver.solutions();

  LOG(INFO) << "Advanced usage:" << std::endl
            << "Problem solved in " << std::to_string(solver.wall_time())
            << "ms" << std::endl
            << "Memory usage: " << std::to_string(Solver::MemoryUsage())
            << "bytes";
}

}  // namespace operations_research

int main(int /*argc*/, char* /*argv*/[]) {
  operations_research::SimpleCpProgram();
  return EXIT_SUCCESS;
}

جاوا

package com.google.ortools.constraintsolver.samples;
import com.google.ortools.Loader;
import com.google.ortools.constraintsolver.DecisionBuilder;
import com.google.ortools.constraintsolver.IntVar;
import com.google.ortools.constraintsolver.Solver;
import java.util.logging.Logger;

/** Simple CP Program.*/
public class SimpleCpProgram {
  private SimpleCpProgram() {}

  private static final Logger logger = Logger.getLogger(SimpleCpProgram.class.getName());

  public static void main(String[] args) throws Exception {
    Loader.loadNativeLibraries();
    // Instantiate the solver.
    Solver solver = new Solver("CpSimple");

    // Create the variables.
    final long numVals = 3;
    final IntVar x = solver.makeIntVar(0, numVals - 1, "x");
    final IntVar y = solver.makeIntVar(0, numVals - 1, "y");
    final IntVar z = solver.makeIntVar(0, numVals - 1, "z");

    // Constraint 0: x != y..
    solver.addConstraint(solver.makeAllDifferent(new IntVar[] {x, y}));
    logger.info("Number of constraints: " + solver.constraints());

    // Solve the problem.
    final DecisionBuilder db = solver.makePhase(
        new IntVar[] {x, y, z}, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE);

    // Print solution on console.
    int count = 0;
    solver.newSearch(db);
    while (solver.nextSolution()) {
      ++count;
      logger.info(
          String.format("Solution: %d\n x=%d y=%d z=%d", count, x.value(), y.value(), z.value()));
    }
    solver.endSearch();
    logger.info("Number of solutions found: " + solver.solutions());

    logger.info(String.format("Advanced usage:\nProblem solved in %d ms\nMemory usage: %d bytes",
        solver.wallTime(), Solver.memoryUsage()));
  }
}

سی شارپ

using System;
using Google.OrTools.ConstraintSolver;

/// <summary>
///   This is a simple CP program.
/// </summary>
public class SimpleCpProgram
{
    public static void Main(String[] args)
    {
        // Instantiate the solver.
        Solver solver = new Solver("CpSimple");

        // Create the variables.
        const long numVals = 3;
        IntVar x = solver.MakeIntVar(0, numVals - 1, "x");
        IntVar y = solver.MakeIntVar(0, numVals - 1, "y");
        IntVar z = solver.MakeIntVar(0, numVals - 1, "z");

        // Constraint 0: x != y..
        solver.Add(solver.MakeAllDifferent(new IntVar[] { x, y }));
        Console.WriteLine($"Number of constraints: {solver.Constraints()}");

        // Solve the problem.
        DecisionBuilder db =
            solver.MakePhase(new IntVar[] { x, y, z }, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE);

        // Print solution on console.
        int count = 0;
        solver.NewSearch(db);
        while (solver.NextSolution())
        {
            ++count;
            Console.WriteLine($"Solution: {count}\n x={x.Value()} y={y.Value()} z={z.Value()}");
        }
        solver.EndSearch();
        Console.WriteLine($"Number of solutions found: {solver.Solutions()}");

        Console.WriteLine("Advanced usage:");
        Console.WriteLine($"Problem solved in {solver.WallTime()}ms");
        Console.WriteLine($"Memory usage: {Solver.MemoryUsage()}bytes");
    }
}

تصمیم ساز

ورودی اصلی حل‌کننده CP اصلی، تصمیم‌ساز است که شامل متغیرهای مسئله است و گزینه‌هایی را برای حل‌کننده تنظیم می‌کند.

مثال کد در بخش قبل یک تصمیم ساز با استفاده از روش Phase (مرتبط با روش C++ MakePhase ) ایجاد می کند.

اصطلاح فاز به مرحله ای از جستجو اشاره دارد. در این مثال ساده، فقط یک فاز وجود دارد، اما برای مسائل پیچیده‌تر، تصمیم‌ساز می‌تواند بیش از یک فاز داشته باشد، به طوری که حل‌کننده می‌تواند استراتژی‌های جستجوی مختلفی را از یک فاز به فاز دیگر به کار گیرد.

روش Phase دارای سه پارامتر ورودی است:

• vars - آرایه ای حاوی متغیرهای مسئله، که در این مورد [x, y, z] است.
• IntVarStrategy - قانون انتخاب متغیر غیر محدود بعدی برای اختصاص یک مقدار. در اینجا، کد از پیش‌فرض CHOOSE_FIRST_UNBOUND استفاده می‌کند، به این معنی که در هر مرحله، حل‌کننده اولین متغیر غیرقابل‌بند را به ترتیبی که در آرایه متغیر ارسال شده به روش Phase رخ می‌دهد، انتخاب می‌کند.
• IntValueStrategy - قانون انتخاب مقدار بعدی برای تخصیص به یک متغیر. در اینجا کد از ASSIGN_MIN_VALUE پیش‌فرض استفاده می‌کند که کوچک‌ترین مقداری را که قبلاً برای متغیر امتحان نشده انتخاب می‌کند. این مقادیر را به ترتیب افزایشی اختصاص می دهد. گزینه دیگر ASSIGN_MAX_VALUE است، در این صورت حل کننده مقادیر را به ترتیب کاهش می دهد.