論文の概要: 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問題の硬度度を決定する上での直感的な要因ではないと結論づけた。
関連論文リスト
- Quantum-Inspired Mean Field Probabilistic Model for Combinatorial Optimization Problems [15.435730759218776]
擬似非制約二項最適化問題の解を近似する新しい量子インスパイア平均場(QIMF)確率モデルを開発した。
実験により,ポートフォリオ選択,重み付きマックスカット問題,イジングモデルといった大規模問題に対するソリューション評価の大幅な改善が示された。
論文 参考訳（メタデータ） (2024-06-01T01:53:11Z) - A Hybrid Quantum-Classical Approach to the Electric Mobility Problem [0.8796261172196743]
NP-hard Electric Vehicle Fleet Charging and Allocation Problemのためのハイブリッド量子古典ルーチンを提案する。
分解法の性能を古典的・量子的メタヒューリスティックスで評価する。
提案手法の主な利点は、多くの不等式制約のある現実的な問題に対して量子ベースの方法を可能にすることである。
論文 参考訳（メタデータ） (2023-10-04T12:14:56Z) - Computing Star Discrepancies with Numerical Black-Box Optimization
Algorithms [56.08144272945755]
我々は,L_infty$星差分問題に対する8つの一般的な数値ブラックボックス最適化アルゴリズムを比較した。
使用済みのソルバは、ほとんどのケースで非常にひどいパフォーマンスを示します。
我々は、最先端の数値ブラックボックス最適化手法が問題のグローバルな構造を捉えるのに失敗していると疑っている。
論文 参考訳（メタデータ） (2023-06-29T14:57:56Z) - 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) - QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum
machines [81.4597482536073]
量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。
量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。
提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
論文 参考訳（メタデータ） (2022-05-24T03:49:10Z) - LAMBDA: Covering the Solution Set of Black-Box Inequality by Search
Space Quantization [1.345821655503426]
ブラックボックス関数は、入力と出力以外の明示的な情報を提供しない複雑な問題をモデル化するために広く使用される。
ブラックボックス対象関数に対する限られた評価によって設定されたソリューションを可能な限りカバーすることは、ブラックボックス被覆(BBC)問題として定義される。
論文 参考訳（メタデータ） (2022-03-25T15:24:05Z) - Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
ヒルベルト空間全体の部分空間への発展を制限する混合作用素を構築するための枠組みを提案する。
我々は,「ワンホット」状態の部分空間を保存するために設計された「XY」ミキサーを,多くの計算基底状態によって与えられる部分空間の一般の場合に一般化する。
我々の分析は、現在知られているよりもCXゲートが少ない"XY"ミキサーのトロタライズも有効である。
論文 参考訳（メタデータ） (2022-03-11T17:19:26Z) - Minimizing Entropy to Discover Good Solutions to Recurrent Mixed Integer
Programs [0.0]
混合整数プログラミング(MIP)問題に対する現在の解法は、幅広い問題に対して良好に動作するように設計されている。
近年の研究では、機械学習(ML)をMIPソルバと統合してドメイン知識を注入し、最適性ギャップを効率的に閉じることが示されている。
本稿では、エントロピーの概念を用いて、最小限のトレーニングデータとチューニングで効率的にモデルを構築するオンラインソルバを提案する。
論文 参考訳（メタデータ） (2022-02-07T18:52:56Z) - MILP for the Multi-objective VM Reassignment Problem [1.3649494534428743]
多目的機械再割り当て問題は制約と混合整数プログラミングのアプローチにおいて難しい問題である。
我々は,IBM ILOG CPLEXのような混合整数最適化問題を多目的マシン再割り当て問題に利用できることを示す。
本研究では,小・中規模のデータセンタに対してのみ有用であり,最適公差や検索空間での探索方向の制限など,いくつかの緩和効果があることを示す。
論文 参考訳（メタデータ） (2021-03-18T17:46:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。