Applying a Random-Key Optimizer on Mixed Integer Programs

Antonio A. Chaves; Mauricio G. C. Resende; Carise E. Schmidt; J. Kyle Brubaker; Helmut G. Katzgraber; Martin J. A. Schuetz

math.OCFeb 25, 2026

Applying a Random-Key Optimizer on Mixed Integer Programs

Authors: Antonio A. Chaves, Mauricio G. C. Resende, Carise E. Schmidt, J. Kyle Brubaker, Helmut G. Katzgraber, Martin J. A. Schuetz

Organizations: Federal Univ. of São Paulo, S. J. dos Campos, SP, Brazil. · DIMACS, Piscataway, NJ, USA. · Instituto Federal de Santa Catarina, Chapecó, SC, Brazil. · San Diego, CA, USA. ·

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.

Figures & tables

Figure 1: Schematic illustration of our approach. Our framework is based on a distinct separation of problem-independent (blue hypercube) and problem-dependent (decoder) modules. The search for high-quality solutions is performed within the (problem-independent) space of random keys, as can be implemented with a stack of algorithmic paradigms such as genetic algorithms, simulated annealing, or swarm-based algorithms. The deterministic (problem-dependent) decoder maps a given random-key vector $\mathcal{X}\in[0,1)^{n}$ to a feasible solution $x=\mathit{decoder(\mathcal{X})}$ within the problem space (as displayed by black dots). For mixed integer programs, our decoder design allows for an efficient, native encoding of a plethora of common constraints such as integrality constraints, variable bounds, and cardinality constraints.

Figure 2: Decoder example for the mixed-integer limited-asset Markowitz model. The solution is encoded in the random key vector of size $2K$ , with the first block encoding the integer variables $z_{i}$ and the second block representing the continous weights $w_{i}$ . Decoding is done through $K$ simple iterations. For the given sample random key vector we obtain a set of selected assets given by $\mathbb{S}=\{9,3,6\}$ . Cardinality, budget, and integrality constraints are satisfied by virtue of this decoder design, while the remaining variable bounds are handeled via appropriate penalty terms in the cost function.

Panel of Figure 3 — Figure 3: Decoder example for the TD-TSP model. The solution is encoded in the random-key vector of size $n$ . For the given example, the selected customer visiting sequence is $5-4-2-3-1-6$ .

						Gurobi				RKO
Instance	$n$	$K$	$l_{i}$	$u_{i}$	$\lambda$	UB	LB	gap(%)	total time (s)	OFV	$\mathrm{RPD_{b}}$	$\mathrm{RPD_{a}}$	best found at (s)
port1 (Hang Seng)	31	5	0.01	0.25	0.3	-0.00466	-0.00466	0.00	0.02	-0.00466	0.00	0.01	6.64
		8				-0.00465	-0.00465	0.00	0.01	-0.00465	0.00	0.00	9.77
		10				-0.00464	-0.00464	0.00	0.01	-0.00464	0.01	0.01	9.94
		15				-0.00461	-0.00461	0.00	0.01	-0.00461	0.03	0.10	9.97
port2 (DAX)	85	10	0.01	0.25	0.3	-0.00532	-0.00532	0.00	0.03	-0.00532	0.00	0.05	19.89

Table 1: Computational results for Portfolio instances (

\lambda=0.3

						Gurobi				RKO
Instance	$n$	$K$	$l_{i}$	$u_{i}$	$\lambda$	UB	LB	gap(%)	total time (s)	OFV	$\mathrm{RPD_{b}}$	$\mathrm{RPD_{a}}$	best found at (s)
port1 (Hang Seng)	31	5	0.01	0.25	0.5	-0.00297	-0.00297	0.00	0.43	-0.00297	0.00	0.00	8.36
		8				-0.00297	-0.00297	0.00	0.03	-0.00297	0.02	0.02	9.93
		10				-0.00296	-0.00296	0.00	0.01	-0.00296	0.00	0.01	9.91
		15				-0.00293	-0.00293	0.00	0.01	-0.00293	0.08	0.15	9.98
port2 (DAX)	85	10	0.01	0.25	0.5	-0.00365	-0.00365	0.00	0.03	-0.00365	0.00	0.03	19.22

Table 2: Computational results for Portfolio instances (

\lambda=0.5

						Gurobi				RKO
Instance	$n$	$K$	$l_{i}$	$u_{i}$	$\lambda$	UB	LB	gap(%)	total time (s)	OFV	$\mathrm{RPD_{b}}$	$\mathrm{RPD_{a}}$	best found at (s)
port1 (Hang Seng)	31	5	0.01	0.25	0.7	-0.00130	-0.00130	0.00	0.01	-0.00130	0.00	0.00	9.81
		8				-0.00130	-0.00130	0.00	0.01	-0.00130	0.00	0.02	9.82
		10				-0.00129	-0.00129	0.00	0.01	-0.00129	0.00	0.03	9.23
		15				-0.00127	-0.00127	0.00	0.01	-0.00127	0.02	0.02	9.96
port2 (DAX)	85	10	0.01	0.25	0.7	-0.00198	-0.00198	0.00	0.03	-0.00198	0.01	0.01	19.81

Table 3: Computational results for Portfolio instances (

\lambda=0.7

)

Figure 4: Time-to-target plot for Russell 3000 instance with

K=40

and

\lambda=0.5

Figure 5: Time-to-target plot for Russell 3000 instance with

K=60

and

\lambda=0.5

Panel of Figure 6 — Figure 6: Pareto Frontiers for the Nikkei instances.

	Gurobi				RKO
$n$	UB	LB	gap(%)	total time (s)	OFV	$\mathrm{RPD_{b}}$	$\mathrm{RPD_{a}}$	best found at (s)
10	7235.60	7235.60	0.00	2.70	7235.60	0.00	0.00	0.00
12	8210.20	8210.20	0.00	14.66	8210.20	0.00	0.00	0.01
14	8930.80	8930.80	0.00	75.29	8930.80	0.00	0.00	0.01
20	11006.00	10349.40	6.26	1618.33	10848.60	-0.89	-0.89	0.47
22	12393.20	10887.00	12.01	1800.05	11877.20	-1.98	-1.98	0.55

Table 4: Average computational results for TD-TSP instances with

|H|=5

	Gurobi				RKO
$n$	UB	LB	gap(%)	total time (s)	OFV	$\mathrm{RPD_{b}}$	$\mathrm{RPD_{a}}$	best found at (s)
10	7354.40	7354.40	0.00	18.32	7354.40	0.00	0.00	0.00
12	8239.20	8239.20	0.00	66.54	8239.20	0.00	0.00	0.01
14	9007.00	8828.40	1.68	590.47	8987.80	0.00	0.00	0.02
20	12339.60	9759.60	20.64	1800.20	11052.80	-3.04	-3.04	0.22
22	12535.80	10367.80	17.20	1800.08	12123.60	-3.20	-3.20	1.21

Table 5: Average computational results for TD-TSP instances with

|H|=10

	Gurobi				RKO
$n$	UB	LB	gap(%)	total time (s)	OFV	$\mathrm{RPD_{b}}$	$\mathrm{RPD_{a}}$	best found at (s)
10	7405.60	7405.60	0.00	41.29	7405.60	0.00	0.00	0.00
12	8334.20	8334.20	0.00	199.02	8334.20	0.00	0.00	0.00
14	9162.60	8966.00	1.78	1144.58	9154.40	-0.02	-0.02	0.01
20	11828.00	8894.00	24.56	1800.33	11093.80	-2.59	-2.59	0.26
22	12883.80	9796.40	24.08	1800.25	12206.80	-4.37	-4.37	1.27

Table 6: Average computational results for TD-TSP instances with

|H|=15

Figure 7: Quality performance profile for the TD-TSP instance set using the best-known value as reference.

Figure 8: Quality performance profile for the TD-TSP instance set using the Gurobi lower bound as reference.

Metaheuristic Optimization

Metaheuristic optimization develops flexible search strategies for finding strong solutions to difficult problems when exact methods are too costly.

See all 115 papers

GRIMIP: A General Framework for Instance-Specific Configuration of MIP Solvers Using LLMs
Jun 22, 2026Yidong Luo, Xuemin Chen, Chenguang Wang +3Surrogate-Assisted Optimization Mixed-Integer Linear Programming
School of Data Science, The Chinese University of Hong Kong, Shenzhen · School of Science and Engineering, The Chinese University of Hong Kong, Shenzhen · Noah’s Ark Lab, Huawei
Constrained Graph Diffusion for Mixed Integer Optimization
Aug 13, 2026Vincenzo Di Vito, Yusuf Guven, Babak Badnava +3Mixed-Integer Linear Programming Constrained Optimization
University of Virginia · MIT · Los Alamos National Laboratory
Fusing Backdoors, Machine Learning, and Optimization for Large-Scale Parametric Mixed-Integer Programs
Jun 19, 2026El Mehdi Er Raqabi, Pascal Van HentenryckLearning to Optimize Combinatorial Optimization
Department of Operations and Decision Systems, Université Laval, Québec, Canada · H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, USA

Jun 22, 2026J/K move · Enter open · S save

GRIMIP: A General Framework for Instance-Specific Configuration of MIP Solvers Using LLMs

Yidong Luo, Xuemin Chen, Chenguang Wang, Fangzhou Zhu+2

School of Data Science, The Chinese University of Hong Kong, Shenzhen · School of Science and Engineering, The Chinese University of Hong Kong, Shenzhen · Noah’s Ark Lab, Huawei

Surrogate-Assisted Optimization Mixed-Integer Linear Programming Bayesian Optimization Large Language Model-Guided Optimization Hyperparameter Optimization

Open paper AskPDF arXiv

Configuring the hyperparameters of Mixed-integer programming (MIP) solvers is a high-dimensional, instance-dependent optimization problem where suboptimal settings can degrade solving time by orders of magnitude. Default configurations are often suboptimal, while traditional tuning methods either suffer from the ``cold-start'' problem and inefficient search or heavily rely on expert experience. This paper introduces GRIMIP (General Reasoning for Instance-specific MIP configuration), a novel hybrid intelligence framework that synergistically integrates the semantic reasoning capabilities of Large Language Models (LLMs) with the sample-efficient search of Bayesian Optimization (BO). GRIMIP enables the LLM to function as a complete probabilistic surrogate within the BO loop, significantly improving performance and reducing sampling and evaluation costs. On seven benchmarks including MIPLIB, GRIMIP achieves over 40% reduction in Primal-Dual Integral on hard instances, outperforming SMAC and other LLM-assisted BO methods. By granting LLMs sufficient autonomy, GRIMIP combines the expert-level reasoning of LLMs with the efficient search of BO, achieving state-of-the-art performance.

Abstract

Metaheuristic Optimization

Explore similar work

GRIMIP: A General Framework for Instance-Specific Configuration of MIP Solvers Using LLMs

Constrained Graph Diffusion for Mixed Integer Optimization

Fusing Backdoors, Machine Learning, and Optimization for Large-Scale Parametric Mixed-Integer Programs