論文の概要: P-split formulations: A class of intermediate formulations between big-M and convex hull for disjunctive constraints

• arxiv url: http://arxiv.org/abs/2202.05198v1
• Date: Thu, 10 Feb 2022 18:02:16 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-11 17:00:01.925257
• Title: P-split formulations: A class of intermediate formulations between big-M and convex hull for disjunctive constraints
• Title（参考訳）: P-スプリット定式化: 共役制約に対するビッグMと凸殻の間の中間定式化のクラス
• Authors: Jan Kronqvist and Ruth Misener and Calvin Tsay
• Abstract要約: 我々は,大小Mおよび凸容器の定式化と中間の解離的制約に対する混合整数定式化のクラスを開発する。 P$-split" の定式化は、凸加法的に分離可能な制約を$P$パーティションに分割するリフト変換に基づいている。 P$-split の定式化が Big-M 同値から凸包に収束する階層を形成することを示す。
• 参考スコア（独自算出の注目度）: 3.585904984801793
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We develop a class of mixed-integer formulations for disjunctive constraints intermediate to the big-M and convex hull formulations in terms of relaxation strength. The main idea is to capture the best of both the big-M and convex hull formulations: a computationally light formulation with a tight relaxation. The "$P$-split" formulations are based on a lifted transformation that splits convex additively separable constraints into $P$ partitions and forms the convex hull of the linearized and partitioned disjunction. We analyze the continuous relaxation of the $P$-split formulations and show that, under certain assumptions, the formulations form a hierarchy starting from a big-M equivalent and converging to the convex hull. The goal of the $P$-split formulations is to form a strong approximation of the convex hull through a computationally simpler formulation. We computationally compare the $P$-split formulations against big-M and convex hull formulations on 320 test instances. The test problems include K-means clustering, P_ball problems, and optimization over trained ReLU neural networks. The computational results show promising potential of the $P$-split formulations. For many of the test problems, $P$-split formulations are solved with a similar number of explored nodes as the convex hull formulation, while reducing the solution time by an order of magnitude and outperforming big-M both in time and number of explored nodes.
• Abstract（参考訳）: 我々は,big-m と凸包式に中間の分離制約のための混合整数式を緩和強度で開発する。 主なアイデアは、big-m と convex hull の両方の定式化をうまく捉えることである: 密な緩和を伴う計算的に軽い定式化である。 p$-split" の定式化は、凸を付加的に分離可能な制約を $p$ 分割に分割し、線型化および分割された連結の凸包を形成するリフト変換に基づいている。 我々は、$P$-splitの定式化の連続的な緩和を解析し、ある仮定の下で、定式化がビッグM同値から凸包へ収束する階層を形成することを示す。 P$-splitの定式化の目標は、計算的に単純な定式化によって凸殻の強い近似を形成することである。 320のテストインスタンスの big-m および convex hull 式に対する $p$-split 式を比較した。 テスト問題には、k平均クラスタリング、p_ball問題、トレーニングされたreluニューラルネットワークの最適化が含まれる。 計算結果は、$P$-splitの定式化の有望な可能性を示している。 多くのテスト問題に対して、$P$-splitの定式化は凸船体定式化と同様の数の探索ノードで解決されるが、解時間を桁違いに減らし、探索ノードの時間と数の両方でビッグMを上回っている。

関連論文リスト

• Noise-Free Sampling Algorithms via Regularized Wasserstein Proximals [3.4240632942024685]
  ポテンシャル関数が支配する分布からサンプリングする問題を考察する。 本研究は, 決定論的な楽譜に基づくMCMC法を提案し, 粒子に対する決定論的進化をもたらす。
  論文  参考訳（メタデータ） (2023-08-28T23:51:33Z)
• Targeted Separation and Convergence with Kernel Discrepancies [61.973643031360254]
  カーネルベースの不一致測度は、(i)ターゲットPを他の確率測度から分離するか、(ii)Pへの弱収束を制御する必要がある。 本稿では, (i) と (ii) を保証するのに十分な,必要な新しい条件を導出する。 可分距離空間上のMDDに対して、ボヒナー埋め込み可測度を分離するカーネルを特徴づけ、すべての測度を非有界カーネルと分離するための単純な条件を導入する。
  論文  参考訳（メタデータ） (2022-09-26T16:41:16Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。 提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
  論文  参考訳（メタデータ） (2022-02-26T19:10:48Z)
• On the Complexity of a Practical Primal-Dual Coordinate Method [63.899427212054995]
  ランダム・座標降下法(PURE-CD)を用いた原始双対アルゴリズムの複雑性境界を証明した。 バイマックス性能問題を解くための優れた外挿が得られることが示されている。
  論文  参考訳（メタデータ） (2022-01-19T16:14:27Z)
• Posterior-Aided Regularization for Likelihood-Free Inference [23.708122045184698]
  後補助正規化(PAR)は,モデル構造に関係なく,密度推定器の学習に適用可能である。 単一のニューラルネットワークを用いて逆KL項と相互情報項の両方を推定するPARの統一推定方法を提供する。
  論文  参考訳（メタデータ） (2021-02-15T16:59:30Z)
• Partition-based formulations for mixed-integer optimization of trained ReLU neural networks [66.88252321870085]
  本稿では,訓練されたReLUニューラルネットワークのための混合整数式について紹介する。 1つの極端な場合、入力毎に1つのパーティションがノードの凸殻、すなわち各ノードの最も厳密な可能な定式化を回復する。
  論文  参考訳（メタデータ） (2021-02-08T17:27:34Z)
• Between steps: Intermediate relaxations between big-M and convex hull formulations [4.769747792846004]
  我々は, 接点のビッグmと凸包式の間の緩和のクラスを展開する。 提案された "P-split" の定式化は凸をP分割に分割し、分節の凸体を形成する。
  論文  参考訳（メタデータ） (2021-01-29T18:03:15Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)
• MINA: Convex Mixed-Integer Programming for Non-Rigid Shape Alignment [77.38594866794429]
  非剛体形状マッチングのための凸混合整数プログラミングの定式化。 効率的な低次元離散モデルに基づく新しい形状変形モデルを提案する。
  論文  参考訳（メタデータ） (2020-02-28T09:54:06Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。