論文の概要: Learning to Solve Integer Linear Programs with Davis-Yin Splitting
- arxiv url: http://arxiv.org/abs/2301.13395v3
- Date: Thu, 21 Mar 2024 13:16:27 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-22 20:39:25.455612
- Title: Learning to Solve Integer Linear Programs with Davis-Yin Splitting
- Title(参考訳): Davis-Yin 分割による整数線形プログラムの解法
- Authors: Daniel McKenzie, Samy Wu Fung, Howard Heaton,
- Abstract要約: 現代の凸最適化のアイデアに基づいて、何千もの変数の問題に懸命にスケールするネットワークとトレーニングスキームを設計する。
提案手法は,最短経路問題とknapsack問題という2つの代表的な問題に対して,計算上の優位性を検証した。
- 参考スコア(独自算出の注目度): 5.199570417938866
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In many applications, a combinatorial problem must be repeatedly solved with similar, but distinct parameters. Yet, the parameters $w$ are not directly observed; only contextual data $d$ that correlates with $w$ is available. It is tempting to use a neural network to predict $w$ given $d$. However, training such a model requires reconciling the discrete nature of combinatorial optimization with the gradient-based frameworks used to train neural networks. When the problem in question is an Integer Linear Program (ILP), one approach to overcome this training issue is to consider a continuous relaxation of the combinatorial problem. While existing methods utilizing this approach have shown to be highly effective on small problems, they do not always scale well to large problems. In this work, we draw on ideas from modern convex optimization to design a network and training scheme which scales effortlessly to problems with thousands of variables. Our experiments verify the computational advantage our proposed method enjoys on two representative problems, namely the shortest path problem and the knapsack problem.
- Abstract(参考訳): 多くの応用において、組合せ問題は類似しているが異なるパラメータで繰り返し解決されなければならない。
しかし、パラメータ$w$は直接観測されておらず、$w$と相関するコンテキストデータ$d$のみが利用可能である。
ニューラルネットワークを使って$d$の$w$を予測する傾向があります。
しかし、そのようなモデルをトレーニングするには、ニューラルネットワークのトレーニングに使用される勾配ベースのフレームワークと組み合わせ最適化の離散的な性質を調整する必要がある。
問題となるのが整数線形プログラム(ILP)の場合、このトレーニング問題を克服するための一つのアプローチは、組合せ問題の継続的な緩和を考えることである。
このアプローチを利用した既存の手法は、小さな問題に対して非常に効果的であることが示されているが、必ずしも大きな問題に対してうまくスケールするとは限らない。
本研究では,最新の凸最適化から,数千の変数を扱う問題に対して無駄にスケールするネットワークとトレーニングスキームを設計するためのアイデアを導出する。
提案手法は,最短経路問題とknapsack問題という2つの代表的な問題に対して,計算上の優位性を検証した。
関連論文リスト
- Matching the Statistical Query Lower Bound for k-sparse Parity Problems with Stochastic Gradient Descent [83.85536329832722]
勾配勾配降下(SGD)は,$d$次元ハイパーキューブ上の$k$パリティ問題を効率的に解くことができることを示す。
次に、SGDでトレーニングされたニューラルネットワークがどのようにして、小さな統計的エラーで$k$-parityの問題を解決するかを実証する。
論文 参考訳(メタデータ) (2024-04-18T17:57:53Z) - What to Do When Your Discrete Optimization Is the Size of a Neural
Network? [24.546550334179486]
ニューラルネットワークを用いた機械学習アプリケーションは、離散最適化問題を解くことを含む。
離散的な設定で使用される古典的なアプローチは、大きなニューラルネットワークに対してうまくスケールしない。
連続経路(CP)法は,前者およびモンテカルロ法(MC)法を純粋に表現し,後者を表現している。
論文 参考訳(メタデータ) (2024-02-15T21:57:43Z) - 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) - Landscape Surrogate: Learning Decision Losses for Mathematical
Optimization Under Partial Information [48.784330281177446]
学習統合最適化の最近の研究は、最適化が部分的にのみ観察される場合や、専門家のチューニングなしに汎用性が不十分な環境では有望であることを示している。
本稿では,$fcirc mathbfg$の代替として,スムーズで学習可能なランドスケープサロゲートを提案する。
このサロゲートはニューラルネットワークによって学習可能で、$mathbfg$ソルバよりも高速に計算でき、トレーニング中に密度が高く滑らかな勾配を提供し、目に見えない最適化問題に一般化でき、交互最適化によって効率的に学習される。
論文 参考訳(メタデータ) (2023-07-18T04:29:16Z) - Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise
Learning [65.54757265434465]
ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。
オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。
本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
論文 参考訳(メタデータ) (2021-11-23T18:10:48Z) - Deep learning for inverse problems with unknown operator [0.0]
フォワード演算子$T$が未知の逆問題では、関数$f_i$とノイズの多いイメージ$Tf_i$からなるトレーニングデータにアクセスできます。
本稿では,データに最小限の仮定を必要とする新しい手法を提案し,学習点数と雑音レベルに依存する再現率を示す。
論文 参考訳(メタデータ) (2021-08-05T17:21:12Z) - Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel
Optimization [62.87181271021217]
機械学習に多くの応用がある非SBO問題を考察する。
本稿では,非SBO問題に対する高速ランダム化アルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-05-05T18:28:42Z) - On the Treatment of Optimization Problems with L1 Penalty Terms via
Multiobjective Continuation [0.0]
本稿では,線形・非線形最適化におけるスパース性の影響を詳細に把握するアルゴリズムを提案する。
本手法は非線形の場合に対する線形回帰問題に対するよく知られたホモトピー法の一般化と見なすことができる。
論文 参考訳(メタデータ) (2020-12-14T13:00:50Z) - Divide and Learn: A Divide and Conquer Approach for Predict+Optimize [50.03608569227359]
予測+最適化問題は、予測係数を使用する最適化プロブレムと、確率係数の機械学習を組み合わせる。
本稿では, 予測係数を1次線形関数として, 最適化問題の損失を直接表現する方法を示す。
本稿では,この制約を伴わずに最適化問題に対処し,最適化損失を用いてその係数を予測する新しい分割アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-12-04T00:26:56Z) - Curriculum learning for multilevel budgeted combinatorial problems [7.804994311050265]
マルチレベル最適化問題はそれらの一般化であり、複数のプレイヤーが逐次決定を下す状況を含んでいる。
グラフ上のゼロサムゲームにおいて、2人のプレイヤーが関与する多段階の予算問題を解決するための価値ベース手法を考案する。
我々のフレームワークは単純なカリキュラムに基づいており、もしエージェントが$B$までの予算を持つインスタンスの価値を見積もる方法を知っているなら、可能なすべての余剰状態の方向に関係なく、予算が$B+1$のインスタンスを時間内に解決することができる。
論文 参考訳(メタデータ) (2020-07-07T01:09:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。