Fugu-MT 論文翻訳(概要): Addressing Unboundedness in Quadratically-Constrained Mixed-Integer Problems

論文の概要: Addressing Unboundedness in Quadratically-Constrained Mixed-Integer Problems

arxiv url: http://arxiv.org/abs/2405.05978v1
Date: Mon, 6 May 2024 10:54:55 GMT
ステータス: 処理完了
システム内更新日: 2024-05-13 17:45:54.535517
Title: Addressing Unboundedness in Quadratically-Constrained Mixed-Integer Problems
Title（参考訳）: 二次制約付き混合整数問題における非有界性への対処
Authors: Guy Zepko, Ofer M. Shir,
Abstract要約: ブラックボックスとホワイトボックスの解法は最先端のMI ESと競合しうることを示す。条件付けと分離性は,このMI問題の複雑性を決定する上での直感的な要因ではないと結論づける。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Quadratically-constrained unbounded integer programs hold the distinction of being undecidable, suggesting a possible soft-spot for Mathematical Programming (MP) techniques, which otherwise constitute a good choice to treat integer or mixed-integer (MI) problems. We consider the challenge of minimizing MI convex quadratic objective functions subject to unbounded decision variables and quadratic constraints. 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 quadratically-constrained quadratic objective functions, across varying Hessian forms and condition numbers, we compare the performance of the CPLEX solver to state-of-the-art 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), on which we report by means of detailed analyses. Overall, the empirical observations confirm that black-box and white-box solvers can be competitive, especially when the constraint function is separable, and that two common ESs' mutation operators can effectively handle the integer unboundedness. We also conclude that conditioning and separability are not intuitive factors in determining the complexity of this class of MI problems, where regular versus rough landscape structures can pose mirrored degrees of challenge for MP versus ESs.
Abstract（参考訳）: 二次的に制約された非有界整数プログラムは決定不能であることの区別を保ち、数学的プログラミング(MP)技法のソフトスポットの可能性を示し、そうでなければ整数や混合整数(MI)問題を扱うのに良い選択となる。非有界決定変数と2次制約を対象とするMI凸2次目的関数の最小化という課題を考察する。このようなモデルを扱うためのホワイトボックスMPソルバの理論的弱点を考えると、我々は進化戦略(ES)ファミリーのブラックボックスメタヒューリスティックスに目を向け、この課題を解決する能力に疑問を投げかける。 CPLEXソルバの性能を、ペナルティによる制約を扱う最先端MI ESと比較する。我々の系統的な調査は、CPLEXソルバが困難(探索空間の次元が増加するにつれてタイムアウト)に遭遇するところから始まり、詳細な分析によって報告する。全体として、ブラックボックスとホワイトボックスのソルバは、特に制約関数が分離可能であり、2つの一般的なESの突然変異作用素が整数の非有界性を効果的に扱うことができる場合、競合可能であることが実証された。また, 条件付けと分離性は, この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)

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

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