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

• arxiv url: http://arxiv.org/abs/2202.05198v2
• Date: Mon, 27 May 2024 12:41:17 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-01 00:29:19.895020
• Title: P-split formulations: A class of intermediate formulations between big-M and convex hull for disjunctive constraints
• Title（参考訳）: P-スプリットの定式化: 共役制約に対するBig-Mと凸殻の間の中間定式化のクラス
• Authors: Jan Kronqvist, Ruth Misener, Calvin Tsay,
• Abstract要約: P-スプリット」の定式化は、各不定形内の凸制約を伴う不定形制約に対して導出される。 P-スプリットの定式化は、大質量M等式から始まり、凸殻に収束する階層を形成する。 344 の試験インスタンス上での P-split の定式化と Big-M および convex の定式化を計算的に比較した。
• 参考スコア（独自算出の注目度）: 6.258016078705562
• 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. The "P-split" formulations are derived for disjunctive constraints with convex constraints within each disjuct, and we generalize the results for the case with nonconvex constraints within the disjuncts. 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 strong approximations of the convex hull through a computationally simpler formulation. We computationally compare the P-split formulations against big-M and convex hull formulations on 344 test instances. The test problems include K-means clustering, semi-supervised 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（参考訳）: 本研究では, ゆらぎ強度の点から, ビッグMおよび凸殻の定式化と中間の解離的制約に対する混合整数定式化のクラスを開発する。 第一のアイデアは、大きなMと凸の船体定式化の双方の長所を捉えることであり、計算的に軽い定式化とゆるやかな緩和である。 P-スプリット」の定式化は、凸を加法的に分離する制約をP分割に分割し、線形化および分割された接合の凸殻を形成するリフト変換に基づいている。 P-スプリット」の定式化は、各不動域内における凸制約を伴う不動制約に対して導出され、不動域内における非凸制約の場合の結果を一般化する。 P-スプリットの定式化の連続的緩和を解析し、ある仮定の下では、定式化が大質量同値から凸包へ収束する階層を形成することを示す。 P-スプリットの定式化の目標は、計算学的に単純な定式化によって凸殻の強い近似を形成することである。 344 の試験インスタンス上での P-split の定式化と Big-M および convex の定式化を計算的に比較した。 テスト問題としては、K平均クラスタリング、半教師付きクラスタリング、P_ball問題、トレーニングされたReLUニューラルネットワークに対する最適化などがある。 計算結果は, P-スプリット定式化の有望な可能性を示している。 多くの試験問題において、P-スプリットの定式化は凸船体定式化と同様の数の探索ノードで解かれるが、解時間を桁違いに減らし、探索ノードの時間と数の両方でビッグ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)

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

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