C++ के लिए OR-टूल के साथ शुरू करें

नीचे दिए गए सेक्शन से आप C++ के साथ OR-टूल का इस्तेमाल कर पाएंगे:

ऑप्टिमाइज़ेशन समस्या क्या है?

ऑप्टिमाइज़ेशन का मकसद, कई संभावित समाधानों में से किसी समस्या का सबसे अच्छा समाधान ढूंढना होता है. (कभी-कभी आप कोई संभव समाधान ढूंढ लेंगे; OR-टूल ऐसा भी कर सकते हैं.)

यह रही ऑप्टिमाइज़ेशन से जुड़ी एक आम समस्या. मान लीजिए कि एक शिपिंग कंपनी अपने ग्राहकों को ट्रकों के बेड़े का इस्तेमाल करके पैकेज डिलीवर करती है. कंपनी को हर दिन, ट्रक के लिए पैकेज असाइन करने चाहिए. इसके बाद, हर ट्रक के लिए अपना पैकेज डिलीवर करने के लिए, एक रास्ता चुनना चाहिए. पैकेज और रूट के हर संभावित असाइनमेंट का शुल्क लगता है. यह शुल्क, ट्रक तक पहुंचने के लिए तय की गई कुल दूरी और अन्य चीज़ों पर निर्भर करता है. सबसे कम कीमत वाले पैकेज और रूट के असाइनमेंट चुनने में समस्या आती है.

सभी ऑप्टिमाइज़ेशन समस्याओं की तरह, इस समस्या में भी ये एलिमेंट होते हैं:

  • मकसद—वह संख्या जिसे आपको ऑप्टिमाइज़ करना है. ऊपर दिए गए उदाहरण में, मकसद कीमत को कम करना है. ऑप्टिमाइज़ेशन की कोई समस्या सेट अप करने के लिए, आपको एक ऐसा फ़ंक्शन सेट करना होगा जो किसी भी संभावित हल के लिए, मकसद की वैल्यू का पता लगाता हो. इसे मकसद फ़ंक्शन कहा जाता है. पिछले उदाहरण में, मकसद फ़ंक्शन, पैकेज और रूट के किसी भी असाइनमेंट की कुल लागत की गणना करेगा.

    सबसे अच्छा समाधान वह होता है जिसके लिए मकसद फ़ंक्शन की वैल्यू सबसे अच्छी हो. ("सबसे अच्छा" ज़्यादा से ज़्यादा या कम से कम हो सकता है.)

  • सीमाएं—समस्या की खास ज़रूरतों के आधार पर, संभावित समाधानों के सेट पर लगने वाली पाबंदियां. उदाहरण के लिए, अगर शिपिंग कंपनी ट्रक के लिए दिए गए वज़न से ज़्यादा के पैकेज असाइन नहीं कर सकती, तो समाधानों पर रोक लग जाएगी.

    सही हल वह होता है जो समस्या के लिए दी गई सभी सीमाओं को पूरा करता है. हालांकि, यह ज़रूरी नहीं है कि वह सबसे बेहतर हो.

ऑप्टिमाइज़ेशन से जुड़ी समस्या को हल करने का पहला कदम होता है मकसद और सीमाओं को पहचानना.

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 <memory>
#include <ostream>

#include "ortools/linear_solver/linear_solver.h"
  • सॉल्वर का एलान करें. 
    // Create the linear solver with the GLOP backend.
std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("GLOP"));
    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 &leq; x ≤ 1 और 0 &leq; y ≤ 2, पहले ही वैरिएबल की परिभाषाओं के हिसाब से सेट होते हैं. यह कोड, कंस्ट्रेंट x + y &leq; 2 के बारे में बताता है: 
    // Create a linear constraint, 0 <= x + y <= 2.
MPConstraint* const ct = solver->MakeRowConstraint(0.0, 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 तरीके के हिसाब से, यह समस्या बड़ी है.
  • सॉल्वर को शुरू करें और नतीजे दिखाएं. 
    solver->Solve();
LOG(INFO) << "Solution:" << std::endl;
LOG(INFO) << "Objective value = " << objective->Value();
LOG(INFO) << "x = " << x->solution_value();
LOG(INFO) << "y = " << y->solution_value();

प्रोग्राम पूरा करें

पूरा प्रोग्राम नीचे दिखाया गया है.

#include <memory>
#include <ostream>

#include "ortools/linear_solver/linear_solver.h"

namespace operations_research {
void BasicExample() {
  // Create the linear solver with the GLOP backend.
  std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("GLOP"));

  // 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, 0 <= x + y <= 2.
  MPConstraint* const ct = solver->MakeRowConstraint(0.0, 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();

  solver->Solve();

  LOG(INFO) << "Solution:" << std::endl;
  LOG(INFO) << "Objective value = " << objective->Value();
  LOG(INFO) << "x = " << x->solution_value();
  LOG(INFO) << "y = " << y->solution_value();
}
}  // namespace operations_research

int main() {
  operations_research::BasicExample();
  return EXIT_SUCCESS;
}

C++ प्रोग्राम चलाना

ऊपर दिए गए प्रोग्राम को इस तरह चलाया जा सकता है:

  1. ऊपर दिए गए कोड को कॉपी करके नई फ़ाइल में चिपकाएं. इसके बाद, उसे program.cc के तौर पर सेव करें.
  2. जिस डायरेक्ट्री में आपने 'OR-टूल' इंस्टॉल किया है उसके टॉप लेवल पर मौजूद कमांड विंडो खोलें. इसके बाद, यह डालें: 
    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-टूल C++ प्रोग्राम को कंपाइल करने पर, एक्ज़ीक्यूटेबल फ़ाइल bin डायरेक्ट्री में बन जाती है. उदाहरण प्रोग्राम के लिए एक्ज़ीक्यूटेबल को इस तरह चलाया जा सकता है:

cd bin && ./program

अगर प्रोग्राम में बदलाव किए जाते हैं, तो आपको इसे ऊपर दिखाए गए तरीके से फिर से कंपाइल करना होगा.

C++ के ज़्यादा उदाहरण

ऑप्टिमाइज़ेशन से जुड़े अलग-अलग तरह के सवालों को हल करने का तरीका बताने वाले C++ उदाहरणों के लिए, उदाहरण देखें.

उस समस्या की पहचान करना जिसे आपको हल करना है

दुनिया में ऑप्टिमाइज़ेशन की कई तरह की समस्याएं हैं. हर तरह की समस्या का सबसे सही समाधान ढूंढने के लिए, अलग-अलग तरीके और एल्गोरिदम होते हैं.

ऑप्टिमाइज़ेशन की किसी समस्या को हल करने के लिए, प्रोग्राम लिखना शुरू करने से पहले, आपको यह पता लगाना होगा कि किस तरह की समस्या से निपटना है और फिर एक सही सॉल्वर चुनना होगा. यह एल्गोरिदम, सबसे बेहतर समाधान खोजने वाला होता है.

नीचे आपको OR-टूल ज़रिए हल की जाने वाली समस्याओं के बारे में खास जानकारी मिलेगी. साथ ही, इस गाइड में दिए गए सेक्शन के लिंक मिलेंगे, जिनमें समस्या को हल करने का तरीका बताया गया है.

लीनियर ऑप्टिमाइज़ेशन

जैसा कि आपने पिछले सेक्शन में सीखा है, लीनियर ऑप्टिमाइज़ेशन समस्या एक है जिसमें मकसद फ़ंक्शन और कंस्ट्रेंट, वैरिएबल में लीनियर एक्सप्रेशन होते हैं.

इस तरह की समस्या के लिए, OR-टूल में प्राइमरी सॉल्वर लीनियर ऑप्टिमाइज़ेशन सॉल्वर है. यह असल में, लीनियर और मिक्स्ड-इंटीजर ऑप्टिमाइज़ेशन के लिए, कई अलग-अलग लाइब्रेरी के लिए रैपर होता है. इनमें, तीसरे पक्ष की लाइब्रेरी भी शामिल हैं.

लीनियर ऑप्टिमाइज़ेशन के बारे में ज़्यादा जानें

मिश्रित-पूर्णांक ऑप्टिमाइज़ेशन

मिले-जुले पूर्णांक ऑप्टिमाइज़ेशन की समस्या एक ऐसी समस्या है जिसमें कुछ या सभी वैरिएबल का पूर्णांक होना ज़रूरी है. इसका एक उदाहरण असाइनमेंट से जुड़ी समस्या है. इसमें, वर्कर के एक ग्रुप को टास्क के सेट को असाइन किया जाना ज़रूरी होता है. हर वर्कर और टास्क के लिए, आपने एक वैरिएबल तय किया है, जिसका मान 1 है, अगर उस वर्कर को कोई टास्क असाइन किया गया है, नहीं तो 0 होगा. इस मामले में, वैरिएबल सिर्फ़ 0 या 1 वैल्यू पर ही काम कर सकते हैं.

मिले-जुले पूर्णांक ऑप्टिमाइज़ेशन के बारे में ज़्यादा जानें

कंस्ट्रेंट ऑप्टिमाइज़ेशन

कंस्ट्रेंट ऑप्टिमाइज़ेशन या कंस्ट्रेंट प्रोग्रामिंग (सीपी), उम्मीदवारों के एक बहुत बड़े सेट में से ऐसे समाधानों की पहचान करता है जो आसानी से काम कर सकते हैं. यहां समस्या को आर्बिट्रेरी कंस्ट्रेंट के हिसाब से तय किया जा सकता है. सीपी, ऑप्टिमाइज़ेशन (सबसे बेहतर समाधान ढूंढने) के बजाय संभावना (सही समाधान खोजना) पर आधारित है और मकसद फ़ंक्शन के बजाय कंस्ट्रेंट और वैरिएबल पर फ़ोकस करता है. हालांकि, सीपी का इस्तेमाल ऑप्टिमाइज़ेशन से जुड़ी समस्याओं को हल करने के लिए किया जा सकता है. इसके लिए, सिर्फ़ मकसद फ़ंक्शन के वैल्यू की तुलना सभी संभावित समाधानों के लिए करनी होगी.

कंस्ट्रेंट ऑप्टिमाइज़ेशन के बारे में ज़्यादा जानें

Assignment

असाइनमेंट से जुड़ी समस्याओं में, टास्क के सेट को एजेंटों (जैसे कि कर्मचारी या मशीन) के एक ग्रुप को असाइन करना शामिल होता है, जहां हर एजेंट को किसी खास टास्क को असाइन करने की एक तय कीमत होती है. सबसे कम कुल कीमत वाला असाइनमेंट ढूंढना है. असाइनमेंट से जुड़ी समस्याएं, असल में नेटवर्क फ़्लो से जुड़ी समस्याओं का खास मामला है.

असाइनमेंट के बारे में ज़्यादा जानें

पैकिंग

बिन पैकिंग में अलग-अलग साइज़ के ऑब्जेक्ट को अलग-अलग क्षमता वाले कंटेनर में पैक किया जाता है. इसका मकसद कंटेनर की कपैसिटी पर निर्भर करते हुए, ज़्यादा से ज़्यादा ऑब्जेक्ट को पैक करना है. इसका एक खास मामला KSnapsack की समस्या है, जिसमें सिर्फ़ एक कंटेनर होता है.

बिन पैकिंग के बारे में ज़्यादा जानें

शेड्यूल करें

शेड्यूल करने में होने वाली समस्याओं में, तय समय पर टास्क पूरे करने के लिए संसाधन असाइन किए जाते हैं. इसका एक अहम उदाहरण नौकरी की दुकान की समस्या है, जिसमें कई कामों को कई मशीनों पर प्रोसेस किया जाता है. हर काम में एक क्रम में टास्क होते हैं जिन्हें एक तय क्रम में किया जाना चाहिए. साथ ही, हर टास्क को एक खास मशीन पर प्रोसेस किया जाना चाहिए. समस्या तो एक शेड्यूल असाइन करने की है, ताकि सभी काम कम से कम समय अंतराल में पूरा हो सके.

शेड्यूल करने के बारे में ज़्यादा जानें

रूटिंग

रूटिंग से जुड़ी समस्याओं में, नेटवर्क को पार करने के लिए वाहनों के ग्रुप के लिए, सबसे सही रास्ते ढूंढना शामिल है. इन रास्तों के बारे में निर्देश दिए गए ग्राफ़ से तय किया गया है. डिलीवरी ट्रक को पैकेज असाइन करने में होने वाली समस्या, रूटिंग से जुड़ी समस्या का एक उदाहरण है. इस समस्या के बारे में ऑप्टिमाइज़ेशन से जुड़ी समस्या क्या है? में बताया गया है. दूसरी समस्या है, यात्रा करने वाले विक्रेता की समस्या.

रूटिंग के बारे में ज़्यादा जानें

नेटवर्क फ़्लो

ऑप्टिमाइज़ेशन से जुड़ी कई समस्याओं को एक डायरेक्ट ग्राफ़ से दिखाया जा सकता है. इस ग्राफ़ में नोड और डायरेक्ट आर्क शामिल होते हैं. उदाहरण के लिए, परिवहन की समस्याएं, जिनमें रेल नेटवर्क पर सामान भेजा जाता है, को एक ग्राफ़ से दिखाया जा सकता है. इसमें चाप, रेल लाइन होती हैं और नोड डिस्ट्रिब्यूशन सेंटर होते हैं.

बोलने की ज़्यादा से ज़्यादा समस्या में, हर चाप की ज़्यादा से ज़्यादा क्षमता होती है, जिसे एक जगह से दूसरी जगह ले जाया जा सकता है. समस्या यह है कि हर ऑर्डर पर शिप किए जाने वाले सामान की संख्या असाइन की जाए, ताकि ढोए जा रहे कुल सामान की संख्या ज़्यादा से ज़्यादा हो.

नेटवर्क फ़्लो के बारे में ज़्यादा जानें