論文の概要: Constraint Matters: Multi-Modal Representation for Reducing Mixed-Integer Linear programming
- arxiv url: http://arxiv.org/abs/2508.18742v1
- Date: Tue, 26 Aug 2025 07:15:38 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-08-27 17:42:38.721315
- Title: Constraint Matters: Multi-Modal Representation for Reducing Mixed-Integer Linear programming
- Title（参考訳）: 制約事項:混合整数線形プログラミングのマルチモーダル表現
- Authors: Jiajun Li, Ran Hou, Yu Ding, Yixuan Li, Shisi Guan, Jiahui Duan, Xiongwei Han, Tao Zhong, Vincent Chau, Weiwei Wu, Wanyuan Wang,
- Abstract要約: 本稿では,MILPのための制約に基づく新しいモデル縮小手法を提案する。
提案手法は, 解法の品質を50%以上改善し, 時間を17.47%短縮することを示した。
- 参考スコア（独自算出の注目度）: 30.037594153262273
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Model reduction, which aims to learn a simpler model of the original mixed integer linear programming (MILP), can solve large-scale MILP problems much faster. Most existing model reduction methods are based on variable reduction, which predicts a solution value for a subset of variables. From a dual perspective, constraint reduction that transforms a subset of inequality constraints into equalities can also reduce the complexity of MILP, but has been largely ignored. Therefore, this paper proposes a novel constraint-based model reduction approach for the MILP. Constraint-based MILP reduction has two challenges: 1) which inequality constraints are critical such that reducing them can accelerate MILP solving while preserving feasibility, and 2) how to predict these critical constraints efficiently. To identify critical constraints, we first label these tight-constraints at the optimal solution as potential critical constraints and design a heuristic rule to select a subset of critical tight-constraints. To learn the critical tight-constraints, we propose a multi-modal representation technique that leverages information from both instance-level and abstract-level MILP formulations. The experimental results show that, compared to the state-of-the-art methods, our method improves the quality of the solution by over 50\% and reduces the computation time by 17.47\%.
- Abstract（参考訳）: モデル還元は、従来の混合整数線形計画法(MILP)のより単純なモデルを学ぶことを目的としており、大規模なMILP問題をより高速に解くことができる。
既存のモデル還元法の多くは変数のサブセットに対する解値を予測する変数還元に基づいている。
双対の観点からは、不等式制約のサブセットを等式に変換する制約還元はMILPの複雑さを減少させるが、ほとんど無視されている。
そこで本研究では,MILPのための制約に基づく新しいモデル縮小手法を提案する。
制約に基づくMILP削減には2つの課題がある。
1)不等式制約が重要であり、その軽減は、実現可能性を維持しつつMILP解決を加速し得ること、
2)これらの臨界制約を効率的に予測する方法。
臨界制約を特定するために、まず、最適解におけるこれらの厳密制約を潜在的臨界制約としてラベル付けし、臨界厳密制約のサブセットを選択するヒューリスティックルールを設計する。
批判的制約を学習するために、インスタンスレベルおよび抽象レベルのMILP定式化からの情報を活用するマルチモーダル表現手法を提案する。
実験の結果, 最先端手法と比較して, 解の質を50%以上改善し, 計算時間を17.47倍に短縮することがわかった。
関連論文リスト
- Conformal Mixed-Integer Constraint Learning with Feasibility Guarantees [0.3058340744328236]
Conformal Mixed-Integer Constraint Learningは、最適化問題におけるデータ駆動制約の確率論的実現可能性を保証する。
我々は,C-MICLが目標レートを一貫して達成し,競争目標性能を維持し,既存の手法に比べて計算コストを大幅に削減することを示す。
論文 参考訳（メタデータ） (2025-06-04T03:26:31Z) - Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
本稿では、目的関数と制約関数の両方が弱凸である問題の重要な部分集合について検討する。
既存の手法では、収束速度の遅さや二重ループ設計への依存など、しばしば制限に直面している。
これらの課題を克服するために,新しい単一ループペナルティに基づくアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-04-21T17:15:48Z) - Fast and Interpretable Mixed-Integer Linear Program Solving by Learning Model Reduction [24.3088703166792]
本稿では,MILPの縮小モデルと等価モデルを中間段階として学習することを目的とする。
縮小モデルはしばしば解釈可能な操作に対応しており、既存の商用解法よりもはるかに高速に大規模MILP問題を解くことができる。
本稿では,モデル縮小学習タスクの性能向上に寄与する嗜好情報を捕捉し,表現するための注意機構を提案する。
論文 参考訳（メタデータ） (2024-12-31T06:50:42Z) - Alternating Minimization Schemes for Computing Rate-Distortion-Perception Functions with $f$-Divergence Perception Constraints [10.564071872770146]
離散メモリレスソースに対するRDPF(Ralse-Distortion-Perception Function)の計算について検討した。
最適パラメトリック解を特徴付ける。
歪みと知覚制約について十分な条件を提供する。
論文 参考訳（メタデータ） (2024-08-27T12:50:12Z) - Learning Constrained Optimization with Deep Augmented Lagrangian Methods [54.22290715244502]
機械学習(ML)モデルは、制約付き最適化ソルバをエミュレートするために訓練される。
本稿では,MLモデルを用いて2つの解推定を直接予測する手法を提案する。
これにより、双対目的が損失関数であるエンドツーエンドのトレーニングスキームと、双対上昇法をエミュレートした原始的実現可能性への解推定を可能にする。
論文 参考訳（メタデータ） (2024-03-06T04:43:22Z) - Double Duality: Variational Primal-Dual Policy Optimization for
Constrained Reinforcement Learning [132.7040981721302]
本研究では,訪問尺度の凸関数を最小化することを目的として,制約付き凸決定プロセス(MDP)について検討する。
制約付き凸MDPの設計アルゴリズムは、大きな状態空間を扱うなど、いくつかの課題に直面している。
論文 参考訳（メタデータ） (2024-02-16T16:35:18Z) - Orthogonal Nonnegative Matrix Factorization with Sparsity Constraints [0.0]
本稿では,空間制約付き直交非負行列因子分解(SCONMF)問題に対する新しいアプローチを提案する。
容量制約のある施設配置問題としてSCONMFを再構成することにより, 提案手法は非負性, 直交性, 疎性制約を自然に統合する。
具体的には,動的最適制御設計問題に使用される制御バリア関数(CBF)に基づくフレームワークと,施設配置問題に使用される最大エントロピー原理に基づくフレームワークを統合し,ロバストな因子化を確保しつつ,これらの制約を強制する。
論文 参考訳（メタデータ） (2022-10-06T04:30:59Z) - Tightening Discretization-based MILP Models for the Pooling Problem
using Upper Bounds on Bilinear Terms [2.6253445491808307]
線形項による非最適化問題の解法として,離散化に基づく手法が提案されている。
本稿では,離散化に基づくMILPモデルを用いてプール問題の解法を提案する。
論文 参考訳（メタデータ） (2022-07-08T05:28:59Z) - Algorithm for Constrained Markov Decision Process with Linear
Convergence [55.41644538483948]
エージェントは、そのコストに対する複数の制約により、期待される累積割引報酬を最大化することを目的としている。
エントロピー正規化ポリシーとベイダの二重化という2つの要素を統合した新しい双対アプローチが提案されている。
提案手法は(線形速度で)大域的最適値に収束することが示されている。
論文 参考訳（メタデータ） (2022-06-03T16:26:38Z) - Conditional gradient methods for stochastically constrained convex
minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。
私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。
提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文 参考訳（メタデータ） (2020-07-07T21:26:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。