2025-11-13T22:16:11.184529

Fast and Interpretable Mixed-Integer Linear Program Solving by Learning Model Reduction

Li, Chen, Li et al.
By exploiting the correlation between the structure and the solution of Mixed-Integer Linear Programming (MILP), Machine Learning (ML) has become a promising method for solving large-scale MILP problems. Existing ML-based MILP solvers mainly focus on end-to-end solution learning, which suffers from the scalability issue due to the high dimensionality of the solution space. Instead of directly learning the optimal solution, this paper aims to learn a reduced and equivalent model of the original MILP as an intermediate step. The reduced model often corresponds to interpretable operations and is much simpler, enabling us to solve large-scale MILP problems much faster than existing commercial solvers. However, current approaches rely only on the optimal reduced model, overlooking the significant preference information of all reduced models. To address this issue, this paper proposes a preference-based model reduction learning method, which considers the relative performance (i.e., objective cost and constraint feasibility) of all reduced models on each MILP instance as preferences. We also introduce an attention mechanism to capture and represent preference information, which helps improve the performance of model reduction learning tasks. Moreover, we propose a SetCover based pruning method to control the number of reduced models (i.e., labels), thereby simplifying the learning process. Evaluation on real-world MILP problems shows that 1) compared to the state-of-the-art model reduction ML methods, our method obtains nearly 20% improvement on solution accuracy, and 2) compared to the commercial solver Gurobi, two to four orders of magnitude speedups are achieved.
academic

तेज़ और व्याख्यायोग्य मिश्रित-पूर्णांक रैखिक कार्यक्रम समाधान सीखने के माध्यम से मॉडल में कमी

मूल जानकारी

  • पेपर आईडी: 2501.00307
  • शीर्षक: तेज़ और व्याख्यायोग्य मिश्रित-पूर्णांक रैखिक कार्यक्रम समाधान सीखने के माध्यम से मॉडल में कमी
  • लेखक: Yixuan Li, Can Chen, Jiajun Li, Jiahui Duan, Xiongwei Han, Tao Zhong, Vincent Chau, Weiwei Wu, Wanyuan Wang
  • वर्गीकरण: cs.LG cs.AI
  • प्रकाशन तिथि: 31 दिसंबर 2024 (arXiv प्रीप्रिंट)
  • संस्थान: दक्षिण-पूर्व विश्वविद्यालय कंप्यूटर विज्ञान और इंजीनियरिंग कॉलेज, हुआवेई नूह आर्क लैब
  • पेपर लिंक: https://arxiv.org/abs/2501.00307

सारांश

यह पेपर मिश्रित पूर्णांक रैखिक प्रोग्रामिंग (MILP) संरचना और समाधान के बीच संबंध का उपयोग करके बड़े पैमाने पर MILP समाधान के लिए एक मशीन लर्निंग आधारित विधि प्रस्तावित करता है। मौजूदा अंत-से-अंत समाधान सीखने की विधियों के विपरीत, यह पेपर मूल MILP के सरलीकृत समतुल्य मॉडल को एक मध्यवर्ती चरण के रूप में सीखता है। यह विधि एक वरीयता-आधारित मॉडल में कमी सीखने की विधि प्रस्तावित करती है, जो प्रत्येक MILP उदाहरण पर सभी कम किए गए मॉडल के सापेक्ष प्रदर्शन को वरीयता जानकारी के रूप में मानती है, और वरीयता जानकारी को कैप्चर करने के लिए ध्यान तंत्र का परिचय देती है। प्रायोगिक परिणाम दिखाते हैं कि अत्याधुनिक मॉडल में कमी ML विधि की तुलना में, यह विधि समाधान सटीकता में लगभग 20% सुधार करती है, और वाणिज्यिक सॉल्वर Gurobi की तुलना में 2-4 परिमाण के क्रम का त्वरण प्राप्त करती है।

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या परिभाषा

मिश्रित पूर्णांक रैखिक प्रोग्रामिंग (MILP) आपूर्ति श्रृंखला लॉजिस्टिक्स, सेवा शेड्यूलिंग, ऊर्जा प्रबंधन, परिवहन योजना और अन्य महत्वपूर्ण क्षेत्रों में व्यापक अनुप्रयोग है। वास्तविक औद्योगिक अनुप्रयोगों में, MILP उदाहरणों में आमतौर पर दसियों हज़ार निर्णय चर और बाधाएं शामिल होती हैं, और मौजूदा वाणिज्यिक सॉल्वर सटीक समाधान विधियों पर आधारित हैं, जिनकी कम्प्यूटेशनल लागत अधिक है और वास्तविक समय की आवश्यकताओं को पूरा नहीं कर सकते।

अनुसंधान प्रेरणा

  1. स्केलेबिलिटी समस्या: मौजूदा ML विधियां सीधे उच्च-आयामी समाधान स्थान मैपिंग सीखती हैं, जिससे स्केलेबिलिटी समस्याएं उत्पन्न होती हैं
  2. व्याख्यायोग्यता की कमी: अंत-से-अंत विधियां व्याख्यायोग्य समाधान या सहज समझ प्रदान नहीं कर सकती हैं
  3. वरीयता जानकारी का अपर्याप्त उपयोग: मौजूदा मॉडल में कमी की विधियां केवल इष्टतम कम किए गए मॉडल पर ध्यान केंद्रित करती हैं, सभी कम किए गए मॉडल की महत्वपूर्ण वरीयता जानकारी को नज़रअंदाज़ करती हैं

मौजूदा विधियों की सीमाएं

  • अंत-से-अंत समाधान भविष्यवाणी: समाधान स्थान की उच्च-आयामीता के कारण भविष्यवाणी सटीकता कम है
  • सीखने का अनुकूलन: निर्णय क्षितिज की सीमाओं से प्रभावित, दक्षता सीमित है
  • मौजूदा मॉडल में कमी की विधियां: व्यवहार्य कम किए गए मॉडल को समान आदर्श लेबल के रूप में मानती हैं, तुलनात्मक जानकारी का पूर्ण उपयोग नहीं करती हैं

मुख्य योगदान

  1. वरीयता-आधारित मॉडल में कमी सीखने की विधि प्रस्तावित करना: कम किए गए मॉडल के प्रदर्शन को वरीयता जानकारी में परिवर्तित करना, उदाहरण-नीति स्थान में तुलनात्मक जानकारी का पूर्ण उपयोग करना
  2. ध्यान तंत्र आर्किटेक्चर डिज़ाइन करना: उदाहरण और वरीयता कम किए गए मॉडल के बीच संबंध को कैप्चर करना, सीखने की सटीकता में सुधार करना
  3. SETCOVER प्रूनिंग तकनीक का परिचय: कम किए गए मॉडल (लेबल) की संख्या को नियंत्रित करना, सभी उदाहरणों के लिए व्यवहार्य न्यूनतम लेबल सेट उत्पन्न करना
  4. महत्वपूर्ण प्रदर्शन सुधार का कार्यान्वयन: वास्तविक MILP समस्याओं पर सत्यापन, मौजूदा विधियों की तुलना में सटीकता में 20% सुधार, Gurobi की तुलना में 2-4 परिमाण के क्रम का त्वरण

विधि विवरण

कार्य परिभाषा

पैरामीटरयुक्त MILP समस्या दी गई:

min f(c, x)
s.t. g(A, x) ≤ b
     xI ∈ Z^d, x_{-I} ∈ R^{n-d}

जहां θ = ⟨A, c, b⟩ MILP पैरामीटर को दर्शाता है।

इष्टतम नीति परिभाषा: s*(θ) = (T(θ), x*_I(θ)), जिसमें तंग बाधा सेट T(θ) और इष्टतम समाधान पर पूर्णांक चर मान शामिल हैं।

उद्देश्य: पैरामीटर θ से इष्टतम नीति s*(θ) तक मैपिंग सीखना।

मॉडल आर्किटेक्चर

1. नीति पीढ़ी और प्रूनिंग चरण

  • नीति पीढ़ी: Good-Turing अनुमानक का उपयोग करके उदाहरण संख्या निर्धारित करना, जब तक N₁/N थ्रेसहोल्ड से नीचे न हो
  • नीति प्रूनिंग: उदाहरण-नीति द्विपक्षीय ग्राफ G(V_θ, V_s, E) का निर्माण, प्रूनिंग समस्या को SETCOVER समस्या में परिवर्तित करना
  • लालची एल्गोरिथ्म: पुनरावृत्ति से सबसे अधिक अनावृत्त उदाहरण नोड्स को कवर करने वाली नीति नोड्स का चयन करना

2. वरीयता-आधारित नीति सीखना

वरीयता गणना:

r(θᵢ, sⱼ) = -log(p(θᵢ, sⱼ) + d(θᵢ, sⱼ))

जहां p(θᵢ, sⱼ) अव्यवहार्यता है, d(θᵢ, sⱼ) उप-इष्टतमता है।

वरीयता परिभाषा:

(θᵢ, sⱼ) ≻ (θᵢ, sₖ) ⇔ r(θᵢ, sⱼ) > r(θᵢ, sₖ)

ध्यान तंत्र एन्कोडिंग:

A([θᵢ, S^P]) = softmax(QK^T/√d)V

प्रत्येक उदाहरण-नीति जोड़ी ⟨θᵢ, sⱼ⟩ को टोकन के रूप में मानना, बहु-स्तरीय ध्यान तंत्र के माध्यम से विशेषताएं निकालना।

तकनीकी नवाचार बिंदु

1. वरीयता नमूनाकरण अनुकूलन

वरीयता की संक्रामकता का उपयोग करके, नीतियों को वरीयता के अनुसार क्रमबद्ध करना, केवल M_P क्रमबद्ध वरीयता नमूनों की आवश्यकता है न कि (M_P choose 2) युग्मित तुलनाओं की, नमूना जटिलता को द्विघात से रैखिक तक कम करना।

2. दोहरी हानि फ़ंक्शन

  • वरीयता हानि:
L_p(φ) = -1/N ∑∑[μᵢ,ⱼ log(pᵢ,ⱼ) + (1-μᵢ,ⱼ) log(1-pᵢ,ⱼ)]
  • पुरस्कार अंतर हानि:
L_d(φ) = 1/N ∑∑(r̂ᵢ,σ(j) - r̂ᵢ,σ(j+1) - δᵢ,ⱼ)²
  • कुल हानि: L_total(φ) = λ₁L_p(φ) + λ₂L_d(φ)

3. शीर्ष-k नीति अनुमान

ऑनलाइन चरण में शीर्ष-k आउटपुट नीतियों को उम्मीदवार के रूप में चुनना, कम किए गए मॉडल को हल करके मूल्यांकन करना और सबसे कम अव्यवहार्यता वाली नीति का चयन करना।

प्रायोगिक सेटअप

डेटासेट

  1. MIPLIB: 6 परिदृश्यों की वास्तविक MILP समस्याएं, विभिन्न पैमाने और समाधान कठिनाई के साथ
  2. ईंधन सेल ऊर्जा प्रबंधन समस्या: समय चरण T को समायोजित करके समस्या जटिलता को नियंत्रित करना
  3. इन्वेंटरी प्रबंधन समस्या: 5 बड़ी वास्तविक औद्योगिक समस्याएं, औसतन लगभग 100,000 बाधाएं

मूल्यांकन मेट्रिक्स

सटीकता मेट्रिक्स:

accuracy = 1/N |{θᵢ | p(θᵢ, ŝⱼ) ≤ ε₁ ∧ d(θᵢ, ŝⱼ) ≤ ε₂}|

जहां अव्यवहार्यता और उप-इष्टतमता सहनशीलता दोनों 1×10⁻⁴ पर सेट हैं।

तुलनात्मक विधियां

  1. Gurobi: उन्नत वाणिज्यिक सॉल्वर (हॉट स्टार्ट सक्षम)
  2. Gurobi Heuristic: Gurobi अनुमानी मोड (1 सेकंड समय सीमा)
  3. MLOPT: सबसे उपयुक्त मॉडल में कमी आधारित सीखने की विधि
  4. Predict and Search: समाधान भविष्यवाणी आधारित विधि

कार्यान्वयन विवरण

  • ऑप्टिमाइज़र: AdamW, सीखने की दर 0.0001-0.001
  • सीखने की दर क्षय: प्रत्येक 10 राउंड में 0.9 गुना रैखिक क्षय, कुल 100 राउंड
  • बैच आकार: 128
  • समन्वय पैरामीटर λ₁: 0.8-0.9

प्रायोगिक परिणाम

मुख्य परिणाम

MIPLIB डेटासेट

  • अधिकांश परिदृश्यों में, यह विधि उप-इष्टतमता और व्यवहार्यता के संदर्भ में Gurobi के प्रदर्शन के समान है
  • MLOPT की तुलना में, व्यवहार्यता के संदर्भ में मामूली लाभ, उप-इष्टतमता में महत्वपूर्ण सुधार
  • अनुमानी विधि समय सीमा के कारण कई मेट्रिक्स पर खराब प्रदर्शन करती है

ईंधन सेल ऊर्जा प्रबंधन

  • सबसे जटिल समस्या पर सटीकता में लगभग 39% सुधार
  • नीति प्रूनिंग प्रभाव महत्वपूर्ण है, विशेष रूप से समस्या के पैमाने के साथ बढ़ते हुए
  • शीर्ष-k प्रदर्शन: k बढ़ने के साथ मॉडल प्रदर्शन में सुधार, समान k मान पर MLOPT से बेहतर

इन्वेंटरी प्रबंधन समस्या

  • सभी उदाहरणों पर व्यवहार्यता बनाए रखना, सटीकता लगभग 90% पर स्थिर
  • सबसे बड़ी समस्या P5 (27 लाख से अधिक बाधाओं) पर, MLOPT की तुलना में लगभग 30% सुधार

कम्प्यूटेशनल समय विश्लेषण

  • Gurobi की तुलना में 3 परिमाण के क्रम का समय सुधार
  • समस्या के पैमाने के साथ बढ़ते हुए समय अपेक्षाकृत स्थिर रहता है
  • MLOPT की तुलना में न्यूनतम अंतर (समान k मान पर)
  • शीर्ष-k गणना को समानांतर किया जा सकता है, गति में और सुधार

विलोपन प्रयोग

वरीयता सीखना बनाम पुरस्कार फिटिंग

ईंधन सेल डेटासेट पर, वरीयता विधि सीधी पुरस्कार फिटिंग की तुलना में औसत सटीकता में लगभग 9% सुधार, अव्यवहार्यता और उप-इष्टतमता मेट्रिक्स पर बेहतर प्रदर्शन।

क्रमबद्ध नमूनाकरण बनाम पारंपरिक नमूनाकरण

क्रमबद्ध विधि पारंपरिक वरीयता जोड़ी नमूनाकरण की तुलना में विभिन्न समस्या पैमानों पर औसत सटीकता में लगभग 8% सुधार, प्रशिक्षण लागत में महत्वपूर्ण कमी।

संबंधित कार्य

ML-आधारित MILP समाधान विधियों का वर्गीकरण

  1. अंत-से-अंत समाधान भविष्यवाणी: MILP उदाहरण से समाधान तक मैपिंग सीधे सीखना
  2. सीखने का अनुकूलन: पारंपरिक सटीक/अनुमानी विधियों को तेज़ करने के लिए सीखना
  3. MILP को सरल बनाना सीखना: MILP प्रीप्रोसेसिंग या पैमाने में कमी सीखना

यह पेपर मौजूदा कार्य के साथ संबंध

  • अंत-से-अंत विधियों की तुलना में: उच्च-आयामी समाधान स्थान सीखने की समस्या से बचना
  • सीखने के अनुकूलन की तुलना में: निर्णय क्षितिज सीमाओं से प्रभावित नहीं
  • मौजूदा मॉडल में कमी की तुलना में: केवल इष्टतम नीति के बजाय वरीयता जानकारी का पूर्ण उपयोग

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

  1. वरीयता-आधारित मॉडल में कमी सीखना MILP समाधान प्रदर्शन में महत्वपूर्ण सुधार करता है
  2. SETCOVER प्रूनिंग तकनीक नीति संख्या को प्रभावी ढंग से नियंत्रित करती है
  3. ध्यान तंत्र सफलतापूर्वक उदाहरण-नीति संबंध को कैप्चर करता है
  4. वास्तविक औद्योगिक समस्याओं पर महत्वपूर्ण त्वरण और सटीकता सुधार प्राप्त करना

सीमाएं

  1. विधि दोहराए गए संरचना वाली सजातीय MILP समस्याओं के लिए उपयुक्त है
  2. प्रभावी वरीयता मॉडल सीखने के लिए पर्याप्त प्रशिक्षण डेटा की आवश्यकता है
  3. नीति पीढ़ी चरण अभी भी इष्टतम समाधान प्राप्त करने के लिए वाणिज्यिक सॉल्वर की आवश्यकता है
  4. बड़ी समस्याओं में नीति स्थान अभी भी बहुत बड़ी हो सकती है

भविष्य की दिशाएं

  1. अधिक व्यापक अनुकूलन समस्या प्रकारों तक विस्तार
  2. प्रशिक्षण डेटा पर निर्भरता को कम करना
  3. नीति पीढ़ी दक्षता में और सुधार
  4. बिना निरीक्षण या अर्ध-निरीक्षण सीखने की विधियों की खोज

गहन मूल्यांकन

शक्तियां

  1. मजबूत नवाचार: MILP मॉडल में कमी में वरीयता सीखने को पहली बार व्यवस्थित रूप से पेश करना
  2. ठोस सैद्धांतिक आधार: संचालन अनुसंधान सिद्धांत के मॉडल में कमी की अवधारणा पर आधारित
  3. व्यापक प्रयोग: कई वास्तविक डेटासेट पर सत्यापन, औद्योगिक-स्तरीय समस्याओं सहित
  4. महत्वपूर्ण प्रदर्शन: मौजूदा विधियों की तुलना में पर्याप्त सुधार
  5. अच्छी व्याख्यायोग्यता: कम किए गए मॉडल व्याख्यायोग्य संचालन मोड के अनुरूप हैं

कमियां

  1. सीमित प्रयोज्यता: मुख्य रूप से पैरामीटरयुक्त MILP समस्याओं के लिए उपयुक्त
  2. प्रशिक्षण लागत: अभी भी बड़ी मात्रा में लेबल किए गए डेटा की आवश्यकता है (इष्टतम समाधान)
  3. अपर्याप्त सैद्धांतिक विश्लेषण: अभिसरण और सामान्यीकरण क्षमता का सैद्धांतिक गारंटी की कमी
  4. सीमित तुलनात्मक आधार: मुख्य रूप से एक सीखने की विधि (MLOPT) के साथ तुलना

प्रभाव

  1. शैक्षणिक योगदान: ML4CO क्षेत्र के लिए नई अनुसंधान दिशा प्रदान करना
  2. व्यावहारिक मूल्य: औद्योगिक MILP समाधान में सीधे अनुप्रयोग की संभावना
  3. पुनरुत्पादनीयता: विधि विवरण विस्तृत, प्रायोगिक सेटअप स्पष्ट
  4. प्रेरणा मूल्य: वरीयता सीखने का विचार अन्य अनुकूलन समस्याओं तक विस्तारित किया जा सकता है

प्रयोज्य परिदृश्य

  1. ऑनलाइन स्टोकेस्टिक योजना: समान MILP उदाहरणों को तेज़ी से हल करने की आवश्यकता
  2. आपूर्ति श्रृंखला अनुकूलन: पैरामीटर परिवर्तन लेकिन संरचना निश्चित समस्याएं
  3. वास्तविक समय शेड्यूलिंग: समाधान समय पर कठोर आवश्यकताओं वाले अनुप्रयोग
  4. बड़े पैमाने पर औद्योगिक अनुकूलन: वाणिज्यिक सॉल्वर के लिए कठिन समस्याएं

संदर्भ

पेपर इस क्षेत्र के महत्वपूर्ण कार्यों का हवाला देता है, जिनमें शामिल हैं:

  • Bengio, Lodi, and Prouvost (2021): संयोजक अनुकूलन के लिए ML सर्वेक्षण
  • Bertsimas and Stellato (2022): ऑनलाइन मिश्रित-पूर्णांक अनुकूलन
  • Misra, Roald, and Ng (2022): विवश अनुकूलन के लिए सीखना
  • साथ ही अंत-से-अंत सीखने और सीखने के अनुकूलन विधियों के संबंधित कार्यों की बड़ी संख्या

समग्र मूल्यांकन: यह ML4CO क्षेत्र में एक उच्च-गुणवत्ता वाला अनुसंधान पेपर है जो वरीयता सीखने की एक नवीन विधि प्रस्तावित करता है। हालांकि कुछ सीमाएं हैं, लेकिन इसके सैद्धांतिक योगदान और व्यावहारिक मूल्य दोनों बहुत उत्कृष्ट हैं, जो बड़े पैमाने पर MILP समाधान के लिए एक नया प्रभावी तरीका प्रदान करते हैं।