C++ এর জন্য OR-Tools দিয়ে শুরু করুন

নিম্নলিখিত বিভাগগুলি আপনাকে C++ সহ OR-Tools দিয়ে শুরু করবে:

একটি অপ্টিমাইজেশান সমস্যা কি?

অপ্টিমাইজেশনের লক্ষ্য হল সম্ভাব্য সমাধানের একটি বড় সেটের মধ্যে একটি সমস্যার সর্বোত্তম সমাধান খুঁজে বের করা। (কখনও কখনও আপনি কোনও সম্ভাব্য সমাধান খুঁজে পেয়ে সন্তুষ্ট হবেন; OR-Toolsও এটি করতে পারে।)

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

সমস্ত অপ্টিমাইজেশান সমস্যার মতো, এই সমস্যাটির নিম্নলিখিত উপাদান রয়েছে:

  • উদ্দেশ্য —আপনি যে পরিমাণ অপ্টিমাইজ করতে চান। উপরের উদাহরণে, উদ্দেশ্য হল খরচ কমানো। একটি অপ্টিমাইজেশান সমস্যা সেট আপ করতে, আপনাকে একটি ফাংশন সংজ্ঞায়িত করতে হবে যা সম্ভাব্য সমাধানের জন্য উদ্দেশ্যের মান গণনা করে। একে বলা হয় উদ্দেশ্যমূলক ফাংশন । পূর্ববর্তী উদাহরণে, উদ্দেশ্য ফাংশন প্যাকেজ এবং রুটগুলির যে কোনও অ্যাসাইনমেন্টের মোট খরচ গণনা করবে।

    একটি সর্বোত্তম সমাধান হল একটি যার জন্য উদ্দেশ্য ফাংশনের মান সর্বোত্তম। ("সেরা" সর্বোচ্চ বা সর্বনিম্ন হতে পারে।)

  • সীমাবদ্ধতা - সমস্যার নির্দিষ্ট প্রয়োজনীয়তার উপর ভিত্তি করে সম্ভাব্য সমাধানের সেটের উপর সীমাবদ্ধতা। উদাহরণস্বরূপ, যদি শিপিং কোম্পানি ট্রাকগুলিতে একটি প্রদত্ত ওজনের উপরে প্যাকেজগুলি বরাদ্দ করতে না পারে তবে এটি সমাধানগুলির উপর একটি সীমাবদ্ধতা আরোপ করবে।

    একটি সম্ভাব্য সমাধান হল এমন একটি যা সমস্যার জন্য প্রদত্ত সমস্ত সীমাবদ্ধতাকে সন্তুষ্ট করে, অগত্যা সর্বোত্তম না হয়ে।

একটি অপ্টিমাইজেশান সমস্যা সমাধানের প্রথম ধাপ হল উদ্দেশ্য এবং সীমাবদ্ধতা চিহ্নিত করা।

C++ এ একটি অপ্টিমাইজেশান সমস্যা সমাধান করা

এর পরে, আমরা একটি অপ্টিমাইজেশান সমস্যার একটি উদাহরণ দিই, এবং এটিকে কীভাবে সেট আপ করতে হয় এবং C++ এ সমাধান করতে হয় তা দেখাই।

একটি লিনিয়ার অপ্টিমাইজেশান উদাহরণ

অপ্টিমাইজেশানের প্রাচীনতম এবং সর্বাধিক ব্যবহৃত ক্ষেত্রগুলির মধ্যে একটি হল লিনিয়ার অপ্টিমাইজেশান (বা লিনিয়ার প্রোগ্রামিং ), যেখানে উদ্দেশ্য ফাংশন এবং সীমাবদ্ধতাগুলি রৈখিক অভিব্যক্তি হিসাবে লেখা যেতে পারে। এখানে এই ধরনের সমস্যার একটি সহজ উদাহরণ।

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

  1. 0 ≤ x ≤ 1
  2. 0 ≤ y ≤ 2
  3. x + y ≤ 2

এই উদাহরণে উদ্দেশ্য ফাংশন হল 3x + y । উদ্দেশ্য ফাংশন এবং সীমাবদ্ধতা উভয়ই রৈখিক অভিব্যক্তি দ্বারা দেওয়া হয়, যা এটিকে একটি রৈখিক সমস্যা করে তোলে।

সমস্যা সমাধানের প্রধান পদক্ষেপ

প্রতিটি ভাষার জন্য, একটি সমস্যা সেট আপ এবং সমাধানের প্রাথমিক ধাপগুলি একই:

  1. প্রয়োজনীয় লাইব্রেরি আমদানি করুন,
  2. সমাধানকারী ঘোষণা করুন,
  3. ভেরিয়েবল তৈরি করুন,
  4. সীমাবদ্ধতা সংজ্ঞায়িত করুন,
  5. উদ্দেশ্য ফাংশন সংজ্ঞায়িত করুন,
  6. সমাধানকারীকে আহ্বান করুন এবং
  7. ফলাফল প্রদর্শন করুন।

C++ প্রোগ্রাম

এই বিভাগটি একটি C++ প্রোগ্রামের মাধ্যমে চলে যা সেট আপ করে এবং সমস্যার সমাধান করে।

এখানে পদক্ষেপগুলি রয়েছে:

  • প্রয়োজনীয় লাইব্রেরি আমদানি করুন। 
    #include <cstdlib>
#include <memory>

#include "absl/flags/flag.h"
#include "absl/log/flags.h"
#include "ortools/base/init_google.h"
#include "ortools/base/logging.h"
#include "ortools/init/init.h"
#include "ortools/linear_solver/linear_solver.h"
  • সমাধানকারী ঘোষণা করুন।
    // Create the linear solver with the GLOP backend.
std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("GLOP"));
if (!solver) {
  LOG(WARNING) << "Could not create solver GLOP";
  return;
}
     MPSolver যেকোন লিনিয়ার প্রোগ্রামিং বা মিশ্র পূর্ণসংখ্যা প্রোগ্রামিং সমস্যা সমাধানের জন্য একটি মোড়ক।
  • ভেরিয়েবল তৈরি করুন। 
    // Create the variables x and y.
MPVariable* const x = solver->MakeNumVar(0.0, 1, "x");
MPVariable* const y = solver->MakeNumVar(0.0, 2, "y");

LOG(INFO) << "Number of variables = " << solver->NumVariables();
  • সীমাবদ্ধতা সংজ্ঞায়িত করুন। প্রথম দুটি সীমাবদ্ধতা, 0 ≤ x ≤ 1 এবং 0 ≤ y ≤ 2 , ভেরিয়েবলের সংজ্ঞা দ্বারা ইতিমধ্যেই সেট করা আছে। নিম্নলিখিত কোড x + y ≤ 2 সীমাবদ্ধতা সংজ্ঞায়িত করে:
    // Create a linear constraint, x + y <= 2.
const double infinity = solver->infinity();
MPConstraint* const ct = solver->MakeRowConstraint(-infinity, 2.0, "ct");
ct->SetCoefficient(x, 1);
ct->SetCoefficient(y, 1);

LOG(INFO) << "Number of constraints = " << solver->NumConstraints();
     SetCoefficient পদ্ধতিটি সীমাবদ্ধতার জন্য এক্সপ্রেশনে x এবং y এর সহগ নির্ধারণ করে।
  • উদ্দেশ্য ফাংশন সংজ্ঞায়িত করুন।
    // Create the objective function, 3 * x + y.
MPObjective* const objective = solver->MutableObjective();
objective->SetCoefficient(x, 3);
objective->SetCoefficient(y, 1);
objective->SetMaximization();
     SetMaximization পদ্ধতি এটিকে সর্বাধিকীকরণ সমস্যা বলে ঘোষণা করে।
  • সমাধানকারীকে আহ্বান করুন এবং ফলাফলগুলি প্রদর্শন করুন। 
    LOG(INFO) << "Solving with " << solver->SolverVersion();
const MPSolver::ResultStatus result_status = solver->Solve();
// Check that the problem has an optimal solution.
LOG(INFO) << "Status: " << result_status;
if (result_status != MPSolver::OPTIMAL) {
  LOG(INFO) << "The problem does not have an optimal solution!";
  if (result_status == MPSolver::FEASIBLE) {
    LOG(INFO) << "A potentially suboptimal solution was found";
  } else {
    LOG(WARNING) << "The solver could not solve the problem.";
    return;
  }
}

LOG(INFO) << "Solution:";
LOG(INFO) << "Objective value = " << objective->Value();
LOG(INFO) << "x = " << x->solution_value();
LOG(INFO) << "y = " << y->solution_value();

সম্পূর্ণ প্রোগ্রাম

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

// Minimal example to call the GLOP solver.
#include <cstdlib>
#include <memory>

#include "absl/flags/flag.h"
#include "absl/log/flags.h"
#include "ortools/base/init_google.h"
#include "ortools/base/logging.h"
#include "ortools/init/init.h"
#include "ortools/linear_solver/linear_solver.h"

namespace operations_research {
void BasicExample() {
  LOG(INFO) << "Google OR-Tools version : " << OrToolsVersion::VersionString();

  // Create the linear solver with the GLOP backend.
  std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("GLOP"));
  if (!solver) {
    LOG(WARNING) << "Could not create solver GLOP";
    return;
  }

  // Create the variables x and y.
  MPVariable* const x = solver->MakeNumVar(0.0, 1, "x");
  MPVariable* const y = solver->MakeNumVar(0.0, 2, "y");

  LOG(INFO) << "Number of variables = " << solver->NumVariables();

  // Create a linear constraint, x + y <= 2.
  const double infinity = solver->infinity();
  MPConstraint* const ct = solver->MakeRowConstraint(-infinity, 2.0, "ct");
  ct->SetCoefficient(x, 1);
  ct->SetCoefficient(y, 1);

  LOG(INFO) << "Number of constraints = " << solver->NumConstraints();

  // Create the objective function, 3 * x + y.
  MPObjective* const objective = solver->MutableObjective();
  objective->SetCoefficient(x, 3);
  objective->SetCoefficient(y, 1);
  objective->SetMaximization();

  LOG(INFO) << "Solving with " << solver->SolverVersion();
  const MPSolver::ResultStatus result_status = solver->Solve();

  // Check that the problem has an optimal solution.
  LOG(INFO) << "Status: " << result_status;
  if (result_status != MPSolver::OPTIMAL) {
    LOG(INFO) << "The problem does not have an optimal solution!";
    if (result_status == MPSolver::FEASIBLE) {
      LOG(INFO) << "A potentially suboptimal solution was found";
    } else {
      LOG(WARNING) << "The solver could not solve the problem.";
      return;
    }
  }

  LOG(INFO) << "Solution:";
  LOG(INFO) << "Objective value = " << objective->Value();
  LOG(INFO) << "x = " << x->solution_value();
  LOG(INFO) << "y = " << y->solution_value();

  LOG(INFO) << "Advanced usage:";
  LOG(INFO) << "Problem solved in " << solver->wall_time() << " milliseconds";
  LOG(INFO) << "Problem solved in " << solver->iterations() << " iterations";
}
}  // namespace operations_research

int main(int argc, char* argv[]) {
  InitGoogle(argv[0], &argc, &argv, true);
  absl::SetFlag(&FLAGS_stderrthreshold, 0);
  operations_research::BasicExample();
  return EXIT_SUCCESS;
}

C++ প্রোগ্রাম চালানো হচ্ছে

আপনি উপরের প্রোগ্রামটি নিম্নরূপ চালাতে পারেন:

  1. উপরের কোডটি কপি করে নতুন ফাইলে পেস্ট করুন এবং program.cc হিসেবে সংরক্ষণ করুন।
  2. ডিরেক্টরির উপরের স্তরে একটি কমান্ড উইন্ডো খুলুন যেখানে আপনি OR-Tools ইনস্টল করেছেন এবং লিখুন:
    make run SOURCE=relative/path/to/program.cc
     যেখানে relative/path/to/ হল সেই ডিরেক্টরির পথ যেখানে আপনি প্রোগ্রামটি সংরক্ষণ করেছেন।

প্রোগ্রামটি x এবং y এর মানগুলি প্রদান করে যা উদ্দেশ্য ফাংশনটিকে সর্বাধিক করে তোলে:

Solution:
x =  1.0
y =  1.0

প্রোগ্রামটি চালানো ছাড়াই কম্পাইল করতে, লিখুন: 

make build SOURCE=relative/path/to/program.cc

অপট মোডে কম্পাইল করা হচ্ছে

O3 মোডে কম্পাইল করতে: 

make DEBUG='-O3' all

C++ এক্সিকিউটেবল চালানো হচ্ছে

আপনি যখন make এর সাথে একটি OR-Tools C++ প্রোগ্রাম কম্পাইল করেন, তখন এক্সিকিউটেবলটি bin ডিরেক্টরিতে তৈরি হয়। আপনি নিম্নরূপ উদাহরণ প্রোগ্রামের জন্য এক্সিকিউটেবল চালাতে পারেন: 

cd bin && ./program

আপনি যদি প্রোগ্রামে পরিবর্তন করেন, তাহলে উপরে দেখানো হিসাবে আপনাকে এটি পুনরায় কম্পাইল করতে হবে।

আরও C++ উদাহরণ

আরও C++ উদাহরণের জন্য যা বিভিন্ন ধরনের অপ্টিমাইজেশান সমস্যার সমাধান কিভাবে ব্যাখ্যা করে, উদাহরণ দেখুন।

আপনি যে ধরনের সমস্যার সমাধান করতে চান তা চিহ্নিত করা

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

আপনি একটি অপ্টিমাইজেশান সমস্যা সমাধানের জন্য একটি প্রোগ্রাম লেখা শুরু করার আগে, আপনি কোন ধরনের সমস্যার সাথে কাজ করছেন তা চিহ্নিত করতে হবে, এবং তারপর একটি উপযুক্ত সমাধানকারী বেছে নিন - একটি সর্বোত্তম সমাধান খোঁজার জন্য একটি অ্যালগরিদম৷

নীচে আপনি OR-Tools যে ধরনের সমস্যার সমাধান করে তার একটি সংক্ষিপ্ত ওভারভিউ পাবেন এবং এই নির্দেশিকায় অংশগুলির লিঙ্কগুলি পাবেন যা ব্যাখ্যা করে যে কীভাবে প্রতিটি সমস্যার সমাধান করতে হয়।

রৈখিক অপ্টিমাইজেশান

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

এই ধরনের সমস্যার জন্য OR-Tools-এ প্রাথমিক সমাধানকারী হল লিনিয়ার অপ্টিমাইজেশান সলভার, যা আসলে তৃতীয় পক্ষের লাইব্রেরি সহ রৈখিক এবং মিশ্র-পূর্ণসংখ্যা অপ্টিমাইজেশনের জন্য বিভিন্ন লাইব্রেরির জন্য একটি মোড়ক।

লিনিয়ার অপ্টিমাইজেশান সম্পর্কে আরও জানুন

মিশ্র-পূর্ণসংখ্যা অপ্টিমাইজেশান

একটি মিশ্র পূর্ণসংখ্যা অপ্টিমাইজেশান সমস্যা হল একটি যেখানে কিছু বা সমস্ত ভেরিয়েবল পূর্ণসংখ্যা হতে হবে। একটি উদাহরণ হ'ল অ্যাসাইনমেন্ট সমস্যা , যেখানে কর্মীদের একটি গ্রুপকে কাজের একটি সেটের জন্য বরাদ্দ করা দরকার। প্রতিটি কর্মী এবং টাস্কের জন্য, আপনি একটি ভেরিয়েবল সংজ্ঞায়িত করেন যার মান 1 যদি প্রদত্ত কর্মীকে প্রদত্ত কাজের জন্য বরাদ্দ করা হয় এবং অন্যথায় 0। এই ক্ষেত্রে, ভেরিয়েবল শুধুমাত্র 0 বা 1 মান নিতে পারে।

মিশ্র-পূর্ণসংখ্যা অপ্টিমাইজেশান সম্পর্কে আরও জানুন

সীমাবদ্ধতা অপ্টিমাইজেশান

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

সীমাবদ্ধতা অপ্টিমাইজেশান সম্পর্কে আরও জানুন

অ্যাসাইনমেন্ট

অ্যাসাইনমেন্ট সমস্যাগুলির মধ্যে একদল এজেন্টকে (বলুন, কর্মী বা মেশিন) কাজের একটি সেটের জন্য বরাদ্দ করা জড়িত, যেখানে প্রতিটি এজেন্টকে একটি নির্দিষ্ট কাজের জন্য নির্ধারিত খরচ রয়েছে। সমস্যা হল সর্বনিম্ন মোট খরচ সহ অ্যাসাইনমেন্ট খুঁজে বের করা। অ্যাসাইনমেন্ট সমস্যা আসলে নেটওয়ার্ক প্রবাহ সমস্যার একটি বিশেষ ক্ষেত্রে।

অ্যাসাইনমেন্ট সম্পর্কে আরও জানুন

প্যাকিং

বিন প্যাকিং হল বিভিন্ন আকারের বস্তুর সেটকে বিভিন্ন ক্ষমতা সহ পাত্রে প্যাক করার সমস্যা। লক্ষ্য হল যতটা সম্ভব বস্তু প্যাক করা, কন্টেইনারগুলির ক্ষমতা সাপেক্ষে। এর একটি বিশেষ কেস হ'ল ন্যাপস্যাক সমস্যা , যেখানে কেবল একটি ধারক রয়েছে।

বিন প্যাকিং সম্পর্কে আরও জানুন

সময়সূচী

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

সময়সূচী সম্পর্কে আরও জানুন

রাউটিং

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

রাউটিং সম্পর্কে আরও জানুন

নেটওয়ার্ক প্রবাহিত হয়

অনেক অপ্টিমাইজেশান সমস্যা নোড এবং তাদের মধ্যে নির্দেশিত আর্ক সমন্বিত একটি নির্দেশিত গ্রাফ দ্বারা প্রতিনিধিত্ব করা যেতে পারে। উদাহরণস্বরূপ, পরিবহন সমস্যা, যেখানে পণ্যগুলি একটি রেলওয়ে নেটওয়ার্ক জুড়ে পাঠানো হয়, একটি গ্রাফ দ্বারা উপস্থাপন করা যেতে পারে যেখানে আর্কগুলি রেললাইন এবং নোডগুলি বিতরণ কেন্দ্র।

সর্বাধিক প্রবাহের সমস্যায় , প্রতিটি চাপের সর্বোচ্চ ক্ষমতা থাকে যা এটি জুড়ে পরিবহন করা যায়। সমস্যাটি হ'ল প্রতিটি চাপ জুড়ে পণ্যের পরিমাণ নির্ধারণ করা যাতে পরিবহন করা মোট পরিমাণ যতটা সম্ভব বড় হয়।

নেটওয়ার্ক প্রবাহ সম্পর্কে আরও জানুন