Random-Key Optimizer and Linearization for the Quadratic Multiple Constraints Variable-Sized Bin Packing Problem
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 problem 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 model 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 Optimizer 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 model, 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 approaches for solving complex quadratic packing problems. Source code and data available at https://github.com/nataliaalves03/RKO-ACO
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Reinforcement Learning for Safety-Critical Control under Model Uncertainty, using Control Lyapunov Functions and Control Barrier Functions
In this paper, the issue of model uncertainty in safety-critical control is addressed with a data-driven approach. For this purpose, we utilize the structure of an input-ouput linearization controller based on a nominal …
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Outlier detection in regression: conic quadratic formulations
In many applications, when building linear regression models, it is important to account for the presence of outliers, i.e., corrupted input data points. Such problems can be formulated as mixed-integer optimization prob…
Outlier DetectionregressionEfficient Optimal Path Planning in Dynamic Environments Using Koopman MPC
This paper presents a data-driven model predictive control framework for mobile robots navigating in dynamic environments, leveraging Koopman operator theory. Unlike the conventional Koopman-based approaches that focus o…
Computational EfficiencyCollision AvoidanceBeyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networks
Recent theoretical work has established connections between over-parametrized neural networks and linearized models governed by he Neural Tangent Kernels (NTKs). NTK theory leads to concrete convergence and generalizatio…
MPC Based Linear Equivalence with Control Barrier Functions for VTOL-UAVs
In this work, we propose a cascaded scheme of linear Model prediction Control (MPC) based on Control Barrier Functions (CBF) with Dynamic Feedback Linearization (DFL) for Vertical Take-off and Landing (VTOL) Unmanned Aer…
Model Predictive Control