আসল সিপি সলভার

এই বিভাগটি মূল সীমাবদ্ধতা প্রোগ্রামিং সমাধানকারীকে বর্ণনা করে, যা উচ্চতর CP-SAT সমাধানকারী দ্বারা প্রতিস্থাপিত হয়েছে।

দ্রষ্টব্য: আমরা দৃঢ়ভাবে CP-SAT সলভার ব্যবহার করার পরামর্শ দিই আসল CP সলভারের পরিবর্তে।

নিম্নলিখিত বিভাগগুলি বর্ণনা করে কিভাবে CP-SAT বিভাগে বর্ণিত উদাহরণটি সমাধান করা যায়, এবার মূল CP সমাধানকারী ব্যবহার করে। আপনি যদি মূল CP সল্ভার ব্যবহার করার জন্য জোর দেন, আপনি API রেফারেন্স ব্রাউজ করতে পারেন। মনে রাখবেন মূল CP সল্ভার হল রাউটিং লাইব্রেরির ভিত্তি, এবং এর API একটি রাউটিং মডেল কাস্টমাইজ করার জন্য প্রয়োজনীয় হতে পারে।

লাইব্রেরি আমদানি করুন

নিম্নলিখিত কোড প্রয়োজনীয় লাইব্রেরি আমদানি করে।

পাইথন

from ortools.constraint_solver import pywrapcp

সি++

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

সি++

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

সি++

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 সীমাবদ্ধতা তৈরি করে। x ≠ y

পাইথন

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

সি++

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 = solver.Phase(
    [x, y, z], solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE
)

সি++

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

সি++

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

সি++

#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 , যে ক্ষেত্রে সমাধানকারী ক্রমবর্ধমান ক্রমে মান নির্ধারণ করবে।