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
শিরোনাম: দ্রুত এবং ব্যাখ্যাযোগ্য মিশ্র-পূর্ণসংখ্যা রৈখিক প্রোগ্রাম সমাধান শেখার মাধ্যমে মডেল হ্রাস
লেখক: ইয়িক্সুয়ান লি, ক্যান চেন, জিয়াজুন লি, জিয়াহুই ডুয়ান, জিয়ংওয়েই হান, তাও ঝং, ভিনসেন্ট চাউ, ওয়েইওয়েই উ, ওয়ানিউয়ান ওয়াং
শ্রেণীবিভাগ: cs.LG cs.AI
প্রকাশনার সময়: ২০২৪ সালের ৩১ ডিসেম্বর (arXiv প্রাক-প্রিন্ট)
প্রতিষ্ঠান: দক্ষিণ-পূর্ব বিশ্ববিদ্যালয় কম্পিউটার বিজ্ঞান ও প্রকৌশল কলেজ, হুয়াওয়ে নোয়াহ আর্ক ল্যাবরেটরি
পেপার লিঙ্ক: https://arxiv.org/abs/2501.00307

সারসংক্ষেপ

এই পেপারটি মিশ্র-পূর্ণসংখ্যা রৈখিক প্রোগ্রামিং (MILP) কাঠামো এবং সমাধানের মধ্যে সম্পর্ক ব্যবহার করে বৃহৎ-স্কেল MILP সমাধানের জন্য একটি মেশিন লার্নিং-ভিত্তিক পদ্ধতি প্রস্তাব করে। বিদ্যমান প্রান্ত-থেকে-প্রান্ত সমাধান শেখার পদ্ধতির বিপরীতে, এই পেপারটি মূল MILP-এর সরলীকৃত সমতুল্য মডেল একটি মধ্যবর্তী পদক্ষেপ হিসাবে শেখে। এই পদ্ধতিটি একটি পছন্দ-ভিত্তিক মডেল হ্রাস শেখার পদ্ধতি প্রস্তাব করে যা প্রতিটি MILP উদাহরণে সমস্ত হ্রাসকৃত মডেলের আপেক্ষিক কর্মক্ষমতা বিবেচনা করে এবং মনোযোগ প্রক্রিয়া প্রবর্তন করে পছন্দের তথ্য ক্যাপচার করতে। পরীক্ষামূলক ফলাফল দেখায় যে অত্যাধুনিক মডেল হ্রাস ML পদ্ধতির তুলনায় এই পদ্ধতি সমাধান নির্ভুলতায় প্রায় ২০% উন্নতি করে এবং বাণিজ্যিক সমাধানকারী Gurobi-এর তুলনায় ২-৪ অর্ডার ম্যাগনিটিউড ত্বরণ অর্জন করে।

গবেষণা পটভূমি এবং প্রেরণা

সমস্যা সংজ্ঞা

মিশ্র-পূর্ণসংখ্যা রৈখিক প্রোগ্রামিং (MILP) সরবরাহ শৃঙ্খল লজিস্টিক্স, সেবা সময়সূচী, শক্তি ব্যবস্থাপনা এবং পরিবহন পরিকল্পনার মতো গুরুত্বপূর্ণ ক্ষেত্রে ব্যাপক প্রয়োগ রয়েছে। বাস্তব শিল্প প্রয়োগে, MILP উদাহরণগুলি সাধারণত দশ লক্ষ সিদ্ধান্ত ভেরিয়েবল এবং সীমাবদ্ধতা জড়িত, বিদ্যমান বাণিজ্যিক সমাধানকারীগুলি সঠিক সমাধান পদ্ধতির উপর ভিত্তি করে তৈরি, গণনা খরচ বেশি এবং রিয়েল-টাইম চাহিদা পূরণ করতে পারে না।

গবেষণা প্রেরণা

১. স্কেলেবিলিটি সমস্যা: বিদ্যমান ML পদ্ধতিগুলি সরাসরি উচ্চ-মাত্রিক সমাধান স্থান ম্যাপিং শেখে, স্কেলেবিলিটি সমস্যা রয়েছে २. ব্যাখ্যাযোগ্যতার অভাব: প্রান্ত-থেকে-প্রান্ত পদ্ধতি ব্যাখ্যাযোগ্য সমাধান বা স্বজ্ঞাত বোঝাপড়া প্রদান করতে পারে না ३. পছন্দের তথ্য ব্যবহার অপর্যাপ্ত: বিদ্যমান মডেল হ্রাস পদ্ধতিগুলি শুধুমাত্র সর্বোত্তম হ্রাসকৃত মডেলের উপর ফোকাস করে, সমস্ত হ্রাসকৃত মডেলের গুরুত্বপূর্ণ পছন্দের তথ্য উপেক্ষা করে

বিদ্যমান পদ্ধতির সীমাবদ্ধতা

প্রান্ত-থেকে-প্রান্ত সমাধান পূর্বাভাস: সমাধান স্থানের উচ্চ-মাত্রিকতার কারণে পূর্বাভাস নির্ভুলতা কম
শেখার অপ্টিমাইজেশন: সিদ্ধান্ত দৃষ্টিভঙ্গি সীমাবদ্ধতার দ্বারা প্রভাবিত, দক্ষতা সীমিত
বিদ্যমান মডেল হ্রাস পদ্ধতি: সম্ভাব্য হ্রাসকৃত মডেলগুলিকে সমান আদর্শ লেবেল হিসাবে বিবেচনা করে, তুলনামূলক তথ্য সম্পূর্ণভাবে ব্যবহার করে না

মূল অবদান

१. পছন্দ-ভিত্তিক মডেল হ্রাস শেখার পদ্ধতি প্রস্তাব: হ্রাসকৃত মডেলের কর্মক্ষমতা পছন্দের তথ্যে রূপান্তরিত করে, উদাহরণ-কৌশল স্থানে তুলনামূলক তথ্য সম্পূর্ণভাবে ব্যবহার করে २. মনোযোগ প্রক্রিয়া স্থাপত্য ডিজাইন: উদাহরণ এবং পছন্দের হ্রাসকৃত মডেলের মধ্যে সম্পর্ক ক্যাপচার করে, শেখার নির্ভুলতা উন্নত করে ३. SETCOVER ছাঁটাই প্রযুক্তি প্রবর্তন: হ্রাসকৃত মডেল (লেবেল) সংখ্যা নিয়ন্ত্রণ করে, সমস্ত উদাহরণের জন্য সম্ভাব্য ন্যূনতম লেবেল সেট তৈরি করে ४. উল্লেখযোগ্য কর্মক্ষমতা উন্নতি বাস্তবায়ন: বাস্তব MILP সমস্যায় যাচাই করা, বিদ্যমান পদ্ধতির তুলনায় নির্ভুলতা ২০% উন্নতি, Gurobi-এর তুলনায় ২-৪ অর্ডার ম্যাগনিটিউড ত্বরণ

পদ্ধতি বিস্তারিত

কাজের সংজ্ঞা

প্যারামিটারাইজড 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*(θ)-এ ম্যাপিং শিখুন।

মডেল স্থাপত্য

१. কৌশল উৎপাদন এবং ছাঁটাই পর্যায়

কৌশল উৎপাদন: Good-Turing অনুমানকারী ব্যবহার করে উদাহরণ সংখ্যা নির্ধারণ করুন, যতক্ষণ না N₁/N থ্রেশহোল্ডের নিচে পড়ে
কৌশল ছাঁটাই: উদাহরণ-কৌশল দ্বিপক্ষীয় গ্রাফ G(V_θ, V_s, E) তৈরি করুন, ছাঁটাই সমস্যাকে SETCOVER সমস্যায় রূপান্তরিত করুন
লোভী অ্যালগরিদম: পুনরাবৃত্তিমূলকভাবে সবচেয়ে বেশি অকভার করা উদাহরণ নোড কভার করে এমন কৌশল নোড নির্বাচন করুন

२. পছন্দ-ভিত্তিক কৌশল শেখা

পছন্দ গণনা:

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ⱼ⟩কে টোকেন হিসাবে বিবেচনা করুন, বহু-স্তরীয় মনোযোগ প্রক্রিয়ার মাধ্যমে বৈশিষ্ট্য নিষ্কাশন করুন।

প্রযুক্তিগত উদ্ভাবন পয়েন্ট

१. পছন্দ নমুনা অপ্টিমাইজেশন

পছন্দের ট্রানজিটিভিটি ব্যবহার করে, কৌশলগুলিকে পছন্দ অনুযায়ী সাজান, শুধুমাত্র M_P অর্ডার করা পছন্দের নমুনা প্রয়োজন (M_P choose 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(φ)

३. শীর্ষ-k কৌশল অনুমান

অনলাইন পর্যায়ে শীর্ষ-k আউটপুট কৌশল প্রার্থী হিসাবে নির্বাচন করুন, হ্রাসকৃত মডেল সমাধান করে মূল্যায়ন করুন এবং সর্বনিম্ন অসম্ভবতা সহ কৌশল নির্বাচন করুন।

পরীক্ষামূলক সেটআপ

ডেটাসেট

१. MIPLIB: ৬টি পরিস্থিতির বাস্তব MILP সমস্যা, বিভিন্ন স্কেল এবং সমাধান কঠিনতা २. জ্বালানী কোষ শক্তি ব্যবস্থাপনা সমস্যা: সময় পদক্ষেপ T বৃদ্ধি করে সমস্যা জটিলতা সামঞ্জস্য করুন ३. ইনভেন্টরি ম্যানেজমেন্ট সমস্যা: ৫টি বৃহৎ-স্কেল বাস্তব শিল্প সমস্যা, গড়ে প্রায় ১০০,০০০ সীমাবদ্ধতা

মূল্যায়ন মেট্রিক্স

নির্ভুলতা মেট্রিক্স:

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

যেখানে অসম্ভবতা এবং সাব-অপ্টিমালিটি সহনশীলতা উভয়ই ১×१०⁻⁴ এ সেট করা হয়।

তুলনামূলক পদ্ধতি

१. Gurobi: উন্নত বাণিজ্যিক সমাধানকারী (উষ্ণ শুরু সক্ষম) २. Gurobi হিউরিস্টিক: Gurobi হিউরিস্টিক মোড (১ সেকেন্ড সময় সীমা) ३. MLOPT: সবচেয়ে প্রযোজ্য মডেল হ্রাস-ভিত্তিক শেখার পদ্ধতি ४. পূর্বাভাস এবং অনুসন্ধান: সমাধান পূর্বাভাস-ভিত্তিক পদ্ধতি

বাস্তবায়ন বিবরণ

অপ্টিমাইজার: AdamW, শেখার হার ০.०००१-०.००१
শেখার হার ক্ষয়: প্রতি ১০ রাউন্ডে রৈখিক ক্ষয় ०.९ গুণ, মোট १००রাউন্ড
ব্যাচ আকার: १२८
সমন্বয় প্যারামিটার λ₁: ०.८-०.९

পরীক্ষামূলক ফলাফল

প্রধান ফলাফল

MIPLIB ডেটাসেট

বেশিরভাগ পরিস্থিতিতে, এই পদ্ধতি সাব-অপ্টিমালিটি এবং সম্ভাব্যতার ক্ষেত্রে Gurobi-এর সাথে তুলনীয় কর্মক্ষমতা প্রদান করে
MLOPT-এর তুলনায়, সম্ভাব্যতার ক্ষেত্রে সামান্য সুবিধা, সাব-অপ্টিমালিটিতে উল্লেখযোগ্য উন্নতি
হিউরিস্টিক পদ্ধতি সময় সীমাবদ্ধতার কারণে একাধিক মেট্রিক্সে দুর্বল কর্মক্ষমতা প্রদর্শন করে

জ্বালানী কোষ শক্তি ব্যবস্থাপনা

সবচেয়ে জটিল সমস্যায় নির্ভুলতা প্রায় ३९% উন্নতি
কৌশল ছাঁটাই প্রভাব উল্লেখযোগ্য, বিশেষত সমস্যার স্কেল বৃদ্ধির সাথে
শীর্ষ-k কর্মক্ষমতা: k বৃদ্ধির সাথে মডেল কর্মক্ষমতা উন্নতি, একই k মানে MLOPT-এর চেয়ে উন্নত

ইনভেন্টরি ম্যানেজমেন্ট সমস্যা

সমস্ত উদাহরণে সম্ভাব্যতা বজায় রাখে, নির্ভুলতা প্রায় ९०% এ স্থিতিশীল
সর্বাধিক স্কেল সমস্যা P५ (२७ লক্ষেরও বেশি সীমাবদ্ধতা)-এ, MLOPT-এর তুলনায় প্রায় ३०% উন্নতি

গণনা সময় বিশ্লেষণ

Gurobi-এর তুলনায় ३ অর্ডার ম্যাগনিটিউড সময় উন্নতি অর্জন করে
সমস্যার স্কেল বৃদ্ধির সাথে সময় তুলনামূলকভাবে স্থিতিশীল থাকে
MLOPT-এর তুলনায় ন্যূনতম পার্থক্য (একই k মানে)
শীর্ষ-k গণনা সমান্তরালকরণযোগ্য, গতি আরও উন্নত করে

অ্যাবলেশন পরীক্ষা

পছন্দ শেখা বনাম পুরস্কার ফিটিং

জ্বালানী কোষ ডেটাসেটে, পছন্দ পদ্ধতি সরাসরি পুরস্কার ফিটিং-এর তুলনায় গড় নির্ভুলতা প্রায় ९% উন্নতি করে, অসম্ভবতা এবং সাব-অপ্টিমালিটি মেট্রিক্সে উন্নত কর্মক্ষমতা।

অর্ডারিং নমুনা বনাম ঐতিহ্যবাহী নমুনা

অর্ডারিং পদ্ধতি ঐতিহ্যবাহী পছন্দ জোড়া নমুনার তুলনায় বিভিন্ন সমস্যা স্কেলে গড় নির্ভুলতা প্রায় ८% উন্নতি করে, প্রশিক্ষণ খরচ উল্লেখযোগ্যভাবে হ্রাস করে।

উপসংহার এবং আলোচনা

প্রধান উপসংহার

१. পছন্দ-ভিত্তিক মডেল হ্রাস শেখা MILP সমাধান কর্মক্ষমতা উল্লেখযোগ্যভাবে উন্নত করে २. SETCOVER ছাঁটাই প্রযুক্তি কৌশল সংখ্যা কার্যকরভাবে নিয়ন্ত্রণ করে ३. মনোযোগ প্রক্রিয়া সফলভাবে উদাহরণ-কৌশল সম্পর্ক ক্যাপচার করে ४. বাস্তব শিল্প সমস্যায় উল্লেখযোগ্য ত্বরণ এবং নির্ভুলতা উন্নতি অর্জন করে

সীমাবদ্ধতা

१. পদ্ধতি পুনরাবৃত্তিমূলক কাঠামো সহ সমজাতীয় MILP সমস্যার জন্য প্রযোজ্য २. কার্যকর পছন্দ মডেল শিখতে পর্যাপ্ত প্রশিক্ষণ ডেটা প্রয়োজন ३. কৌশল উৎপাদন পর্যায় এখনও সর্বোত্তম সমাধান পেতে বাণিজ্যিক সমাধানকারী প্রয়োজন ४. বৃহৎ-স্কেল সমস্যায় কৌশল স্থান এখনও বড় হতে পারে

ভবিষ্যত দিকনির্দেশনা

१. আরও বিস্তৃত অপ্টিমাইজেশন সমস্যা প্রকারে সম্প্রসারণ করুন २. প্রশিক্ষণ ডেটার উপর নির্ভরতা হ্রাস করুন ३. কৌশল উৎপাদন দক্ষতা আরও উন্নত করুন ४. তত্ত্বাবধানহীন বা আধা-তত্ত্বাবধানহীন শেখার পদ্ধতি অন্বেষণ করুন

গভীর মূল্যায়ন

সুবিধা

१. শক্তিশালী উদ্ভাবনী: প্রথমবারের মতো MILP মডেল হ্রাসে পছন্দ শেখা সিস্টেমেটিকভাবে প্রবর্তন করে २. দৃঢ় তাত্ত্বিক ভিত্তি: পরিচালনা গবেষণা তত্ত্বের মডেল হ্রাস ধারণার উপর ভিত্তি করে ३. ব্যাপক পরীক্ষা: একাধিক বাস্তব ডেটাসেটে যাচাই, শিল্প-স্তরের সমস্যা অন্তর্ভুক্ত ४. উল্লেখযোগ্য কর্মক্ষমতা: বিদ্যমান পদ্ধতির তুলনায় উল্লেখযোগ্য উন্নতি অর্জন করে ५. ভাল ব্যাখ্যাযোগ্যতা: হ্রাসকৃত মডেল ব্যাখ্যাযোগ্য অপারেশনাল মোডের সাথে সামঞ্জস্যপূর্ণ

অপূর্ণতা

१. প্রয়োগের পরিধি সীমিত: প্রধানত প্যারামিটারাইজড MILP সমস্যার জন্য প্রযোজ্য २. প্রশিক্ষণ খরচ: এখনও বড় পরিমাণ মনোনীত ডেটা (সর্বোত্তম সমাধান) প্রয়োজন ३. তাত্ত্বিক বিশ্লেষণ অপর্যাপ্ত: সংযোগ এবং সাধারণীকরণ ক্ষমতার তাত্ত্বিক গ্যারান্টি অভাব ४. সীমিত তুলনা ভিত্তি: প্রধানত একটি শেখার পদ্ধতির (MLOPT) সাথে তুলনা

প্রভাব

१. একাডেমিক অবদান: ML4CO ক্ষেত্রে নতুন গবেষণা দিকনির্দেশনা প্রদান করে २. ব্যবহারিক মূল্য: শিল্প MILP সমাধানে সরাসরি প্রয়োগের সম্ভাবনা ३. পুনরুৎপাদনযোগ্যতা: পদ্ধতি বর্ণনা বিস্তারিত, পরীক্ষামূলক সেটআপ স্পষ্ট ४. অনুপ্রেরণামূলক তাৎপর্য: পছন্দ শেখার ধারণা অন্যান্য অপ্টিমাইজেশন সমস্যায় সম্প্রসারণযোগ্য

প্রযোজ্য পরিস্থিতি

१. অনলাইন স্টোকাস্টিক পরিকল্পনা: অনুরূপ MILP উদাহরণ দ্রুত সমাধানের প্রয়োজন २. সরবরাহ শৃঙ্খল অপ্টিমাইজেশন: প্যারামিটার পরিবর্তন কিন্তু কাঠামো নির্ধারিত সমস্যা ३. রিয়েল-টাইম সময়সূচী: সমাধান সময়ের জন্য কঠোর প্রয়োজনীয়তা সহ প্রয়োগ ४. বৃহৎ-স্কেল শিল্প অপ্টিমাইজেশন: বাণিজ্যিক সমাধানকারী পরিচালনা করতে পারে না এমন সমস্যা

সংদর্ভ

পেপারটি এই ক্ষেত্রের গুরুত্বপূর্ণ কাজ উদ্ধৃত করে, যার মধ্যে রয়েছে:

Bengio, Lodi, এবং Prouvost (२०२१): সমন্বয় অপ্টিমাইজেশনের জন্য ML সমীক্ষা
Bertsimas এবং Stellato (२०२२): অনলাইন মিশ্র-পূর্ণসংখ্যা অপ্টিমাইজেশন
Misra, Roald, এবং Ng (२०२२): সীমাবদ্ধ অপ্টিমাইজেশনের জন্য শেখা
এবং প্রচুর সম্পর্কিত প্রান্ত-থেকে-প্রান্ত শেখা এবং শেখার অপ্টিমাইজেশন পদ্ধতি সাহিত্য

সামগ্রিক মূল্যায়ন: এটি ML4CO ক্ষেত্রে একটি উচ্চ-মানের গবেষণা পেপার যা উদ্ভাবনী পছন্দ শেখার পদ্ধতি প্রস্তাব করে। যদিও কিছু সীমাবদ্ধতা রয়েছে, তবে এর তাত্ত্বিক অবদান এবং ব্যবহারিক মূল্য উভয়ই অত্যন্ত বিশিষ্ট, বৃহৎ-স্কেল MILP সমাধানের জন্য নতুন কার্যকর পথ প্রদান করে।