論文の概要: Tightening Discretization-based MILP Models for the Pooling Problem
using Upper Bounds on Bilinear Terms
- arxiv url: http://arxiv.org/abs/2207.03699v1
- Date: Fri, 8 Jul 2022 05:28:59 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-14 08:28:12.024947
- Title: Tightening Discretization-based MILP Models for the Pooling Problem
using Upper Bounds on Bilinear Terms
- Title(参考訳): 双線型項上の上限を用いたプーリング問題の引き締め離散化に基づくミルプモデル
- Authors: Yifu Chen, Christos T. Maravelias, Xiaomin Zhang
- Abstract要約: 線形項による非最適化問題の解法として,離散化に基づく手法が提案されている。
本稿では,離散化に基づくMILPモデルを用いてプール問題の解法を提案する。
- 参考スコア(独自算出の注目度): 2.6253445491808307
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Discretization-based methods have been proposed for solving nonconvex
optimization problems with bilinear terms. These methods convert the original
nonconvex optimization problems into mixed-integer linear programs (MILPs).
Compared to a wide range of studies related to methods to convert nonconvex
optimization problems into MILPs, research on tightening the resulting MILP
models is limited. In this paper, we present tightening constraints for the
discretization-based MILP models for the pooling problem. Specifically, we
study tightening constraints derived from upper bounds on bilinear term and
exploiting the structures resulting from the discretization. We demonstrate the
effectiveness of our constraints, showing computational results for MILP models
derived from different formulations for (1) the pooling problem and (2)
discretization-based pooling models. Computational results show that our
methods reduce the computational time for MILP models on CPLEX 12.10. Finally,
we note that while our methods are presented in the context of the pooling
problem, they can be extended to address other nonconvex optimization problems
with upper bounds on bilinear terms.
- Abstract(参考訳): 非凸最適化問題を双線型項で解くために離散化に基づく手法が提案されている。
これらの手法は、元の非凸最適化問題を混合整数線形プログラム(MILP)に変換する。
非凸最適化問題をMILPに変換する手法に関する幅広い研究と比較して、結果のMILPモデルの強化に関する研究は限られている。
本稿では,プール問題に対する離散化に基づくMILPモデルの厳密化制約について述べる。
具体的には, 双線形項上界から引き起こされる制約の厳密化と, 離散化による構造の利用について検討する。
この制約の有効性を実証し,(1)プーリング問題,(2)離散化型プーリングモデルについて異なる定式化から導出したmilpモデルの計算結果を示す。
計算結果から,本手法はcplex 12.10におけるミルプモデルの計算時間を短縮することを示した。
最後に,本手法はプール問題の文脈で提案されるが,双線型項上の上限を持つ他の非凸最適化問題に対処するために拡張可能であることに留意する。
関連論文リスト
- Pushing the Limits of Large Language Model Quantization via the Linearity Theorem [71.3332971315821]
本稿では,階層的$ell$再構成誤差と量子化によるモデルパープレキシティ増加との直接的な関係を確立する「線形定理」を提案する。
この知見は,(1)アダマール回転とHIGGSと呼ばれるMSE最適格子を用いた単純なデータフリーLCM量子化法,(2)非一様層ごとの量子化レベルを求める問題に対する最適解の2つの新しい応用を可能にする。
論文 参考訳(メタデータ) (2024-11-26T15:35:44Z) - Maximum a Posteriori Inference for Factor Graphs via Benders' Decomposition [0.38233569758620056]
一般ベイズ因子モデルにおける最大a-ポストペリオーリ推定法を提案する。
ベイジアン・ガウス混合モデルと潜在ディリクレ割り当てに対するMAP推定アルゴリズムを導出する。
論文 参考訳(メタデータ) (2024-10-24T19:57:56Z) - Total Uncertainty Quantification in Inverse PDE Solutions Obtained with Reduced-Order Deep Learning Surrogate Models [50.90868087591973]
機械学習サロゲートモデルを用いて得られた逆PDE解の総不確かさを近似したベイズ近似法を提案する。
非線型拡散方程式に対する反復的アンサンブルスムーズおよび深層アンサンブル法との比較により,提案手法を検証した。
論文 参考訳(メタデータ) (2024-08-20T19:06:02Z) - Optimized QUBO formulation methods for quantum computing [0.4999814847776097]
実世界の金融シナリオにインスパイアされたNPハード最適化問題に対して,我々の手法を適用する方法について述べる。
2つのD波量子異方体にこの問題の事例を提出し、これらのシナリオで使用される標準手法と新しい手法の性能を比較した。
論文 参考訳(メタデータ) (2024-06-11T19:59:05Z) - Feature selection in linear SVMs via a hard cardinality constraint: a scalable SDP decomposition approach [3.7876216422538485]
本稿では, 線形支援ベクトルマシン(SVM)において, 濃度制約が適用された場合の組込み特徴選択問題について検討する。
この問題は、元の線形SVMが時間内に解決可能な問題に等しいにもかかわらず、濃度制約が存在するためNPハードである。
この問題に対処するために、まず2つの混合整数式を導入し、新しい半定緩和法を提案する。
論文 参考訳(メタデータ) (2024-04-15T19:15:32Z) - 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) - Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
本稿では,低ランク構造制約下でのグラフ学習のためのフレキシブルなアルゴリズムフレームワークを提案する。
この問題は楕円分布のペナルティ化された最大推定値として表される。
楕円モデルによく適合する正定行列と定ランクの正半定行列のジオメトリを利用する。
論文 参考訳(メタデータ) (2022-10-21T13:19:45Z) - Conditional gradient methods for stochastically constrained convex
minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。
私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。
提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文 参考訳(メタデータ) (2020-07-07T21:26:35Z) - Consistent Second-Order Conic Integer Programming for Learning Bayesian
Networks [2.7473982588529653]
連続観測データからBNのスパースDAG構造を学習する問題について検討する。
この数学的プログラムの最適解は、ある条件下では望ましい統計的性質を持つことが知られている。
ほぼ最適解を得るために, 分岐・結合プロセスの終了に向け, 早期停止条件を提案する。
論文 参考訳(メタデータ) (2020-05-29T00:13:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。