論文の概要: Solve Smart, Not Often: Policy Learning for Costly MILP Re-solving
- arxiv url: http://arxiv.org/abs/2509.23470v1
- Date: Sat, 27 Sep 2025 19:47:15 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-09-30 22:32:19.246471
- Title: Solve Smart, Not Often: Policy Learning for Costly MILP Re-solving
- Title（参考訳）: 賢く解決する - コストのかかるMILP再解決のための政策学習
- Authors: Rui Ai, Hugo De Oliveira Barbalho, Sirui Li, Alexei Robsky, David Simchi-Levi, Ishai Menache,
- Abstract要約: リアルタイム操作における一般的な課題は、最適化問題を再解決するか、既存のソリューションを使い続けるかを決定することである。
本稿では,変化点検出を用いた近似政策最適化というフレームワークを提案する。
- 参考スコア（独自算出の注目度）: 18.62245790631018
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A common challenge in real-time operations is deciding whether to re-solve an optimization problem or continue using an existing solution. While modern data platforms may collect information at high frequencies, many real-time operations require repeatedly solving computationally intensive optimization problems formulated as Mixed-Integer Linear Programs (MILPs). Determining when to re-solve is, therefore, an economically important question. This problem poses several challenges: 1) How to characterize solution optimality and solving cost; 2) How to detect environmental changes and select beneficial samples for solving the MILP; 3) Given the large time horizon and non-MDP structure, vanilla reinforcement learning (RL) methods are not directly applicable and tend to suffer from value function explosion. Existing literature largely focuses on heuristics, low-data settings, and smooth objectives, with little focus on common NP-hard MILPs. We propose a framework called Proximal Policy Optimization with Change Point Detection (POC), which systematically offers a solution for balancing performance and cost when deciding appropriate re-solving times. Theoretically, we establish the relationship between the number of re-solves and the re-solving cost. To test our framework, we assemble eight synthetic and real-world datasets, and show that POC consistently outperforms existing baselines by 2%-17%. As a side benefit, our work fills the gap in the literature by introducing real-time MILP benchmarks and evaluation criteria.
- Abstract（参考訳）: リアルタイム操作における一般的な課題は、最適化問題を再解決するか、既存のソリューションを使い続けるかを決定することである。
現代のデータプラットフォームは高頻度で情報を集めることができるが、多くのリアルタイム操作では、MILP(Mixed-Integer Linear Programs)と呼ばれる計算集約的な最適化問題を繰り返し解決する必要がある。
再解決の時期を決定することは経済的に重要な問題である。
この問題にはいくつかの課題がある。
1) 解の最適性と解決コストを特徴づける方法
2 環境変化の検知方法及びMILP解決のための有用なサンプルの選択方法
3) 大きな時間的地平線と非MDP構造を考えると,バニラ強化学習(RL)法は直接適用されず,付加価値関数の爆発に悩まされる傾向にある。
既存の文献は主にヒューリスティックス、低データ設定、スムーズな目的に焦点を当てており、一般的なNPハードMILPにはほとんど焦点を当てていない。
本稿では, 適切な再解決時間を決定する際に, 性能とコストのバランスをとるためのソリューションを体系的に提供するPOC(Proximal Policy Optimization with Change Point Detection)というフレームワークを提案する。
理論的には,再解決数と再解決コストの関係を確立する。
フレームワークをテストするため、8つの合成および実世界のデータセットを収集し、POCが既存のベースラインを2%-17%上回っていることを示す。
副次的な利点として、リアルタイムMILPベンチマークと評価基準を導入することにより、文献のギャップを埋める。
関連論文リスト
- Learning to Refine: Self-Refinement of Parallel Reasoning in LLMs [102.48588475875749]
本稿では,新しい並列テスト時間スケーリングフレームワークであるGenerative Self-Refinement (GSR)を紹介する。
GSRは一連の候補応答を並列に生成し、その後自己精製を行い、新しい優れた解を合成する。
提案手法は,5つの数学ベンチマークにおいて,最先端性能を実現する。
論文 参考訳（メタデータ） (2025-08-27T06:51:48Z) - A Heuristic Algorithm Based on Beam Search and Iterated Local Search for the Maritime Inventory Routing Problem [0.45152963243489175]
海運インベントリ問題(MIRP)は、世界の海運レベルの統合において重要な役割を担っている。
MIRPは世界海運水準の統合において重要な役割を担っている。
大規模なMIRPインスタンスやその変種を効率的に解決できる、確立された方法論はいまだに存在しない。
論文 参考訳（メタデータ） (2025-05-17T22:40:36Z) - Autoformulation of Mathematical Optimization Models Using LLMs [50.030647274271516]
本稿では,自然言語問題記述から解法対応最適化モデルを自動生成する,$textitautoformulation$の問題にアプローチする。
オートフォーミュレーションの3つの主要な課題を識別する: $textit(1)$ 巨大で問題に依存した仮説空間、および$textit(2)$ 不確実性の下でこの空間を効率的かつ多様に探索する。
我々は,$textitLarge Language Models$と$textitMonte-Carlo Tree Search$を併用した新しい手法を提案する。
論文 参考訳（メタデータ） (2024-11-03T20:41:38Z) - Automatic MILP Solver Configuration By Learning Problem Similarities [1.1585113506994469]
混合線形プログラム(MILP)は、内部アルゴリズムを制御するために多数の構成パラメータを公開する。
我々は,探索・評価設定のオーバーヘッドを伴わずに,低コストなソリューションを実現する未確認問題インスタンスの構成パラメータを予測することを目的としている。
1つのソルバ構成で同様のコストを持つインスタンスも、同じランタイム環境で別のソルバ構成で同様のコストを持つことを示す。
論文 参考訳（メタデータ） (2023-07-02T21:31:47Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳（メタデータ） (2022-01-28T05:53:28Z) - Solving Multistage Stochastic Linear Programming via Regularized Linear
Decision Rules: An Application to Hydrothermal Dispatch Planning [77.34726150561087]
AdaSO(Adaptive least absolute shrinkage and selection operator)に基づく線形決定規則(LDR)の新しい正規化手法を提案する。
実験により、MSLPを解くために古典的な非正規化LDRを使用する場合、過度に適合する脅威は無視できないことが示された。
LHDP問題に対しては、非正規化ベンチマークと比較して、提案したフレームワークの次の利点を強調した。
論文 参考訳（メタデータ） (2021-10-07T02:36:14Z) - Learning to Schedule Heuristics in Branch-and-Bound [25.79025327341732]
現実世界のアプリケーションは通常、迅速な意思決定を可能にするために、検索の早い段階で優れたソリューションを見つける必要があります。
正確なMIPソルバにおけるスケジューリングのための最初のデータ駆動フレームワークを提案する。
最先端の学術MIPソルバーのデフォルト設定と比較して、挑戦的なインスタンスのクラスで平均プライマリ積分を最大49%削減することができます。
論文 参考訳（メタデータ） (2021-03-18T14:49:52Z) - Contrastive Losses and Solution Caching for Predict-and-Optimize [19.31153168397003]
ノイズコントラスト法を用いて、サロゲート損失関数の族を動機付ける。
すべての予測と最適化アプローチのボトルネックに対処する。
非常に遅い成長率でさえ、最先端の手法の質に合わせるのに十分であることを示す。
論文 参考訳（メタデータ） (2020-11-10T19:09:12Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳（メタデータ） (2020-07-14T12:38:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。