Applying a Random-Key Optimizer on Mixed Integer Programs

2026-02-26 · Source: cs.NE updates on arXiv.org · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Data Science & Analytics · Depth: Advanced, extended

Summary

The Random-Key Optimizer (RKO) framework is proposed as a flexible metaheuristic for solving Mixed-Integer Programs (MIPs), which are NP-hard optimization models prevalent in finance, logistics, and energy systems. While commercial solvers like Gurobi perform well on small-to-medium instances, their efficiency degrades with large-scale or highly constrained problems. RKO addresses this by separating the search process from feasibility enforcement, operating in a continuous random-key space and mapping candidate solutions to feasible integer solutions via problem-specific decoders. The methodology was evaluated on two distinct benchmark problems: the mean-variance Markowitz portfolio optimization with buy-in and cardinality constraints, and the Time-Dependent Traveling Salesman Problem (TD-TSP). Computational experiments demonstrated that RKO consistently produced competitive, and often superior, solutions compared to a commercial MIP solver in terms of both solution quality and computational time, especially for larger instances where Gurobi struggled.

Key takeaway

For AI Scientists and Research Scientists tackling large-scale or highly constrained Mixed-Integer Programs, RKO presents a compelling alternative to traditional commercial solvers. You should consider developing problem-specific decoders within the RKO framework, especially when facing high licensing costs or computational time limits with existing tools. This approach can yield superior solution quality and faster convergence, making it suitable for complex real-world optimization challenges like portfolio optimization or time-dependent routing.

Key insights

RKO offers a scalable metaheuristic for complex MIPs by decoupling search from feasibility via custom decoders.

Principles

• Separate search from feasibility enforcement.
• Map continuous random keys to feasible integer solutions.
• Problem-specific decoders reduce search space and accelerate convergence.

Method

RKO uses a vector of random keys mapped to feasible solutions via a deterministic decoder. It integrates various metaheuristics (e.g., GA, SA, PSO) and employs shaking, blending, and local search for exploration and exploitation.

In practice

• Implement custom decoders for specific MIP constraints.
• Utilize RKO for large-scale MIPs where commercial solvers falter.
• Explore RKO's C++ source code on GitHub for implementation details.

Topics

• Mixed-Integer Programming
• Random-Key Optimizer
• Metaheuristics
• Portfolio Optimization
• Traveling Salesman Problem

Best for: AI Scientist, Research Scientist, AI Researcher, Machine Learning Engineer, Software Engineer

Related on AIssential

• CADO: From Imitation to Cost Minimization for Heatmap-based Solvers in Combinatorial Optimization — Objective mismatch in heatmap-based CO solvers is resolved by RL fine-tuning that directly optimizes post-decoded solution cost.
• Two-Phase Bilevel Search for the Moving-Target Traveling Salesman Problem with Moving Obstacles — A two-phase bilevel search and MICP formulation significantly improve solving the Moving-Target Traveling Salesman Problem with Moving Obstacles.
• RACL: Reasoning-Agent Control Layers for Continuous Metaheuristic Learning — RACL enables reasoning agents to continuously learn and control metaheuristic search behavior using operational memory and bounded experimentation.
• A Gentle Introduction to Nonlinear Constrained Optimization with Piecewise Linear Approximations — Linearizing separable nonlinear programs via PWL approximations and SOS type 2 constraints enables efficient solution with LP/MIP solvers.
• Fast Non-Episodic Finite-Horizon RL with K-Step Lookahead Thresholding — K-step lookahead Q-functions with adaptive thresholding enable fast, sample-efficient online RL in finite-horizon MDPs.
• Pareto-Optimal Offline Reinforcement Learning via Smooth Tchebysheff Scalarization — STOMP uses smooth Tchebysheff scalarization for multi-objective offline RL, outperforming linear methods by recovering full Pareto fronts.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by cs.NE updates on arXiv.org.