論文の概要: Tightening the mixed integer linear formulation for the piecewise linear approximation in general dimensions

• arxiv url: http://arxiv.org/abs/2508.09395v2
• Date: Thu, 14 Aug 2025 13:17:48 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-19 14:49:10.241117
• Title: Tightening the mixed integer linear formulation for the piecewise linear approximation in general dimensions
• Title（参考訳）: 一般次元におけるピースワイズ線形近似に対する混合整数線型定式化の強化
• Authors: Quentin Ploussard, Xiang Li, Matija Pavičević,
• Abstract要約: 本稿では,任意の次元のデータセットの連続分数線形(CPWL)近似に対する混合整数プログラミング(MILP)の定式化について述べる。
• 参考スコア（独自算出の注目度）: 4.566850249315913
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper addresses the problem of tightening the mixed-integer linear programming (MILP) formulation for continuous piecewise linear (CPWL) approximations of data sets in arbitrary dimensions. The MILP formulation leverages the difference-of-convex (DC) representation of CPWL functions. We introduce the concept of well-behaved CPWL interpolations and demonstrate that any CPWL interpolation of a data set has a well-behaved version. This result is critical to tighten the MILP problem. We present six different strategies to tighten the problem, which include fixing the values of some variables, introducing additional constraints, identifying small big-M parameter values and applying tighter variable bounds. These methods leverage key aspects of the DC representation and the inherent structure of well-behaved CPWL interpolations. Experimental results demonstrate that specific combinations of these tightening strategies lead to significant improvement in solution times, especially for tightening strategies that consider well-behaved CPWL solutions.
• Abstract（参考訳）: 本稿では,任意の次元におけるデータセットの連続分数線形(CPWL)近似に対する混合整数線形計画法(MILP)の厳密化の問題に対処する。 MILPの定式化はCPWL関数の差分凸(DC)表現を利用する。 我々は、よく渡されたCPWL補間の概念を導入し、データセットの任意のCPWL補間がよく渡されたバージョンを持っていることを示す。 この結果はMILP問題を厳しくする上で重要である。 そこで本研究では,変数の値の修正,追加制約の導入,大規模パラメータ値の特定,より厳密な変数境界の適用など,6つの方法を提案する。 これらの手法は、DC表現の鍵となる側面と、よく定義されたCPWL補間の性質を生かしている。 実験結果から, これらの厳密化戦略の特定の組み合わせは, 特にCPWLソリューションを考慮した厳密化戦略において, 解時間を著しく改善することを示した。

関連論文リスト

• Integrating Reinforcement Learning and Model Predictive Control with Applications to Microgrids [14.389086937116582]
  本研究は,有限水平最適制御問題を効率的に解くために,強化学習とモデル予測制御(MPC)を統合するアプローチを提案する。 我々のアプローチは、離散変数の決定を連続変数の決定から切り離すことによってこの問題を軽減することを目的としている。 提案手法では,MPC制御器のオンライン問題を混合整数線形プログラムから線形プログラムへ簡易化する。
  論文  参考訳（メタデータ） (2024-09-17T15:17:16Z)
• A unified consensus-based parallel ADMM algorithm for high-dimensional regression with combined regularizations [3.280169909938912]
  並列交互乗算器 (ADMM) は大規模分散データセットの処理に有効であることが広く認識されている。 提案アルゴリズムは,財務事例の信頼性,安定性,スケーラビリティを示す。
  論文  参考訳（メタデータ） (2023-11-21T03:30:38Z)
• SIGMA: Scale-Invariant Global Sparse Shape Matching [50.385414715675076]
  非剛体形状の正確なスパース対応を生成するための新しい混合整数プログラミング(MIP)法を提案する。 いくつかの挑戦的な3Dデータセットに対して,スパースな非剛性マッチングの最先端結果を示す。
  論文  参考訳（メタデータ） (2023-08-16T14:25:30Z)
• Regularized Multivariate Functional Principal Component Analysis [3.4238565157486187]
  本稿では,プライマリコンポーネントの粗さ制御の問題に対処するため,Realized theCA (ReCA) と呼ばれる新しいアプローチを提案する。 提案手法は多変量関数型PCを生成し,データの簡潔かつ解釈可能な表現を提供する。
  論文  参考訳（メタデータ） (2023-06-24T14:22:25Z)
• High-probability sample complexities for policy evaluation with linear function approximation [88.87036653258977]
  本研究では,2つの広く利用されている政策評価アルゴリズムに対して,最適線形係数の予め定義された推定誤差を保証するために必要なサンプル複素量について検討する。 高確率収束保証に縛られた最初のサンプル複雑性を確立し、許容レベルへの最適依存を実現する。
  論文  参考訳（メタデータ） (2023-05-30T12:58:39Z)
• Tightening Discretization-based MILP Models for the Pooling Problem using Upper Bounds on Bilinear Terms [2.6253445491808307]
  線形項による非最適化問題の解法として,離散化に基づく手法が提案されている。 本稿では,離散化に基づくMILPモデルを用いてプール問題の解法を提案する。
  論文  参考訳（メタデータ） (2022-07-08T05:28:59Z)
• Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
  帰納バイアスは 経験的に過剰フィットを防げる中心的存在です この研究は、この問題を最も基本的な設定として考慮している: 線形回帰に対する定数ステップサイズ SGD。 我々は、(正規化されていない)SGDで得られるアルゴリズム正則化と、通常の最小二乗よりも多くの顕著な違いを反映する。
  論文  参考訳（メタデータ） (2021-03-23T17:15:53Z)
• A Flexible Optimization Framework for Regularized Matrix-Tensor Factorizations with Linear Couplings [5.079136838868448]
  行列とテンソルの分解を結合するフレキシブルなアルゴリズムフレームワークを提案する。 このフレームワークは、様々な制約、損失関数、線形変換との結合の使用を容易にする。
  論文  参考訳（メタデータ） (2020-07-19T06:49:59Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)

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

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