論文の概要: Random-Key Metaheuristic and Linearization for the Quadratic Multiple Constraints Variable-Sized Bin Packing Problem

• arxiv url: http://arxiv.org/abs/2511.12367v1
• Date: Sat, 15 Nov 2025 22:05:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-18 14:36:23.994366
• Title: Random-Key Metaheuristic and Linearization for the Quadratic Multiple Constraints Variable-Sized Bin Packing Problem
• Title（参考訳）: 可変サイズビンパッケージ問題に対するランダムキーメタヒューリスティックと線形化
• Authors: Natalia A. Santos, Marlon Jeske, Antonio A. Chaves,
• Abstract要約: 本稿では,QMC-VSBPPの2次多重制約可変サイズバンドル問題に対処する。 この問題は、複数のキャパシティ次元、異種ビンタイプ、アイテム間の二次的相互作用コストを組み込むことで、古典的なビンパッキングを一般化する。 現状を推し進める2つの補完手法を提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper addresses the Quadratic Multiple Constraints Variable-Sized Bin Packing Problem (QMC-VSBPP), a challenging combinatorial optimization problem that generalizes the classical bin packing by incorporating multiple capacity dimensions, heterogeneous bin types, and quadratic interaction costs between items. We propose two complementary methods that advance the current state-of-the-art. First, a linearized mathematical formulation is introduced to eliminate quadratic terms, enabling the use of exact solvers such as Gurobi to compute strong lower bounds - reported here for the first time for this problem. Second, we develop RKO-ACO, a continuous-domain Ant Colony Optimization algorithm within the Random-Key Optimization framework, enhanced with adaptive Q-learning parameter control and efficient local search. Extensive computational experiments on benchmark instances show that the proposed linearized model produces significantly tighter lower bounds than the original quadratic formulation, while RKO-ACO consistently matches or improves upon all best-known solutions in the literature, establishing new upper bounds for large-scale instances. These results provide new reference values for future studies and demonstrate the effectiveness of evolutionary and random-key metaheuristic approaches for solving complex quadratic packing problems. Source code and data available at https://github.com/nataliaalves03/RKO-ACO
• Abstract（参考訳）: 本稿では,複数キャパシティディメンション,異種ビンタイプ,アイテム間の2次相互作用コストを組み込んだ古典的ビンパッキングを一般化する難解な組合せ最適化問題であるQMC-VSBPP(Quardratic Multiple Constraints Variable-Sized Bin Packing Problem)に対処する。 現状を推し進める2つの補完手法を提案する。 まず、二次項を排除するために線形化された数学的定式化を導入し、グロビのような正確な解法を使って強い下界を計算することができる。 第二にRKO-ACOは,Random-Key Optimizationフレームワーク内での連続領域アントコロニー最適化アルゴリズムであり,適応的なQ-ラーニングパラメータ制御と効率的な局所探索によって拡張されている。 ベンチマークインスタンス上での大規模計算実験により、提案された線形化モデルは、元の二次的定式化よりもかなり低い境界を生成する一方、RKO-ACOは、文献におけるすべての最もよく知られた解に一貫して一致または改善し、大規模インスタンスに対する新しい上限を確立する。 これらの結果は、将来の研究のための新しい基準値を提供し、複雑な二次パッキング問題を解決するための進化的およびランダムキーメタヒューリスティックなアプローチの有効性を実証する。 source code and data available at https://github.com/nataliaalves03/RKO-ACO

関連論文リスト

• Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems [3.757262277494307]
  本稿では,量子近似最適化Ansatzのための制約符号化手法の新たな組み合わせを提案する。 ワンホット制約は、検索空間を実現可能なサブ空間に自然に制限する$XY$-mixerによって強制される。 XY$-mixersは検索スペースを制限するため、特定の状態ベクトルエントリは常にゼロであり、シミュレーションから省略することができ、貴重なメモリとコンピューティングリソースを節約できる。
  論文  参考訳（メタデータ） (2025-06-03T17:46:53Z)
• $\ell_0$-Regularized Quadratic Surface Support Vector Machines [0.0]
  カーネルフリーの二次曲面支持ベクトルマシンは、カーネル関数に依存することなく非線形決定境界をモデル化する柔軟性により、近年注目を集めている。 本稿では,モデルパラメータに濃度制約を課すことにより,QSVMのスパース変種を提案する。 我々は,いくつかの実世界のデータセットに対するアプローチを検証し,高い分類性能を維持しながらオーバーフィッティングを低減できることを実証した。
  論文  参考訳（メタデータ） (2025-01-20T04:26:34Z)
• Feature selection in linear SVMs via a hard cardinality constraint: a scalable SDP decomposition approach [3.7876216422538485]
  本稿では, 線形支援ベクトルマシン(SVM)において, 濃度制約が適用された場合の組込み特徴選択問題について検討する。 この問題は、元の線形SVMが時間内に解決可能な問題に等しいにもかかわらず、濃度制約が存在するためNPハードである。 この問題に対処するために、まず2つの混合整数式を導入し、新しい半定緩和法を提案する。
  論文  参考訳（メタデータ） (2024-04-15T19:15:32Z)
• A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization [53.14532968909759]
  ALEXRと呼ばれる,効率的な単ループプリマル・デュアルブロック座標アルゴリズムを提案する。 本研究では, ALEXR の凸面および強凸面の収束速度を滑らか性および非滑らか性条件下で確立する。 CFCCO の ROC 曲線の下での GDRO および部分領域の実験結果から,提案アルゴリズムの有望な性能を示す。
  論文  参考訳（メタデータ） (2023-12-04T19:00:07Z)

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

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