論文の概要: Learning Mixed-Integer Linear Programs from Contextual Examples
- arxiv url: http://arxiv.org/abs/2107.07136v1
- Date: Thu, 15 Jul 2021 05:45:52 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-17 01:28:00.852375
- Title: Learning Mixed-Integer Linear Programs from Contextual Examples
- Title(参考訳): 実例による混合整数線形プログラムの学習
- Authors: Mohit Kumar, Samuel Kolb, Luc De Raedt and Stefano Teso
- Abstract要約: 混合整数線形プログラム(MILP)は人工知能や運用研究で広く使われている。
本稿では,文脈的事例からMILPを取得することの問題点について考察する。
また、コンテキストサンプルからMILPを学習するアルゴリズムであるMISLEをコントリビュートする。
- 参考スコア(独自算出の注目度): 37.56298025474654
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Mixed-integer linear programs (MILPs) are widely used in artificial
intelligence and operations research to model complex decision problems like
scheduling and routing. Designing such programs however requires both domain
and modelling expertise. In this paper, we study the problem of acquiring MILPs
from contextual examples, a novel and realistic setting in which examples
capture solutions and non-solutions within a specific context. The resulting
learning problem involves acquiring continuous parameters -- namely, a cost
vector and a feasibility polytope -- but has a distinctly combinatorial flavor.
To solve this complex problem, we also contribute MISSLE, an algorithm for
learning MILPs from contextual examples. MISSLE uses a variant of stochastic
local search that is guided by the gradient of a continuous surrogate loss
function. Our empirical evaluation on synthetic data shows that MISSLE acquires
better MILPs faster than alternatives based on stochastic local search and
gradient descent.
- Abstract(参考訳): 混合整数線形プログラム(MILP)は、スケジューリングやルーティングといった複雑な決定問題をモデル化するために人工知能や運用研究で広く使われている。
しかし、そのようなプログラムを設計するにはドメインとモデリングの両方の専門知識が必要です。
本稿では,事例が特定の文脈内で解や非解をキャプチャする,新しい,現実的な環境である文脈的事例からMILPを取得するという課題について考察する。
結果として生じる学習問題は、コストベクターと実現可能なポリトープという、連続的なパラメータを取得することである。
この複雑な問題を解決するために、コンテキストサンプルからMILPを学習するアルゴリズムであるMISLEも提案する。
MISSLEは、連続的な代理損失関数の勾配によって導かれる確率的局所探索の変種を用いる。
合成データに対する経験的評価から,確率的局所探索と勾配降下により,ミスルは代替品よりも優れたミルプを高速に獲得できることがわかった。
関連論文リスト
- Learning to Configure Mathematical Programming Solvers by Mathematical
Programming [0.8075866265341176]
本稿では,与えられた問題の特定の事例に対して,優れた数学的プログラミング解法構成を求める問題について論じる。
優れたソルバ構成を学ぶことの難しさは、パラメータ設定がすべて独立しているとは限らないことである。
このアプローチの第2段階でこの問題に対処し、学習した情報を用いて最適化問題を構築し、解決する。
論文 参考訳(メタデータ) (2024-01-10T10:02:01Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳(メタデータ) (2023-10-08T23:39:38Z) - A Deep Instance Generative Framework for MILP Solvers Under Limited Data
Availability [66.37474135424637]
我々は、MILPインスタンスのための最初の深層生成フレームワークであるG2MILPを提案する。
G2MILPはMILPインスタンスを二部グラフとして表現し、マスク付き変分オートエンコーダを元のグラフの一部を反復的に破損させ、置き換えて新しいグラフを生成する。
生成されたMILPインスタンスの品質を評価するためのベンチマークスイートを設計する。
論文 参考訳(メタデータ) (2023-10-04T13:34:34Z) - Online Distributed Learning over Random Networks [1.119697400073873]
本研究は, 実運用による課題として, (i) オンライン学習, (i) ローカルデータの時間的変化, (ii) 非同期エージェントの計算, (iii) 信頼性の低い限られた通信, (iv) ローカルの計算を不正確に行うことに焦点を当てる。
マルチプライヤの交互方向法(ADMM)の分散演算子理論(DOT)版を紹介する。
我々は,凸学習の問題に収束することが証明された。
論文 参考訳(メタデータ) (2023-09-01T15:18:05Z) - Tackling Diverse Minorities in Imbalanced Classification [80.78227787608714]
不均衡データセットは、様々な現実世界のアプリケーションで一般的に見られ、分類器の訓練において重要な課題が提示されている。
マイノリティクラスとマイノリティクラスの両方のデータサンプルを混合することにより、反復的に合成サンプルを生成することを提案する。
提案するフレームワークの有効性を,7つの公開ベンチマークデータセットを用いて広範な実験により実証する。
論文 参考訳(メタデータ) (2023-08-28T18:48:34Z) - RetICL: Sequential Retrieval of In-Context Examples with Reinforcement
Learning [77.34726150561087]
In-Context Learning (RetICL) のための検索式を提案する。
我々は、マルコフ決定プロセスとして逐次サンプル選択の問題を定義し、LSTMを用いてサンプルレトリバーモデルを設計し、近似ポリシー最適化を用いてそれを訓練する。
論文 参考訳(メタデータ) (2023-05-23T20:15:56Z) - Global and Preference-based Optimization with Mixed Variables using
Piecewise Affine Surrogates [1.30536490219656]
本稿では,線形制約付き混合変数問題の解法として,新しいサロゲートに基づく大域的最適化アルゴリズムを提案する。
本稿では,2種類の探索関数を導入し,混合整数線形計画解法を用いて実現可能な領域を効率的に探索する。
提案アルゴリズムは,既存の手法よりもよく,あるいは同等の結果が得られることが多い。
論文 参考訳(メタデータ) (2023-02-09T15:04:35Z) - Provable Reinforcement Learning with a Short-Term Memory [68.00677878812908]
我々はPMDPsの新しいサブクラスについて研究し、その潜在状態は、最近の短い長さ$m$の履歴によって復号化することができる。
特に、リッチ・オブザーブレーション・セッティングにおいて、指数関数的にスケールするサンプル複雑性を持つ新しい「モーメントマッチング」アプローチを用いて、新しいアルゴリズムを開発する。
以上の結果から,これらの環境下での強化学習には短期記憶が十分であることが示唆された。
論文 参考訳(メタデータ) (2022-02-08T16:39:57Z) - Minimizing Entropy to Discover Good Solutions to Recurrent Mixed Integer
Programs [0.0]
混合整数プログラミング(MIP)問題に対する現在の解法は、幅広い問題に対して良好に動作するように設計されている。
近年の研究では、機械学習(ML)をMIPソルバと統合してドメイン知識を注入し、最適性ギャップを効率的に閉じることが示されている。
本稿では、エントロピーの概念を用いて、最小限のトレーニングデータとチューニングで効率的にモデルを構築するオンラインソルバを提案する。
論文 参考訳(メタデータ) (2022-02-07T18:52:56Z) - Knowledge engineering mixed-integer linear programming: constraint
typology [2.4002205752931625]
混合整数線形プログラムMILPの制約型について検討する。
milpは、実生活のスケジューリング、ルーティング、計画、リソース割り当て、時間的最適化問題のモデリングと解決によく使われる数学的プログラミング手法である。
論文 参考訳(メタデータ) (2021-02-20T20:07:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。