क्वाड्रैटिक से रैखिक प्रोग्राम को कैसे परिवर्तित करें?

Question

मेरे पास एक ऑप्टिमाइज़ेशन समस्या है जो उद्देश्य फ़ंक्शन 2 गुणा चर में है, जो मॉडल वर्गबद्ध बनाती है।

मैं वर्तमान में मॉडल को पार्स करने के लिए zimpl का उपयोग कर रहा हूं, और इसे हल करने के लिए glpk। चूंकि वे वर्गबद्ध प्रोग्रामिंग का समर्थन नहीं करते हैं, इसलिए मुझे इसे एक एमआईएलपी में बदलने की आवश्यकता होगी।

। पहला चर वास्तविक है, श्रेणी [0, 1] में, दूसरा वास्तविक है, श्रेणी 0 से inf तक। यह बिना किसी समस्या के पूर्णांक हो सकता है।

उद्देश्य समारोह में महत्वपूर्ण हिस्सा इस तरह दिखता है:

max ... + var1 * var2 + ... 

मैं बाधाओं में इसी तरह की समस्या नहीं थी, लेकिन वे आसानी से व्याख्या करने योग्य थे।

मैं उद्देश्य कार्य में इस तरह की समस्या को कैसे हल कर सकता हूं?

Answer 1

इस फ़ॉर्म में मॉडल को वास्तव में बिलीनेर ऑप्टिमाइज़ेशन समस्या कहा जाता है। Bilinear शर्तों को रेखांकित करने के लिए सामान्य दृष्टिकोण McCormick लिफाफा कहा जाता है के माध्यम से है।

चर और एक्स पर विचार करें, जहां आप अपनी अधिकतम समस्या के उद्देश्य से x*y चाहते हैं। अगर हम यह मान x और y xL <= x <= xU और yL <= y <= yU से घिरा रहे हैं, तो हम w, मात्रा के लिए एक ऊपरी बाध्य साथ x*y की जगह ले सकता है, तो निम्न बाधाओं के साथ (आप व्युत्पत्ति here देख सकते हैं):

w <= xU*y + x*yL - xU*yL 
w <= x*yU + xL*y - xL*yU 
xL <= x <= xU 
yL <= y <= yL 

ध्यान दें कि ये बाधा निर्णय चर में सभी रैखिक हैं। McCormick लिफाफा में इसी तरह की निचली सीमाएं हैं, लेकिन चूंकि आप अधिकतम कर रहे हैं, वे आपके मामले में महत्वहीन हैं।

यदि आप x*y पर कड़े बाध्य चाहते हैं, तो आप चर [xL1, xU1], [xL2, xU2], [xL2, xU2], ... में चर के एक अंतराल पर अंतराल को विभाजित कर सकते हैं ..., [xLn, xUn], सहायक निरंतर चर {x1, x2, ..., xn} और {w1, w2, ..., wn} के साथ-साथ सहायक बाइनरी चर {z1, z2, ..., zn} , जो इंगित करेगा कि x मानों की किस श्रेणी का चयन किया गया था। बाधाओं से ऊपर द्वारा प्रतिस्थापित किया जा सकता है (मैं सूचकांक 1 मामले दिखाता हूँ, लेकिन आप सभी n सूचकांक के लिए इन की आवश्यकता होगी):

w1 <= xU1*y + x1*yL - xU1*yL*z1 
w1 <= x1*yU + xL1*y - xL1*yU*z1 
xL*z1 <= x1 <= xU*z1 

मूल रूप से आप x1 = 0 और w1 होगा < = 0 जब भी z1 = 0 (उर्फ इस श्रेणी का हिस्सा चुना नहीं गया है), और यदि आपके पास z1 = 1 (उर्फ श्रेणी का यह हिस्सा चुना गया है) तो आपके पास सामान्य McCormick लिफाफा होगा।

अंतिम चरण इन चर के श्रेणी-विशिष्ट संस्करणों से एक्स और डब्ल्यू उत्पन्न करना है। इस के साथ किया जा सकता है:

x = x1 + x2 + ... + xn 
w = w1 + w2 + ... + wn 

बड़ा तुम n बनाने के लिए, और अधिक एक अनुमान के सटीक आप द्विरेखीय अवधि के लिए होगा। हालांकि एन के बड़े मूल्य आपके मॉडल को हल करने की प्रवृत्ति को प्रभावित करेंगे।

एक अंतिम नोट - आप इंगित करते हैं कि आपके चर में से एक चरम पर है, लेकिन McCormick लिफाफा दोनों चरों पर सीमाओं की आवश्यकता है। आपको सीमा तय करना चाहिए, हल करना चाहिए, और यदि आपका इष्टतम मूल्य सीमा पर है तो आपको एक अलग सीमा के साथ फिर से हल करना चाहिए।