এই পৃষ্ঠাটি Cloud Translation API অনুবাদ করেছে।

একটি CP সমস্যা সমাধান

পূর্ববর্তী বিভাগে দেখানো হয়েছে কিভাবে একটি CP সমস্যার সব সমাধান খুঁজে বের করতে হয়। পরবর্তী, আমরা দেখাব কিভাবে একটি সর্বোত্তম সমাধান খুঁজে বের করতে হয়। একটি উদাহরণ হিসাবে, আমরা নিম্নলিখিত অপ্টিমাইজেশন সমস্যার সমাধান করব।

নিম্নলিখিত সীমাবদ্ধতা সাপেক্ষে 2 x + 2 y + 3 z সর্বাধিক করুন:

x + ⁷ ⁄ ₂ y + ³ ⁄ ₂ z	≤	25
3 x - 5 y + 7 z	≤	45
5 x + 2 y - 6 z	≤	37
x , y , z	≥	0
x , y , z পূর্ণসংখ্যা

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

CP-SAT সমাধানকারী ব্যবহার করে সমাধান

নিম্নলিখিত বিভাগগুলি একটি পাইথন প্রোগ্রাম উপস্থাপন করে যা CP-SAT সমাধানকারী ব্যবহার করে সমস্যার সমাধান করে।

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

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

পাইথন

from ortools.sat.python import cp_model

সি++

#include <stdint.h>
#include <stdlib.h>

#include <algorithm>

#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"
#include "ortools/util/sorted_interval_list.h"

জাভা

import static java.util.Arrays.stream;

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.IntVar;
import com.google.ortools.sat.LinearExpr;

সি#

using System;
using System.Linq;
using Google.OrTools.Sat;

মডেল ঘোষণা করুন

নিম্নলিখিত কোডটি সমস্যার জন্য মডেল ঘোষণা করে।

পাইথন

model = cp_model.CpModel()

সি++

CpModelBuilder cp_model;

জাভা

CpModel model = new CpModel();

সি#

CpModel model = new CpModel();

ভেরিয়েবল তৈরি করুন

নিম্নলিখিত কোডটি সমস্যার জন্য ভেরিয়েবল তৈরি করে।

পাইথন

var_upper_bound = max(50, 45, 37)
x = model.new_int_var(0, var_upper_bound, "x")
y = model.new_int_var(0, var_upper_bound, "y")
z = model.new_int_var(0, var_upper_bound, "z")

সি++

int64_t var_upper_bound = std::max({50, 45, 37});
const Domain domain(0, var_upper_bound);
const IntVar x = cp_model.NewIntVar(domain).WithName("x");
const IntVar y = cp_model.NewIntVar(domain).WithName("y");
const IntVar z = cp_model.NewIntVar(domain).WithName("z");

জাভা

int varUpperBound = stream(new int[] {50, 45, 37}).max().getAsInt();

IntVar x = model.newIntVar(0, varUpperBound, "x");
IntVar y = model.newIntVar(0, varUpperBound, "y");
IntVar z = model.newIntVar(0, varUpperBound, "z");

সি#

int varUpperBound = new int[] { 50, 45, 37 }.Max();

IntVar x = model.NewIntVar(0, varUpperBound, "x");
IntVar y = model.NewIntVar(0, varUpperBound, "y");
IntVar z = model.NewIntVar(0, varUpperBound, "z");

সীমাবদ্ধতা সংজ্ঞায়িত করুন

প্রথম বাধা থেকে,

x + ⁷ ⁄ ₂ y + ³ ⁄ ₂ z

≤

অ-পূর্ণসংখ্যা সহগ আছে, আপনাকে প্রথমে সম্পূর্ণ সীমাবদ্ধতাকে যথেষ্ট বড় পূর্ণসংখ্যা দ্বারা গুণ করতে হবে যাতে সহগগুলিকে পূর্ণসংখ্যাতে রূপান্তর করা যায়। এই ক্ষেত্রে, আপনি 2 দ্বারা গুণ করতে পারেন, যার ফলে নতুন সীমাবদ্ধতা দেখা দেয়

2 x + 7 y + 3 z

≤

এটি সমস্যাটি পরিবর্তন করে না, যেহেতু মূল সীমাবদ্ধতার ঠিক একই সমাধান রয়েছে রূপান্তরিত সীমাবদ্ধতার মতো।

নিম্নলিখিত কোডটি সমস্যার জন্য তিনটি রৈখিক সীমাবদ্ধতা সংজ্ঞায়িত করে:

পাইথন

model.add(2 * x + 7 * y + 3 * z <= 50)
model.add(3 * x - 5 * y + 7 * z <= 45)
model.add(5 * x + 2 * y - 6 * z <= 37)

সি++

cp_model.AddLessOrEqual(2 * x + 7 * y + 3 * z, 50);
cp_model.AddLessOrEqual(3 * x - 5 * y + 7 * z, 45);
cp_model.AddLessOrEqual(5 * x + 2 * y - 6 * z, 37);

জাভা

model.addLessOrEqual(LinearExpr.weightedSum(new IntVar[] {x, y, z}, new long[] {2, 7, 3}), 50);
model.addLessOrEqual(LinearExpr.weightedSum(new IntVar[] {x, y, z}, new long[] {3, -5, 7}), 45);
model.addLessOrEqual(LinearExpr.weightedSum(new IntVar[] {x, y, z}, new long[] {5, 2, -6}), 37);

সি#

model.Add(2 * x + 7 * y + 3 * z <= 50);
model.Add(3 * x - 5 * y + 7 * z <= 45);
model.Add(5 * x + 2 * y - 6 * z <= 37);

উদ্দেশ্য ফাংশন সংজ্ঞায়িত করুন

নিম্নলিখিত কোডটি সমস্যার জন্য উদ্দেশ্য ফাংশন সংজ্ঞায়িত করে এবং এটিকে সর্বাধিকীকরণ সমস্যা হিসাবে ঘোষণা করে:

পাইথন

model.maximize(2 * x + 2 * y + 3 * z)

সি++

cp_model.Maximize(2 * x + 2 * y + 3 * z);

জাভা

model.maximize(LinearExpr.weightedSum(new IntVar[] {x, y, z}, new long[] {2, 2, 3}));

সি#

model.Maximize(2 * x + 2 * y + 3 * z);

সমাধানকারীকে কল করুন

নিম্নলিখিত কোড সমাধানকারী কল.

পাইথন

solver = cp_model.CpSolver()
status = solver.solve(model)

সি++

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

সমাধান প্রদর্শন করুন

নিম্নলিখিত কোড ফলাফল প্রদর্শন করে.

পাইথন

if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print(f"Maximum of objective function: {solver.objective_value}\n")
    print(f"x = {solver.value(x)}")
    print(f"y = {solver.value(y)}")
    print(f"z = {solver.value(z)}")
else:
    print("No solution found.")

সি++

if (response.status() == CpSolverStatus::OPTIMAL ||
    response.status() == CpSolverStatus::FEASIBLE) {
  // Get the value of x in the solution.
  LOG(INFO) << "Maximum of objective function: "
            << response.objective_value();
  LOG(INFO) << "x = " << SolutionIntegerValue(response, x);
  LOG(INFO) << "y = " << SolutionIntegerValue(response, y);
  LOG(INFO) << "z = " << SolutionIntegerValue(response, z);
} else {
  LOG(INFO) << "No solution found.";
}

জাভা

if (status == CpSolverStatus.OPTIMAL || status == CpSolverStatus.FEASIBLE) {
  System.out.printf("Maximum of objective function: %f%n", solver.objectiveValue());
  System.out.println("x = " + solver.value(x));
  System.out.println("y = " + solver.value(y));
  System.out.println("z = " + solver.value(z));
} else {
  System.out.println("No solution found.");
}

সি#

if (status == CpSolverStatus.Optimal || status == CpSolverStatus.Feasible)
{
    Console.WriteLine($"Maximum of objective function: {solver.ObjectiveValue}");
    Console.WriteLine("x = " + solver.Value(x));
    Console.WriteLine("y = " + solver.Value(y));
    Console.WriteLine("z = " + solver.Value(z));
}
else
{
    Console.WriteLine("No solution found.");
}

আউটপুট নীচে দেখানো হয়েছে:

Maximum of objective function: 35

x value:  7
y value:  3
z value:  5

পুরো প্রোগ্রাম

সম্পূর্ণ প্রোগ্রাম নীচে দেখানো হয়.

পাইথন

"""Simple solve."""
from ortools.sat.python import cp_model


def main() -> None:
    """Minimal CP-SAT example to showcase calling the solver."""
    # Creates the model.
    model = cp_model.CpModel()

    # Creates the variables.
    var_upper_bound = max(50, 45, 37)
    x = model.new_int_var(0, var_upper_bound, "x")
    y = model.new_int_var(0, var_upper_bound, "y")
    z = model.new_int_var(0, var_upper_bound, "z")

    # Creates the constraints.
    model.add(2 * x + 7 * y + 3 * z <= 50)
    model.add(3 * x - 5 * y + 7 * z <= 45)
    model.add(5 * x + 2 * y - 6 * z <= 37)

    model.maximize(2 * x + 2 * y + 3 * z)

    # Creates a solver and solves the model.
    solver = cp_model.CpSolver()
    status = solver.solve(model)

    if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
        print(f"Maximum of objective function: {solver.objective_value}\n")
        print(f"x = {solver.value(x)}")
        print(f"y = {solver.value(y)}")
        print(f"z = {solver.value(z)}")
    else:
        print("No solution found.")

    # Statistics.
    print("\nStatistics")
    print(f"  status   : {solver.status_name(status)}")
    print(f"  conflicts: {solver.num_conflicts}")
    print(f"  branches : {solver.num_branches}")
    print(f"  wall time: {solver.wall_time} s")


if __name__ == "__main__":
    main()

সি++

#include <stdint.h>
#include <stdlib.h>

#include <algorithm>

#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"
#include "ortools/util/sorted_interval_list.h"

namespace operations_research {
namespace sat {

void CpSatExample() {
  CpModelBuilder cp_model;

  int64_t var_upper_bound = std::max({50, 45, 37});
  const Domain domain(0, var_upper_bound);
  const IntVar x = cp_model.NewIntVar(domain).WithName("x");
  const IntVar y = cp_model.NewIntVar(domain).WithName("y");
  const IntVar z = cp_model.NewIntVar(domain).WithName("z");

  cp_model.AddLessOrEqual(2 * x + 7 * y + 3 * z, 50);
  cp_model.AddLessOrEqual(3 * x - 5 * y + 7 * z, 45);
  cp_model.AddLessOrEqual(5 * x + 2 * y - 6 * z, 37);

  cp_model.Maximize(2 * x + 2 * y + 3 * z);

  // Solving part.
  const CpSolverResponse response = Solve(cp_model.Build());

  if (response.status() == CpSolverStatus::OPTIMAL ||
      response.status() == CpSolverStatus::FEASIBLE) {
    // Get the value of x in the solution.
    LOG(INFO) << "Maximum of objective function: "
              << response.objective_value();
    LOG(INFO) << "x = " << SolutionIntegerValue(response, x);
    LOG(INFO) << "y = " << SolutionIntegerValue(response, y);
    LOG(INFO) << "z = " << SolutionIntegerValue(response, z);
  } else {
    LOG(INFO) << "No solution found.";
  }

  // Statistics.
  LOG(INFO) << "Statistics";
  LOG(INFO) << CpSolverResponseStats(response);
}

}  // namespace sat
}  // namespace operations_research

int main() {
  operations_research::sat::CpSatExample();
  return EXIT_SUCCESS;
}

জাভা

package com.google.ortools.sat.samples;
import static java.util.Arrays.stream;

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.IntVar;
import com.google.ortools.sat.LinearExpr;

/** Minimal CP-SAT example to showcase calling the solver. */
public final class CpSatExample {
  public static void main(String[] args) {
    Loader.loadNativeLibraries();
    // Create the model.
    CpModel model = new CpModel();

    // Create the variables.
    int varUpperBound = stream(new int[] {50, 45, 37}).max().getAsInt();

    IntVar x = model.newIntVar(0, varUpperBound, "x");
    IntVar y = model.newIntVar(0, varUpperBound, "y");
    IntVar z = model.newIntVar(0, varUpperBound, "z");

    // Create the constraints.
    model.addLessOrEqual(LinearExpr.weightedSum(new IntVar[] {x, y, z}, new long[] {2, 7, 3}), 50);
    model.addLessOrEqual(LinearExpr.weightedSum(new IntVar[] {x, y, z}, new long[] {3, -5, 7}), 45);
    model.addLessOrEqual(LinearExpr.weightedSum(new IntVar[] {x, y, z}, new long[] {5, 2, -6}), 37);

    model.maximize(LinearExpr.weightedSum(new IntVar[] {x, y, z}, new long[] {2, 2, 3}));

    // Create a solver and solve the model.
    CpSolver solver = new CpSolver();
    CpSolverStatus status = solver.solve(model);

    if (status == CpSolverStatus.OPTIMAL || status == CpSolverStatus.FEASIBLE) {
      System.out.printf("Maximum of objective function: %f%n", solver.objectiveValue());
      System.out.println("x = " + solver.value(x));
      System.out.println("y = " + solver.value(y));
      System.out.println("z = " + solver.value(z));
    } else {
      System.out.println("No solution found.");
    }

    // Statistics.
    System.out.println("Statistics");
    System.out.printf("  conflicts: %d%n", solver.numConflicts());
    System.out.printf("  branches : %d%n", solver.numBranches());
    System.out.printf("  wall time: %f s%n", solver.wallTime());
  }

  private CpSatExample() {}
}

সি#

using System;
using System.Linq;
using Google.OrTools.Sat;

public class CpSatExample
{
    static void Main()
    {
        // Creates the model.
        CpModel model = new CpModel();

        // Creates the variables.
        int varUpperBound = new int[] { 50, 45, 37 }.Max();

        IntVar x = model.NewIntVar(0, varUpperBound, "x");
        IntVar y = model.NewIntVar(0, varUpperBound, "y");
        IntVar z = model.NewIntVar(0, varUpperBound, "z");

        // Creates the constraints.
        model.Add(2 * x + 7 * y + 3 * z <= 50);
        model.Add(3 * x - 5 * y + 7 * z <= 45);
        model.Add(5 * x + 2 * y - 6 * z <= 37);

        model.Maximize(2 * x + 2 * y + 3 * z);

        // Creates a solver and solves the model.
        CpSolver solver = new CpSolver();
        CpSolverStatus status = solver.Solve(model);

        if (status == CpSolverStatus.Optimal || status == CpSolverStatus.Feasible)
        {
            Console.WriteLine($"Maximum of objective function: {solver.ObjectiveValue}");
            Console.WriteLine("x = " + solver.Value(x));
            Console.WriteLine("y = " + solver.Value(y));
            Console.WriteLine("z = " + solver.Value(z));
        }
        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");
    }
}