論文の概要: Addressing Unboundedness in Quadratically-Constrained Mixed-Integer Problems
- arxiv url: http://arxiv.org/abs/2405.05978v2
- Date: Tue, 15 Oct 2024 09:44:45 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-16 13:59:47.305668
- Title: Addressing Unboundedness in Quadratically-Constrained Mixed-Integer Problems
- Title(参考訳): 二次制約付き混合整数問題における非有界性への対処
- Authors: Guy Zepko, Ofer M. Shir,
- Abstract要約: 混合整数(MI)2次モデル(All-Quadratic MI Programs)はNP完全最適化問題の挑戦的なクラスを構成する。
非有界決定変数を持つMI凸2次目的関数と制約関数の最小化について検討する。
- 参考スコア(独自算出の注目度): 0.0
- License:
- Abstract: Mixed-integer (MI) quadratic models subject to quadratic constraints, known as All-Quadratic MI Programs, constitute a challenging class of NP-complete optimization problems. The particular scenario of unbounded integers defines a subclass that holds the distinction of being even undecidable [Jeroslow, 1973]. This complexity suggests a possible soft-spot for Mathematical Programming (MP) techniques, which otherwise constitute a good choice to treat MI problems. We consider the task of minimizing MI convex quadratic objective and constraint functions with unbounded decision variables. Given the theoretical weakness of white-box MP solvers to handle such models, we turn to black-box meta-heuristics of the Evolution Strategies (ESs) family, and question their capacity to solve this challenge. Through an empirical assessment of all-quadratic test-cases, across varying Hessian forms and condition numbers, we compare the performance of the CPLEX solver to modern MI ESs, which handle constraints by penalty. Our systematic investigation begins where the CPLEX solver encounters difficulties (timeouts as the search-space dimensionality increases, D>=30), and we report in detail on the D=64 case. Overall, the empirical observations confirm that black-box and white-box solvers can be competitive, where CPLEX is evidently outperformed on 13% of the cases. This trend is flipped when unboundedness is amplified by a significant translation of the optima, leading to a totally inferior performance of CPLEX at 83% of the cases. We also conclude that conditioning and separability are not intuitive factors in determining the hardness degree of this class of MI problems.
- Abstract(参考訳): 混合整数(MI)2次モデル(All-Quadratic MI Programs)はNP完全最適化問題の挑戦的なクラスを構成する。
非有界整数の特定のシナリオは、決定不能であることの区別を保持する部分クラスを定義する[Jeroslow, 1973]。
この複雑さは、数学的プログラミング(MP)技法のソフトスポットの可能性を示している。
非有界決定変数を持つMI凸2次目的関数と制約関数の最小化について検討する。
このようなモデルを扱うためのホワイトボックスMPソルバの理論的弱点を考えると、我々は進化戦略(ES)ファミリーのブラックボックスメタヒューリスティックスに目を向け、この課題を解決する能力に疑問を投げかける。
CPLEXソルバの性能を, ペナルティによる制約を扱う現代MI ESと比較した。
CPLEXソルバは困難(探索空間次元が増加するにつれてD>=30)に遭遇し,D=64症例について詳細に報告する。
全体としては、ブラックボックスとホワイトボックスのソルバは競合する可能性があり、CPLEXは13%のケースで明らかに優れています。
アンバウンドネスがオプティマのかなりの翻訳によって増幅されると、この傾向は反転し、CPLEXの83%のケースでは完全に劣っている。
また, 条件付けと分離性は, このクラスMI問題の硬度度を決定する上での直感的な要因ではないと結論づけた。
関連論文リスト
- Feature selection in linear SVMs via hard cardinality constraint: a scalable SDP decomposition approach [3.7876216422538485]
線形支援ベクトルマシン(SVM)における組込み特徴選択問題について検討する。
濃度制約が適用され、完全に説明可能な選択モデルが導かれる。
問題は、濃度制約が存在するためNPハードである。
論文 参考訳(メタデータ) (2024-04-15T19:15:32Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
論文 参考訳(メタデータ) (2022-12-19T14:48:54Z) - On the Global Solution of Soft k-Means [159.23423824953412]
本稿では,ソフトk-平均問題の解法を全世界で提案する。
ミニマルボリュームソフトkMeans (MVSkM) と呼ばれる新しいモデルを提案する。
論文 参考訳(メタデータ) (2022-12-07T12:06:55Z) - Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。
これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。
本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
論文 参考訳(メタデータ) (2022-11-16T18:59:54Z) - Sparse Polynomial Optimization: Theory and Practice [5.27013884159732]
本書は、この課題に重要な科学的意味を持って取り組むためのいくつかの取り組みを提示している。
これは計算複雑性の観点からうまくスケールする代替の最適化スキームを提供する。
制約のない問題や制約のない問題に対して、緩和の疎開的階層を提示する。
論文 参考訳(メタデータ) (2022-08-23T18:56:05Z) - Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
ヒルベルト空間全体の部分空間への発展を制限する混合作用素を構築するための枠組みを提案する。
我々は,「ワンホット」状態の部分空間を保存するために設計された「XY」ミキサーを,多くの計算基底状態によって与えられる部分空間の一般の場合に一般化する。
我々の分析は、現在知られているよりもCXゲートが少ない"XY"ミキサーのトロタライズも有効である。
論文 参考訳(メタデータ) (2022-03-11T17:19:26Z) - Nonequilibrium Monte Carlo for unfreezing variables in hard
combinatorial optimization [1.1783108699768]
適応的勾配自由戦略を開発することにより,非局所非平衡モンテカルロ(NMC)アルゴリズムの量子インスパイアされたファミリーを導入する。
我々は、特殊解法と汎用解法の両方に対して、大幅な高速化と堅牢性を観察する。
論文 参考訳(メタデータ) (2021-11-26T17:45:32Z) - Generalization of Neural Combinatorial Solvers Through the Lens of
Adversarial Robustness [68.97830259849086]
ほとんどのデータセットは単純なサブプロブレムのみをキャプチャし、おそらくは突発的な特徴に悩まされる。
本研究では, 局所的な一般化特性である対向ロバスト性について検討し, 厳密でモデル固有な例と突発的な特徴を明らかにする。
他のアプリケーションとは異なり、摂動モデルは知覚できないという主観的な概念に基づいて設計されているため、摂動モデルは効率的かつ健全である。
驚くべきことに、そのような摂動によって、十分に表現力のあるニューラルソルバは、教師あり学習で共通する正確さと悪質さのトレードオフの限界に悩まされない。
論文 参考訳(メタデータ) (2021-10-21T07:28:11Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳(メタデータ) (2021-07-08T17:59:55Z) - Consistent Second-Order Conic Integer Programming for Learning Bayesian
Networks [2.7473982588529653]
連続観測データからBNのスパースDAG構造を学習する問題について検討する。
この数学的プログラムの最適解は、ある条件下では望ましい統計的性質を持つことが知られている。
ほぼ最適解を得るために, 分岐・結合プロセスの終了に向け, 早期停止条件を提案する。
論文 参考訳(メタデータ) (2020-05-29T00:13:15Z) - On the Sample Complexity and Optimization Landscape for Quadratic
Feasibility Problems [7.722592882475735]
複素ベクトル $mathbfxin mathbbCn$ を $mangle A-imathbfx, mathbfxr_i=1m から復元する問題を考える。
一般に、NP-ハードが解ける二次問題であるだけでなく、実際には特定できないかもしれない。
論文 参考訳(メタデータ) (2020-02-04T00:35:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。