एलपी की बेहतर सेवा

एलपी टेक्नोलॉजी के मैच्योर होने के बावजूद, इस्तेमाल के कुछ मामलों में ज़्यादा बेहतर तकनीकों की ज़रूरत होती है. उदाहरण के लिए, ऐसे कई अलग-अलग एलपी एल्गोरिदम उपलब्ध हैं जिनकी अपनी खूबियां और खामियां हैं. इसके अलावा, संख्यात्मक अस्थिरता की वजह से सॉल्वर धीमे हो सकते हैं या कुछ मॉडल को हल नहीं कर सकते हैं.

इस गाइड में सिद्धांतों के बारे में जानकारी दी गई है. साथ ही, उदाहरण भी दिए गए हैं, जिनकी मदद से एलपी सॉल्वर को ज़्यादा से ज़्यादा परफ़ॉर्मेंस और भरोसेमंद तरीके से हासिल करने में मदद मिलेगी.

कॉन्सेप्ट

इस सेक्शन में, एलपी सॉल्वर बेहतर तरीके से इस्तेमाल करने के लिए अहम कॉन्सेप्ट के बारे में बताया गया है. हमें लगता है कि पाठकों को एलपी में दोहराव के कॉन्सेप्ट के बारे में पता है.

एलपी एल्गोरिदम के परिवार

एलपी के लिए एल्गोरिदम की इन क्लास को OR-टूल से ऐक्सेस किया जा सकता है.

  1. सिंप्लेक्स एल्गोरिदम, पहला एलपी एल्गोरिदम था. साथ ही, यह सबसे लोकप्रिय भी है. एल्गोरिदम सही इलाके के वर्टेक्स (कॉर्नर पॉइंट) के साथ-साथ काम करता है. इसके लिए, सही समाधान तक पहुंचने तक मकसद फ़ंक्शन की वैल्यू को बार-बार सुधारता रहता है. सिंप्लेक्स एल्गोरिदम दो तरह के होते हैं:

    1. प्राइमल सिंप्लेक्स, उस इलाके के सिरों के साथ-साथ चलता है जहां उस इलाके की सबसे नई चीज़ें दिखाई जाती हैं. यह वैरिएंट, LP से जुड़ी समस्याओं के क्रम को हल करने में खास तौर पर असरदार है. इसमें, मकसद के अलग-अलग फ़ंक्शन हैं. इसका मतलब है कि काम के क्षेत्र को पहले से तय किया जाना चाहिए.
    2. ड्यूअल सिंप्लेक्स, दो जगहों के किनारों पर काम करता है. यह वैरिएंट, एलपी से जुड़ी समस्याओं के क्रम को हल करने में खास तौर पर असरदार होता है, जहां डुअल फ़ंक्शनल रीजन तय होता है, उदाहरण के लिए, जब सिर्फ़ वैरिएबल की सीमाएं बदलती हैं. इस वजह से, एमआईपी सॉल्वर में ड्यूअल सिंप्लेक्स का ज़्यादा इस्तेमाल किया जाता है.

  2. बैरियर या इंटीरियर-पॉइंट तरीके, एलपी के लिए एल्गोरिदम की दूसरी प्रैक्टिकल फ़ैमिली थीं. बैरियर तरीके, कुशल (पॉलिनोमियल टाइम) की थ्योरी से मिली गारंटी को भरोसेमंद परफ़ॉर्मेंस के साथ जोड़ते हैं. जब नतीजे ठीक से काम नहीं करते, तब वे सिंप्लेक्स एल्गोरिदम को बेहतर बनाते हैं. उदाहरण के लिए, कुछ सॉल्वर साथ-साथ सिंप्लेक्स और बैरियर, दोनों को साथ-साथ चलाते हैं. इससे, उन्हें सबसे पहले खत्म होने वाले एल्गोरिदम से हल मिलता है.

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

नीचे दी गई टेबल में, OR-टूल में मौजूद एलपी सॉल्वर दिए गए हैं. इससे यह भी पता चलता है कि हर सॉल्वर में, तीन एल्गोरिदम के परिवारों में से किस को लागू किया गया है.

सॉल्वर सिंप्लेक्स बैरियर पहला ऑर्डर
क्लैप X X
सीपीएल X X
ग्लोपजी X
जीएलपीके X X
गुरोबील X X
पीडीएलपीG X
L दबाएं X X

G से पता चलता है कि सॉल्वर को Google ने डेवलप किया है. L बताता है कि समाधान करने वाले के लिए तीसरे पक्ष के डेवलपर से जारी लाइसेंस ज़रूरी है.

कौनसे सॉल्वर और एल्गोरिदम इस्तेमाल किए जाएं, इसके बारे में जानने के लिए सुझाव देखें.

हल करने का क्या मतलब होता है?

एलपी सॉल्वर का ज़्यादा से ज़्यादा फ़ायदा पाने के लिए, यह समझना ज़रूरी है कि जब कोई सॉल्वर, एलपी की समस्या का समाधान ढूंढ लेने का दावा करता है, तो क्या होता है. इस सेक्शन में इस सवाल का जवाब देने के लिए ज़रूरी बुनियादी जानकारी दी गई है. खास तौर पर, सवालों के जवाब देने के लिए ज़रूरी चीज़ों के बारे में बताया गया है.

सहनशीलता

एलपी सॉल्वर अक्सर फ़्लोटिंग-पॉइंट अरिथमेटिक का इस्तेमाल करते हैं. इस वजह से, उनके समाधानों में सुधार होने की संभावना ज़्यादा होती है. इस पर ध्यान देने और परफ़ॉर्मेंस को बेहतर बनाने के लिए, ऐसे समाधान खोजने पर ज़ोर न दिया जाए जो पहले से ही काफ़ी अच्छे हों. ऐसे में, वे समाधान स्वीकार करते हैं और समस्या को हल करने का दावा करते हैं. इसके लिए, ये समाधान कुछ सहिष्णुता तक की शर्तें पूरी करते हैं.

रेखीय प्रोग्रामिंग सवाल पर विचार करें

$$ \begin{align*} \min\quad & -2x_1 - x_2 \\ \text{s.t.}\quad& x_1 + x_2 \le 1\\ & x_1, x_2 \ge 0 \end{align*} $$

और इससे जुड़ी दोहरी समस्या

$$ \begin{align*} \max\quad& y \\ \text{s.t.}\quad& -2 - y \ge 0\\ &-1 - y \ge 0 \\ &y \le 0 \end{align*} $$

सवालों के इस जोड़े में, $ x_1 = 1, x_2 = 0 $ और दोहरे समाधान $ y = -2 $ का सबसे अनोखा और शुरुआती शुरुआती समाधान है. सॉल्वर किन समाधानों को सबसे बेहतर मान सकता है? इसका जवाब देने के लिए, हम नीचे दी गई संख्याएं तय करते हैं:

  • ड्यूअल गैप, प्राइमरी ऑब्जेक्टिव वैल्यू और ड्यूअल ऑब्जेक्ट वैल्यू के बीच का अंतर है. इस मामले में, $ |(-2x_1 - x_2) - y| $.
  • प्राइमल इन्फ़ेबिलिटी, प्रीमल कंस्ट्रेंट का उल्लंघन है. इस मामले में, $ (\max\{ (x_1+x_2) - 1, 0 \}, \max\{-x_1, 0\}, \max\{-x_2, 0\}) $.
  • दो चरणों में होने वाली परेशानियों का मतलब है, दोहरी सीमाओं का उल्लंघन करना. इस मामले में, $ (\max\{ 2 + y, 0 \}, \max\{ 1 + y, 0 \}, \max\{ y, 0 \}) $.

सॉल्वर किसी समाधान को तब सबसे बेहतर मानता है, जब ड्यूअल गैप, मुख्य अक्षमता, और डुअल इंफ़ीशियलिटी, दी गई सहिष्णुता से कम हो.1

खास तौर पर, अलग-अलग तरह के सॉल्वर और एल्गोरिदम में, प्राकृतिक और विषमलैंगिक, दोनों वजहों से यह छूट लागू होती है. उदाहरण के लिए, सिंप्लेक्स एल्गोरिदम में डुअलिटी गैप सिर्फ़ न्यूमेरिक (संख्या) में न होने की वजह से होता है, जबकि सटीक अंकगणित में भी प्राइमल और ड्यूअल इनफ़िसिलिटीज़ मौजूद होती हैं. कुछ तरीके सीधे तौर पर सीमित कंस्ट्रेंट $ x_1 \ge 0, x_2 \ge 0, $ और $ y \le 0 $ को लागू करते हैं. अन्य $x_1 + x_2 \le 1$ जैसी बाउंड्री कंस्ट्रेंट के उल्लंघनों को $x_1 + x_2 \le 1$ जैसी बाउंड्री कंस्ट्रेंट और ड्यूअल सॉल्वर के बराबर माना जाता है. कुछ सॉल्वर के लिए $ s_1 \ge 0, x_2 \ge 0, $ ,

सहिष्णुता के प्रभाव के उदाहरण के लिए, ऊपर दिए गए प्राइमल-ड्यूअल पेयर पर लागू $ \epsilon = \frac{1}{2} $ की कुल टॉलरेंस देखें. हल $ x_1 = 1.5, x_2 = 0, y = -3 $ में ज़ीरो ड्यूअल गैप और $ \epsilon $ से कम या इसके बराबर की सुविधाएं उपलब्ध नहीं हैं. इसलिए, सॉल्वर इस सलूशन को "बेहतरीन" बता सकता है. फिर भी, इसका मकसद वैल्यू (-3), -2 के सही सबसे सही मकसद वैल्यू से 1 और 2 से अलग है. $ \epsilon $ की सामान्य डिफ़ॉल्ट वैल्यू, 10^{-6}$ और 10^{-8}$ के बीच होती है. इसलिए, ऐसे बहुत ही खराब उदाहरण बहुत कम दिखते हैं, लेकिन नामुमकिन नहीं.

समाधान के टाइप

एलपी की समस्याओं के एक से ज़्यादा सबसे अच्छे समाधान हो सकते हैं. ऐसा तब और भी हो सकता है, जब सहनशक्ति को ध्यान में रखा जाता हो. हम ऊपर बताए गए एलपी एल्गोरिदम के तीन अलग-अलग परिवारों से मिले समाधानों के गुणों के बारे में कम शब्दों में चर्चा करते हैं.

सिंप्लेक्स एल्गोरिदम हमेशा काम के इलाके के वर्टेक्स या कॉर्नर पॉइंट दिखाते हैं. कुछ स्थितियों में इन समाधानों को प्राथमिकता दी जाती है, क्योंकि वे ज़्यादा कम होते हैं.

बैरियर और फ़र्स्ट-ऑर्डर विधियां आम तौर पर वर्टेक्स नहीं दिखाती हैं. (सिद्धांत में ऐसी और विशेषताएं बताई गई हैं जो इस गाइड के दायरे से बाहर हैं.)

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

सुझाव

एलपी सॉल्वर बेहतर तरीके से इस्तेमाल करने के लिए, हम ये सुझाव देते हैं.

समस्या से जुड़े डेटा को स्केल करना

संख्यात्मक समस्याओं की वजह से, सॉल्वर को मॉडल में धीरे-धीरे कन्वर्जन या फ़ेल होने का सामना करना पड़ सकता है. इस तरह की समस्याएं कई वजहों से हो सकती हैं. यहां हमने एक उदाहरण दिया है.

एलपी मॉडल में, बहुत छोटे या बड़े संख्यात्मक कॉन्सटेंट का दिखना आम बात है. ऊपर दिए गए उदाहरण को ध्यान में रखते हुए, अगर \(x_1\) और \(x_2\) "सेवा देने वाली कंपनी 1" या "सेवा देने वाली कंपनी 2" की संख्या को असाइन किए गए ग्राहकों की संख्या को दिखाता है. साथ ही, अगर हम इन ग्राहकों को सेवा देकर ज़्यादा से ज़्यादा फ़ायदा पाना चाहते हैं, तो हम नीचे दिए गए मकसद फ़ंक्शन लिख सकते हैं,

$$ \min -c_1x_1 - c_2x_2 $$

कहां:

  • $ c_1 $, सेवा देने वाली कंपनी 1 को ग्राहक असाइन करने का फ़ायदा है
  • $ c_2 $, सेवा देने वाली कंपनी 2 को ग्राहक असाइन करने का फ़ायदा है

नीचे दी गई शर्तों को पूरा करने वाले डुअल को पूरी तरह सहन करना $ \epsilon $:

  • $ y \le -c_1 + \epsilon $,
  • $ y \le -c_2 + \epsilon $.

अगर $ c_1 $ और $ c_2 $ की फ़ायदा यूनिट, छोटी फ़्रैक्शनल वैल्यू हैं जो $ \epsilon $ के बराबर स्केल पर होती हैं, तो दोहरी संभावना वाली स्थितियां थोड़ी कमज़ोर हो जाती हैं, इसलिए सबसे कम प्राइमल प्राइमल हो सकता है.

वहीं दूसरी ओर, फ़ायदे की इकाइयां "माइक्रोडॉलर" (1,000,000 माइक्रोडॉलर = 1 डॉलर) हैं, तो नतीजे में मिलने वाले बहुत बड़े निरपेक्ष मान, समाधान में बहुत ज़्यादा सटीक होने की मांग करते हैं. फ़्लोटिंग पॉइंट नंबर की सीमाओं की वजह से, हो सकता है कि वैल्यू काफ़ी ज़्यादा सटीक हो. अगर सवाल इस तरह से तय किया जाए, तो शायद सॉल्वर साथ न मिलें. सही समस्या का हल निकालने के लिए, बेहतर मॉडलर को यह देखना चाहिए कि समस्या से जुड़े डेटा को स्केल करने के लिए इस्तेमाल होने वाले डेटा की वैल्यू, सॉल्वर की क्षमता के मुताबिक है या नहीं.

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

यह जानने के लिए कि Glop पर कितना असर डाला जा सकता है, GlopParameters में primal_feasibility_tolerance, dual_feasibility_tolerance, और solution_feasibility_tolerance देखें. ध्यान दें कि primal_feasibility_tolerance और dual_feasibility_tolerance का इस्तेमाल एल्गोरिदम में किया जाता है, जबकि solution_feasibility_tolerance का इस्तेमाल, समस्याओं को हल करने के बाद संख्या में होने वाली समस्याओं को फ़्लैग करने के लिए किया जाता है. पीडीपी के लिए eps_optimal_absolute और eps_optimal_relative देखें.

इस तरह की समस्याओं के बारे में ज़्यादा जानने के लिए, Gurobi के संख्यात्मक समस्याओं के लिए दिशा-निर्देश देखें. वैसे तो Gurobi के उपयोगकर्ताओं के लिए दिशा-निर्देश लिखे गए हैं, फिर भी कई सिद्धांत आम तौर पर लागू होते हैं.

सॉल्वर और एल्गोरिदम के विकल्प

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

डेटा में बदलाव

हम एलपी एल्गोरिदम और सॉल्वर की परफ़ॉर्मेंस में होने वाले उतार-चढ़ाव के बारे में बताते हैं. इसके लिए, हम उन इंस्टेंस के चुने गए इंस्टेंस के आधार पर सॉल्व टाइम की तुलना करते हैं जिनका इस्तेमाल एलपी सॉल्वर मानदंड के लिए हैन्स मित्तलमैन इस्तेमाल करते हैं. इन इंस्टेंस को खास तौर पर, थोड़ी-बहुत परफ़ॉर्मेंस दिखाने के लिए चुना जाता है. साथ ही, ये सामान्य व्यवहार नहीं के तौर पर दिखाए जाते हैं.

ग्लोप के प्राइमल और ड्यूअल सिंप्लेक्स तरीकों की तुलना, गुरोबी के बैरियर तरीके (क्रॉसओवर के साथ और उसके बिना, जो वर्टेक्स समाधान ढूंढती है) से की जाती है और पीडीएलपी, एक फ़र्स्ट-ऑर्डर तरीका, ज़्यादा और कम सटीक है. नीचे दी गई टेबल में, 20 मिनट (1200 सेकंड) की सीमा में, समय को सेकंड में हल किया जाता है.

इंस्टेंस ग्लोप
प्राइमल सिंप्लेक्स		 ग्लोप
ड्यूअल सिंप्लेक्स		 क्रॉसओवर के साथ गुरोबी बैरियर
 गुरोबी बैरियर
बिना क्रॉसओवर		 पीडीएलपी
ज़्यादा सटीक		 पीडीएलपी
कम सटीक
ex10 >1200 >1200 79.7 63.5 8.2 2.7
Nug08-3रा >1200 252.8 144.6 3.2 1.1 0.9
savsched1 >1200 >1200 156.0 78 जीबी में से 46.4 32.4
wide15 >1200 20.8 >1200 >1200 916.4 56.3
बिल्डिंग एनर्जी 178.4 267.5 78 जीबी में से 12.3 >1200 157.2
CANNOT TRANSLATE 12.1 520.6 15.2 16.4 >1200 >1200
सॉल्वर वर्शन या-टूल 9.3 या-टूल 9.3 गुरोबी 9.0 गुरोबी 9.0 या-टूल 9.3 या-टूल 9.3
solver_specific_parameters (डिफ़ॉल्ट) use_dual_simplex: true Method 2, Threads 1 Method 2, Crossover 0, Threads 1 termination_criteria { eps_optimal_absolute: 1e-8 eps_optimal_relative: 1e-8 } termination_criteria { eps_optimal_absolute: 1e-4 eps_optimal_relative: 1e-4 }

इन नतीजों के आधार पर हम ये बातें पता लगाते हैं.

  • अलग-अलग एल्गोरिदम और सॉल्वर की परफ़ॉर्मेंस एक ही जगह पर अलग-अलग हो सकती है.
  • कोई भी एक एल्गोरिदम और सॉल्वर, दूसरों से बेहतर नहीं होता है.
  • क्रॉसओवर (डिफ़ॉल्ट रूप से चालू) सॉल्व समय को बढ़ा देता है, कभी-कभी काफ़ी हद तक बढ़ जाता है.
  • पीडीपी को ज़्यादा सटीक तरीके से हल करने के मुकाबले, कभी-कभी 10 गुना तेज़ी से समस्या हल की जा सकती है.

एलपी सॉल्वर चुनने के लिए छोटी सी गाइड

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

  1. Glop आज़माएं. क्यों: Glop Google ने प्राइमल और ड्यूअल सिंप्लेक्स तरीकों को इन-हाउस तरीके से लागू किया है. Glop एक ओपन सोर्स है और Google के प्रोडक्शन वर्कलोड के लिए भरोसेमंद है.
    • अगर डिफ़ॉल्ट कॉन्फ़िगरेशन (प्राइमल सिंप्लेक्स) अच्छा परफ़ॉर्म नहीं करता है, तो use_dual_simplex: true का इस्तेमाल करके ड्यूअल सिंप्लेक्स पर स्विच करने की कोशिश करें.
  2. अगर लाइसेंस उपलब्ध है, तो कमर्शियल सॉल्वर (CPLEX, Gurobi या Xpress) आज़माएं. सिंप्लेक्स और बैरियर तरीकों के साथ प्रयोग करें. क्यों: ये सॉल्वर इंडस्ट्री स्टैंडर्ड और अच्छी तरह ऑप्टिमाइज़ किए गए हैं. साथ ही, बैरियर तरीके, Glop के सिंप्लेक्स एल्गोरिदम को बेहतर बनाते हैं.
    • अगर बैरियर का इस्तेमाल किया जा रहा है, तो अगर आपको वर्टेक्स सलूशन की ज़रूरत नहीं है, तो "क्रॉसओवर" को बंद कर दें.
  3. पीडीपी को आज़माएं. अपने ऐप्लिकेशन के लिए एक जैसे तरीकों को अपनाएं. क्यों: पीडीएल को सबसे बड़ी समस्याओं के लिए डिज़ाइन किया गया है, जहां सिंप्लेक्स और रुकावट डालने वाले तरीकों से मेमोरी की सीमा तय होती है या बहुत धीमी होती है. पीडीपी सबसे बेहतर तब काम करता है, जब सटीक और धीमी प्रोसेस वाले समाधान को प्राथमिकता दी जाती है.
  4. अगर आप यहां तक पहुंच गए हैं, तो अब आप एक बेहतर LP उपयोगकर्ता हैं! ज़्यादा सहायता के लिए कृपया या-टूल सहायता विकल्प देखें.

  1. अक्सर यह इससे ज़्यादा मुश्किल होता है. आम तौर पर, सॉल्वर इन स्थितियों की जांच, समस्या के बदले गए/आसान वर्शन में करते हैं. इसे पहले से हल किया गया सवाल कहा जाता है. कुछ मामलों में, हल की गई समस्या का समाधान, इनपुट में मौजूद समस्या के समाधान से काफ़ी दूर हो सकता है. इस वजह से, CPLEX OptimalInfeas या Glop IMPRECISE जैसे असामान्य स्टेटस हो सकते हैं.↩