परिसंचरण समस्याओं में 'निचली बाध्य' का क्या अर्थ है?

Question

प्रश्न: परिसंचरण की समस्याएं आपको एक विशेष चाप के माध्यम से प्रवाह पर निचले और ऊपरी बाउंड दोनों की अनुमति देती हैं। ऊपरी बाउंड मैं समझता हूं (पाइप की तरह, केवल इतना ही सामान है जो जा सकता है)। हालांकि, मुझे निचले बाध्य विचार को समझने में मुश्किल हो रही है। इसका क्या मतलब है? एक निचली सीमा के साथ यकीन है कि हर चाप बनाने के लिए करेंगे समस्या को हल करने के लिए एक एल्गोरिथ्म ...

• कोशिश में नाकाम रहने के लिए पूरी तरह से अगर यह एक तरह से नहीं मिल रहा है, कम से कम इतना प्रवाह मिलेगा?
• यदि निचली बाउंड को पूरा नहीं किया जा सकता है तो बस चाप को नजरअंदाज कर दें? यह मेरे लिए अधिक मतलब होगा, लेकिन वहाँ परिणामी ग्राफ़ में 0 से प्रवाह के साथ आर्क्स हो सकता है, मतलब होगा यानी

प्रसंग: मैं एक तरह से जल्दी से एक सेट शेड्यूल करने के लिए खोजने की कोशिश कर रहा हूँ घटनाओं का, जिसमें प्रत्येक की लंबाई होती है और संभावित समय का एक सेट निर्धारित किया जा सकता है। मैं इस समस्या को परिसंचरण समस्या में कम करने की कोशिश कर रहा हूं, जिसके लिए कुशल एल्गोरिदम मौजूद हैं।

मैंने प्रत्येक घटना को एक निर्देशित ग्राफ में नोड के रूप में रखा है, और इसे भरने वाले समय स्लॉट की मात्रा के साथ आपूर्ति करें। तब मैं सभी संभव बार के रूप में रूप में अच्छी तरह नोड अंत में सब समय स्लॉट इस तरह (सभी आर्क्स सही को इंगित) जोड़ने के लिए, और,:

 

 

पहले दो कार्यक्रमों में एक भी संभावित समय और 1 की लंबाई होती है, और अंतिम घटना में 4 और दो संभावित समय की लंबाई होती है।

क्या यह ग्राफ समझ में आता है? अधिक विशेष रूप से, क्या 'स्लॉट' प्राप्त करने वाले समय स्लॉट की मात्रा 2 (केवल 'आसान' वाले) या छह हो, जैसे तस्वीर में?

(मैं LEMON पुस्तकालय से एक धक्का फिर लेबल कलन विधि का उपयोग कर रहा हूँ कि यदि कोई फर्क नहीं पड़ता।)

Answer 1

सामान्य परिसंचरण समस्या के बारे में:

मैं @Helen से सहमत; भले ही यह निचले बाध्य के व्यावहारिक उपयोग की कल्पना करने के लिए अंतर्ज्ञानी न हो, यह एक बाधा है कि से मुलाकात की जानी चाहिए। मुझे विश्वास नहीं है कि आप इस बाधा को नजरअंदाज कर पाएंगे, भले ही वह प्रवाह शून्य हो।

प्रवाह = 0 केस अधिक अंतर्ज्ञानी अधिकतम प्रवाह समस्या (जैसा कि @ किलियनडीएस द्वारा इंगित किया गया है) के लिए अपील करता है। उस मामले में, अगर नोड्स की एक जोड़ी के बीच प्रवाह शून्य है, तो वे "प्रवाह राशि के संरक्षण" को प्रभावित नहीं कर सकते हैं:

जब कोई लोअर बाउंड तो दिया जाता है (यह मानते हुए प्रवाह गैर नकारात्मक कर रहे हैं) एक शून्य प्रवाह परिणाम प्रभावित नहीं कर सकते, क्योंकि

1. यह कमी
2. यह राशि को प्रभावित नहीं कर सकते हैं (क्योंकि यह एक शून्य अवधि कहते हैं) के लिए एक उल्लंघन परिचय नहीं कर सकते।

एक न्यूनतम प्रवाह कुछ बाहरी बाधा की वजह से मौजूद हो सकता है की एक व्यावहारिक उदाहरण (एक संबद्ध समस्या कम से कम X पानी एक निश्चित पाइप के माध्यम से जाना है, के रूप में @Helen द्वारा बताया आवश्यकता है)। निचली बाध्य बाधाएं एक समान दोहरी समस्या से उत्पन्न हो सकती हैं, जो प्रवाह को कम करती है जैसे कि कुछ किनारों के निचले बाध्य होते हैं (और ऊपरी बाउंड के साथ अधिकतम क्षमता के बराबर इष्टतम पाता है)।

अपने विशिष्ट समस्या के लिए:

ऐसा लगता है कि आप के रूप में कई घटनाओं समय स्लॉट (जहां कोई दो घटनाओं एक समय स्लॉट में ओवरलैप कर सकते हैं) की एक निश्चित सेट में करवाने के लिए कोशिश कर रहे हैं। {09:10}
E2 - - {09:00}
E3 - {9

ई 1:

कि किसी दिए गए घटना को सौंपा जा सकता है समय स्लॉट के सेट पर विचार करें : 20 9:30, 09:40, 09:50}
E3 - {9:00 9:10 9:20 9:30}

तो तुम संख्या बढ़ाना चाहते हैं कार्य असाइनमेंट (यानी किनारों पर घटनाओं की घटना "चालू हो जाती है) सेंट परिणामस्वरूप सेट जोड़ों के विवाद होते हैं (यानी असाइन किए गए समय स्लॉट ओवरलैप में से कोई भी नहीं)।

मुझे विश्वास है कि यह एनपी-हार्ड है क्योंकि यदि आप इसे हल कर सकते हैं, तो आप इसे maximal set packing problem (यानी अधिकतम सेट पैकिंग को कम करने के लिए) का उपयोग कर सकते हैं। आपकी समस्या को पूर्णांक रैखिक प्रोग्रामिंग के साथ हल किया जा सकता है, लेकिन व्यावहारिक रूप से इन समस्याओं को लालची विधियों/शाखा और बाध्यता के साथ भी हल किया जा सकता है।

उदाहरण के लिए, आपकी उदाहरण समस्या में। E3 के साथ E3 और E2 विवादों के साथ ईवेंट E1 "संघर्ष"। यदि ई 1 असाइन किया गया है (केवल एक विकल्प है), तो ई 3 (बाद में असाइनमेंट) के केवल एक ही शेष असाइनमेंट असाइनमेंट है। यदि यह असाइनमेंट ई 3 के लिए लिया जाता है, तो ई 2 के लिए केवल एक शेष असाइनमेंट है। इसके अलावा, उप-अनुच्छेद (उन घटनाओं के सेट जो संभवतः संसाधनों पर संघर्ष नहीं कर सकते हैं) अलग-अलग हल किए जा सकते हैं।

यदि यह मैं था, तो मैं एक बहुत ही सरल लालची समाधान (कम से कम संभव "स्लॉट्स" के साथ कार्यों को आवंटित करता हूं) के साथ शुरू करता हूं, और उसके बाद उस शाखा का उपयोग शाखा और बाध्य सॉल्वर के लिए करता हूं (यदि लालची समाधान 4 पाया जाता है कार्य असाइनमेंट, तब बाध्य यदि आप असाइनमेंट के उप-अनुवर्ती उपखंड 3 से अधिक नहीं हो सकते हैं)। आप सेट के बीच जोड़ी के चौराहे के ग्राफ को बनाकर और असाइनमेंट सेट करते समय केवल आसन्न सेट को सूचित करके कुछ अतिरिक्त प्रदर्शन को निचोड़ सकते हैं। जब आप शाखा जारी रखते हैं और बाध्य करते हैं (मुझे लगता है कि यह सामान्य है) तो आप अपनी सर्वश्रेष्ठ संख्या में असाइनमेंट भी अपडेट कर सकते हैं, इसलिए यदि आप जल्दी भाग्यशाली हो जाते हैं, तो आप जल्दी से अभिसरण करते हैं।

मैंने प्रोटीन का सबसे छोटा सेट खोजने के लिए यही विचार किया है जो पहचाने गए पेप्टाइड्स (प्रोटीन टुकड़ों) के एक सेट को समझाएगा, और इसे व्यावहारिक समस्याओं के लिए पर्याप्त से अधिक पाया जाएगा। यह एक बहुत ही समान समस्या है।

आप किनारे प्रदर्शन खून बह रहा है की जरूरत है: जब rephrased, पूर्णांक रैखिक प्रोग्रामिंग इस समस्या यह है कि आप चाहते हैं के लगभग किसी भी संस्करण कर सकते हैं। बेशक, बहुत बुरे मामलों में यह धीमा हो सकता है (व्यावहारिक रूप से, यह शायद आपके लिए काम करने जा रहा है, खासकर यदि आपका ग्राफ बहुत घनिष्ठ रूप से जुड़ा हुआ नहीं है)। यदि ऐसा नहीं होता है, तो नियमित रैखिक प्रोग्रामिंग आराम आईएलपी के समाधान का अनुमान लगाते हैं और आमतौर पर इस तरह की समस्या के लिए काफी अच्छे होते हैं।

उम्मीद है कि इससे मदद मिलती है।

Answer 2

एक चाप के प्रवाह पर निचली बाध्य एक कठिन बाधा है। यदि बाधाओं को पूरा नहीं किया जा सकता है, तो एल्गोरिदम विफल रहता है। आपके मामले में, वे निश्चित रूप से पूरा नहीं किया जा सकता है।

आपकी समस्या को निम्न सीमाओं के साथ भी शुद्ध नेटवर्क-प्रवाह मॉडल के साथ मॉडल नहीं किया जा सकता है। आप बाधा पाने की कोशिश कर रहे हैं कि प्रवाह या तो 0 या कम से कम कुछ निचला बाध्य है। इसके लिए पूर्णांक चर की आवश्यकता होती है। हालांकि, LEMON पैकेज में interface है जहां आप पूर्णांक बाधाओं को जोड़ सकते हैं। आर्क की पहली परत में से प्रत्येक का प्रवाह या तो 0 या एन होना चाहिए जहां n आवश्यक समय-स्लॉट की संख्या है या आप कह सकते हैं कि प्रत्येक "ईवेंट" में से अधिकांश चापों में nonzero प्रवाह होता है। के रूप में

f >= y * lower 
f <= y * upper 

y के साथ

जा रहा है 0 या 1. यदि y 0 है, तो च केवल 0. हो सकता है, तो y 1 है के लिए प्रतिबंधित

आपका "अलगाव" बाधा, प्रतिरूप बनाया जा सकता, एफ निचले और ऊपरी के बीच कोई मूल्य हो सकता है। मिश्रित-पूर्णांक प्रोग्रामिंग एल्गोरिदम नेटवर्क-प्रवाह एल्गोरिदम की तुलना में तीव्रता के आदेश का आदेश देंगे, लेकिन वे आपकी समस्या का मॉडल करेंगे।