論文の概要: Applying a Random-Key Optimizer on Mixed Integer Programs

• arxiv url: http://arxiv.org/abs/2602.22173v1
• Date: Wed, 25 Feb 2026 18:20:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-26 18:19:16.944254
• Title: Applying a Random-Key Optimizer on Mixed Integer Programs
• Title（参考訳）: 混合整数プログラムにおけるランダムキー最適化の適用
• Authors: Antonio A. Chaves, Mauricio G. C. Resende, Carise E. Schmidt, J. Kyle Brubaker, Helmut G. Katzgraber,
• Abstract要約: Mixed-Integer Programs (MIP) は、幅広い意思決定アプリケーションで発生するNPハード最適化モデルである。 本稿では,MIPに対する高品質な解を計算するための,柔軟でメタヒューリスティックな代替手段として,RKO(Random-Key integer)フレームワークの利用について検討する。
• 参考スコア（独自算出の注目度）: 0.36700088931938835
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Mixed-Integer Programs (MIPs) are NP-hard optimization models that arise in a broad range of decision-making applications, including finance, logistics, energy systems, and network design. Although modern commercial solvers have achieved remarkable progress and perform effectively on many small- and medium-sized instances, their performance often degrades when confronted with large-cale or highly constrained formulations. This paper explores the use of the Random-Key Optimizer (RKO) framework as a flexible, metaheuristic alternative for computing high-quality solutions to MIPs through the design of problem-specific decoders. The proposed approach separates the search process from feasibility enforcement by operating in a continuous random-key space while mapping candidate solutions to feasible integer solutions via efficient decoding procedures. We evaluate the methodology on two representative and structurally distinct benchmark problems: the mean-variance Markowitz portfolio optimization problem with buy-in and cardinality constraints, and the Time-Dependent Traveling Salesman Problem. For each formulation, tailored decoders are developed to reduce the effective search space, promote feasibility, and accelerate convergence. Computational experiments demonstrate that RKO consistently produces competitive, and in several cases superior, solutions compared to a state-of-the-art commercial MIP solver, both in terms of solution quality and computational time. These results highlight the potential of RKO as a scalable and versatile heuristic framework for tackling challenging large-scale MIPs.
• Abstract（参考訳）: MIP(Mixed-Integer Programs)は、金融、ロジスティクス、エネルギーシステム、ネットワーク設計など、幅広い意思決定アプリケーションで発生するNPハード最適化モデルである。 現代の商用の解法は目覚ましい進歩を遂げ、多くの中小のインスタンスで効果的に機能するが、その性能は大規模または高度に制約された定式化に直面すると劣化することが多い。 本稿では、問題固有デコーダの設計を通じて、MIPの高品質な解を計算するためのフレキシブルでメタヒューリスティックな代替手段としてRKO(Random-Key Optimizer)フレームワークについて検討する。 提案手法は,効率的な復号処理により,候補解を実現可能な整数解にマッピングしながら,連続的なランダムキー空間で操作することで,検索プロセスと実行可能性の強制を分離する。 本稿では, 平均分散マーコウィッツポートフォリオ最適化問題と, 購買制約, 基数制約問題, 時間依存トラベリングセールスマン問題という2つの代表的な, 構造的に異なるベンチマーク問題について評価する。 各定式化のために、効率的な探索空間を減らし、実現可能性を促進し、収束を加速するために調整されたデコーダを開発する。 計算実験により、RKOは一貫して競争力を発揮し、いくつかの場合において、ソリューションの品質と計算時間の両方の観点から、最先端の商用MIP解決器と比較して、ソリューションが優れていることが示されている。 これらの結果は、大規模MIPに挑戦するためのスケーラブルで多用途なヒューリスティックなフレームワークとしてのRKOの可能性を強調している。

関連論文リスト

• LLM Agents for Combinatorial Efficient Frontiers: Investment Portfolio Optimization [0.0]
  本研究では,カーディナリティ制約付き平均分散ポートフォリオ最適化問題に対する新しいエージェント・フレームワークを実装した。 ベンチマーク問題では、実装されたエージェントフレームワークは最先端のアルゴリズムと一致する。 複雑なアルゴリズム開発は軽減され、最悪の場合、低いが許容できるエラーが報告される。
  論文  参考訳（メタデータ） (2026-01-02T18:02:13Z)
• Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems [3.757262277494307]
  本稿では,量子近似最適化Ansatzのための制約符号化手法の新たな組み合わせを提案する。 ワンホット制約は、検索空間を実現可能なサブ空間に自然に制限する$XY$-mixerによって強制される。 XY$-mixersは検索スペースを制限するため、特定の状態ベクトルエントリは常にゼロであり、シミュレーションから省略することができ、貴重なメモリとコンピューティングリソースを節約できる。
  論文  参考訳（メタデータ） (2025-06-03T17:46:53Z)
• A Random-Key Optimizer for Combinatorial Optimization [0.0]
  本稿では,最適化問題に適した汎用的で効率的な局所探索手法を提案する。 ランダムキーの概念を用いて、RKOは解をランダムキーのベクトルとしてエンコードし、後に実行可能な解に復号する。 RKOフレームワークは古典的メタヒューリスティクスの多元体を組み合わせ、それぞれが独立して、あるいは並列に動作可能であり、エリートソリューションプールを通じてソリューション共有が促進される。
  論文  参考訳（メタデータ） (2024-11-06T22:23:29Z)
• Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
  組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。 GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。 本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
  論文  参考訳（メタデータ） (2023-05-26T15:13:09Z)
• Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
  ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。 1つの典型的な戦略はアルゴリズムのアンローリングであり、これは反復解法の操作による自動微分に依存している。 本稿では,非ロール最適化の後方通過に関する理論的知見を提供し,効率よく解けるバックプロパゲーション解析モデルを生成するシステムに繋がる。
  論文  参考訳（メタデータ） (2023-01-28T01:50:42Z)
• Mining Large Independent Sets on Massive Graphs [47.21699378695116]
  ARCISは、巨大なグラフ上の大きな独立した集合をマイニングするための効率的なアルゴリズムである。 ARCISは、ほとんどのインスタンスで最高の、または最も結びついたソリューション品質が得られることを示す。
  論文  参考訳（メタデータ） (2022-08-16T14:39:38Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)

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

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