pith. sign in

arxiv: 2602.22173 · v2 · submitted 2026-02-25 · 🧮 math.OC · cs.NE

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 This is my paper

Pith reviewed 2026-05-15 19:20 UTC · model grok-4.3

classification 🧮 math.OC cs.NE
keywords random-key optimizermixed-integer programsmetaheuristicsportfolio optimizationtime-dependent traveling salesmandecoder mappingheuristic MIP solving
0
0 comments X

The pith

A random-key optimizer produces competitive or superior solutions to mixed-integer programs compared to a commercial solver on two benchmark problems.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper applies the Random-Key Optimizer to mixed-integer programs by searching in a continuous random-key space and using problem-specific decoders to generate feasible integer solutions. This separates the exploration process from the enforcement of constraints, which is intended to make the search more efficient on hard MIPs. Experiments on the mean-variance portfolio optimization problem with buy-in and cardinality constraints and on the time-dependent traveling salesman problem show the method matching or exceeding the solution quality and speed of a state-of-the-art commercial MIP solver. A sympathetic reader would care because MIPs appear in finance, logistics, and network design, and exact solvers often slow down on large or tightly constrained instances.

Core claim

The Random-Key Optimizer framework solves mixed-integer programs by operating in continuous random-key space and mapping candidate vectors to feasible integer solutions through tailored decoding procedures. On the constrained Markowitz portfolio problem and the time-dependent TSP, these decoded solutions are competitive with and in several cases better than those obtained from a leading commercial MIP solver, both in objective value and computation time.

What carries the argument

Problem-specific decoders that map random-key vectors to feasible high-quality integer solutions while reducing the effective search space.

If this is right

  • RKO can efficiently enforce cardinality and buy-in constraints in portfolio selection without exhaustive enumeration.
  • Time-dependent costs in routing problems can be handled by decoder logic that respects the time structure during mapping.
  • The continuous search space allows the optimizer to converge faster than direct branch-and-cut on the tested instances.
  • The same framework can be reused on other MIPs by swapping in new decoder procedures.
  • Solution quality remains high even when the underlying MIP becomes large enough to challenge exact solvers.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If decoder design can be partially automated, RKO might serve as a general-purpose complement to exact solvers for very large MIPs.
  • The separation of search and feasibility might extend usefully to other combinatorial problems that have natural continuous relaxations.
  • Hybrid systems could run RKO first to generate good starting points or upper bounds for exact MIP solvers.
  • Further experiments on additional MIP classes would test whether the observed advantage depends on the structure of the two chosen benchmarks.

Load-bearing premise

That problem-specific decoders can be designed to map random-key vectors to feasible high-quality integer solutions without systematically excluding better feasible points or introducing bias.

What would settle it

On a larger instance of either the portfolio or time-dependent TSP problem, if the RKO solutions are consistently worse in quality than the commercial solver when both are run for the same amount of time, the claim of consistent competitiveness would not hold.

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper proposes applying the Random-Key Optimizer (RKO) framework to mixed-integer programs by designing problem-specific decoders that map continuous random-key vectors to feasible integer solutions. It evaluates the approach on two benchmark classes—the constrained mean-variance Markowitz portfolio optimization problem and the Time-Dependent Traveling Salesman Problem—claiming that RKO produces competitive or superior solutions relative to a commercial MIP solver in both solution quality and runtime.

Significance. If the empirical comparisons hold under controlled conditions, the work offers a practical metaheuristic alternative for large-scale MIPs where exact solvers degrade. The random-key separation of search from feasibility enforcement is a clean conceptual contribution, and the provision of tailored decoders for two structurally different problems demonstrates flexibility. However, the absence of detailed experimental protocols limits the strength of the significance claim.

major comments (2)
  1. [§4] §4 (Computational Experiments): no instance sizes, number of runs, or statistical tests are reported, so the claim of consistent superiority cannot be verified against variance or solver tuning effects.
  2. [§4.2] §4.2 (Comparison with MIP solver): the protocol does not state wall-clock time limits applied to the commercial solver or report optimality gaps on instances where the solver fails to terminate; without this, apparent RKO wins may reflect incomplete solver execution rather than decoder quality.
minor comments (2)
  1. [§3] Notation for the random-key vector and decoder mapping is introduced without a compact formal definition; a single displayed equation would improve clarity.
  2. [§4] Figure captions for the portfolio and TD-TSP results do not indicate whether plotted values are averages, best-of-run, or single-run outcomes.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments. We address each major comment below and have revised the manuscript to provide the requested experimental details.

read point-by-point responses

  1. Referee: [§4] §4 (Computational Experiments): no instance sizes, number of runs, or statistical tests are reported, so the claim of consistent superiority cannot be verified against variance or solver tuning effects.

    Authors: We agree that the original manuscript omitted key experimental details. In the revised version we have expanded Section 4 with a table listing all instance sizes for both benchmark classes, stated that each instance was solved in 30 independent runs, and added Wilcoxon signed-rank tests (with p-values) comparing RKO and the MIP solver. These additions allow direct verification of the reported performance differences against stochastic variance. revision: yes

  2. Referee: [§4.2] §4.2 (Comparison with MIP solver): the protocol does not state wall-clock time limits applied to the commercial solver or report optimality gaps on instances where the solver fails to terminate; without this, apparent RKO wins may reflect incomplete solver execution rather than decoder quality.

    Authors: We accept this criticism. The revised Section 4.2 now explicitly states that the commercial solver was run with a 3600-second wall-clock limit on all instances. For every case in which the solver did not terminate, the final optimality gap reported by the solver is tabulated. This protocol ensures that any claimed advantage of RKO is not an artifact of truncated solver runs. revision: yes

Circularity Check

0 steps flagged

No circularity: purely empirical comparison with independent benchmarks

full rationale

The paper advances no derivation chain, uniqueness theorem, or first-principles prediction. Its central claim rests on computational experiments that run RKO (with newly designed decoders) against a commercial MIP solver on two external benchmark families. No equation is shown to equal its own input by construction, no fitted parameter is relabeled as a prediction, and no load-bearing premise collapses to a self-citation. The framework description cites prior RKO literature, but that citation supplies only the metaheuristic template; the reported solution-quality and runtime comparisons are generated afresh on the chosen instances and therefore constitute independent evidence.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The approach assumes that efficient, problem-specific decoding procedures exist that map continuous random-key vectors to feasible MIP solutions while preserving solution quality. No free parameters or invented entities are explicitly introduced in the abstract; any tuning parameters inside the decoders are left implicit.

axioms (1)
  • domain assumption Problem-specific decoders can be constructed that enforce all MIP constraints during the mapping step without excluding optimal feasible solutions.
    Invoked when the authors state that tailored decoders reduce the effective search space and promote feasibility for the two benchmark problems.

pith-pipeline@v0.9.0 · 5563 in / 1327 out tokens · 41741 ms · 2026-05-15T19:20:16.741556+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

37 extracted references · 37 canonical work pages · 1 internal anchor

  1. [1]

    Applied Soft Computing 82, 105575 (2019) https://doi.org/10.1016/ j.asoc.2019.105575

    Andrade, C.E., Byers, S.D., Gopalakrishnan, V., Halepovic, E., Poole, D.J., Tran, L.K., Volinsky, C.T.: Scheduling software updates for connected cars with limited availability. Applied Soft Computing 82, 105575 (2019) https://doi.org/10.1016/ j.asoc.2019.105575

    work page arXiv 2019

  2. [2]

    European Journal of Operational Research 289(1), 17–30 (2021) https://doi.org/10.1016/j.ejor.2019.11.037

    Andrade, C.E., Toso, R.F., Gonçalves, J.F., Resende, M.G.: The multi-parent biased random-key genetic algorithm with implicit path-relinking and its real-world applications. European Journal of Operational Research 289(1), 17–30 (2021) https://doi.org/10.1016/j.ejor.2019.11.037

    work page doi:10.1016/j.ejor.2019.11.037 2021

  3. [3]

    Algorithms 10(4), 121 (2017) https://doi.org/10.3390/a10040121

    Bewoor, L.A., Chandra Prakash, V., Sapkal, S.U.: Evolutionary hybrid particle swarm optimization algorithm for solving NP-hard no-wait flow shop scheduling problems. Algorithms 10(4), 121 (2017) https://doi.org/10.3390/a10040121

    work page doi:10.3390/a10040121 2017

  4. [4]

    Glover, Tabu search — Part I,ORSA J

    Bean, J.C.: Genetic algorithms and random keys for sequencing and optimization. ORSA Journal on Computing 6(2), 154–160 (1994) https://doi.org/10.1287/ijoc. 6.2.154

    work page doi:10.1287/ijoc 1994

  5. [5]

    Networks 42(1), 26–41 (2003) https://doi.org/10.1002/net.10079

    Baldacci, R., Hadjiconstantinou, E., Mingozzi, A.: An exact algorithm for the traveling salesman problem with deliveries and collections. Networks 42(1), 26–41 (2003) https://doi.org/10.1002/net.10079

    work page doi:10.1002/net.10079 2003

  6. [6]

    Operations Research 52(5), 723–738 (2004) https://doi.org/10.1287/ opre.1040.0111

    Baldacci, R., Hadjiconstantinou, E., Mingozzi, A.: An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow for- mulation. Operations Research 52(5), 723–738 (2004) https://doi.org/10.1287/ opre.1040.0111

    work page arXiv 2004

  7. [7]

    Procedia Manufac- turing 22, 57–64 (2018) https://doi.org/10.1016/j.promfg.2018.03.010

    Bewoor, L.A., Prakash, V.C., Sapkal, S.U.: Production scheduling optimization in foundry using hybrid particle swarm optimization algorithm. Procedia Manufac- turing 22, 57–64 (2018) https://doi.org/10.1016/j.promfg.2018.03.010

    work page doi:10.1016/j.promfg.2018.03.010 2018

  8. [8]

    Cambridge University Press, UK (2004)

    Boyd, S.P., Vandenberghe, L.: Convex Optimization. Cambridge University Press, UK (2004)

    work page 2004

  9. [9]

    In: 2021 IEEE Congress on Evolutionary Computation (CEC), pp

    Chaves, A.A., Lorena, L.H.N.: An adaptive and near parameter-free BRKGA using Q- learning method. In: 2021 IEEE Congress on Evolutionary Computation (CEC), pp. 2331–2338 (2021). https://doi.org/10.1109/CEC45853.2021.9504766

    work page doi:10.1109/cec45853.2021.9504766 2021

  10. [10]

    Computers & Operations Research 27(13), 1271–1302 (2000) https://doi.org/10.1016/S0305-0548(99)00074-X

    Chang, T.-J., Meade, N., Beasley, J.E., Sharaiha, Y.M.: Heuristics for cardinality constrained portfolio optimisation. Computers & Operations Research 27(13), 1271–1302 (2000) https://doi.org/10.1016/S0305-0548(99)00074-X

    work page doi:10.1016/s0305-0548(99)00074-x 2000

  11. [11]

    Chaves, A.A., Resende, M.G.C., Silva, R.M.A.: A random-key GRASP for combina- torial optimization. J. Nonlinear Var. Anal. 8, 855–881 (2024) https://doi.org/ 10.23952/jnva.8.2024.6.03

    work page doi:10.23952/jnva.8.2024.6.03 2024

  12. [12]

    Journal of Heuristics 31(4), 32 (2025) https://doi.org/10.1007/ s10732-025-09568-z

    Chaves, A.A., Resende, M.G.C., Schuetz, M.J.A., Brubaker, J.K., Katzgraber, 26 H.G., Arruda, E.F., Silva, R.M.A.: A random-key optimizer for combinatorial optimization. Journal of Heuristics 31(4), 32 (2025) https://doi.org/10.1007/ s10732-025-09568-z

    work page 2025

  13. [13]

    Portfolio selection problems in practice: a comparison between linear and quadratic optimization models

    Cesarone, F., Scozzari, A., Tardella, F.: Portfolio selection problems in practice: a comparison between linear and quadratic optimization models. arXiv preprint arXiv:1105.3594 (2011) https://doi.org/10.48550/arXiv.1105.3594

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.1105.3594 2011

  14. [14]

    (ed.): Handbook of Genetic Algorithms

    Davis, L.D. (ed.): Handbook of Genetic Algorithms. Van Nostrand Reinhold, New York (1991)

    work page 1991

  15. [15]

    Mathematical Programming 91, 201–213 (2002) https://doi.org/10.1007/ s101070100263 Fair Isaac Corporation: FICO Xpress Optimization Suite: User’s Manual

    Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance pro- files. Mathematical Programming 91, 201–213 (2002) https://doi.org/10.1007/ s101070100263 Fair Isaac Corporation: FICO Xpress Optimization Suite: User’s Manual. San Jose,

    work page 2002

  16. [16]

    https://www.fico.com/en/products/fico-xpress-optimization

    CA, USA (2025). https://www.fico.com/en/products/fico-xpress-optimization

    work page 2025

  17. [17]

    Jour- nal of Global Optimization 6(1), 109–133 (1995) https://doi.org/10.1007/ BF01096763 Gurobi Optimization, L.: Gurobi Optimizer Reference Manual

    Feo, T.A., Resende, M.G.C.: Greedy randomized adaptive search procedures. Jour- nal of Global Optimization 6(1), 109–133 (1995) https://doi.org/10.1007/ BF01096763 Gurobi Optimization, L.: Gurobi Optimizer Reference Manual. (2024). https://www. gurobi.com Gonçalves, J.F., Resende, M.G.: Biased random-key genetic algorithms for combina- torial optimization...

    work page doi:10.1007/s10732-010-9143-1 1995

  18. [18]

    Engineering Optimization 47(11), 1481–1496 (2015) https://doi.org/10.1080/0305215X.2014.971778

    Garcia-Santiago, C., Ser, J., Upton, C., Quilligan, F., Gil-Lopez, S., Salcedo-Sanz, S.: A random-key encoded harmony search approach for energy-efficient production scheduling with shared resources. Engineering Optimization 47(11), 1481–1496 (2015) https://doi.org/10.1080/0305215X.2014.971778

    work page doi:10.1080/0305215x.2014.971778 2015

  19. [19]

    Armonk, NY, USA (2024)

    Cambridge, Massachusetts (1992) IBM Corporation: IBM ILOG CPLEX Optimization Studio V22.1.1 User’s Manual. Armonk, NY, USA (2024). https://www.ibm.com/products/ ilog-cplex-optimization-studio

    work page 1992

  20. [20]

    (eds.) Reducibil- ity among Combinatorial Problems, pp

    Karp, R.M.: In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Reducibil- ity among Combinatorial Problems, pp. 85–103. Springer, Boston, MA (1972). https://doi.org/10.1007/978-3-540-68279-0_8

    work page doi:10.1007/978-3-540-68279-0_8 1972

  21. [21]

    doi:10.1109/ICNN.1995.488968 Scott Kirkpatrick, C

    Kennedy, J., Eberhart, R.: Particle swarm optimization. In: Proceedings of ICNN’95 - International Conference on Neural Networks, vol. 4, pp. 1942–1948 (1995). https: //doi.org/10.1109/ICNN.1995.488968

    work page doi:10.1109/icnn.1995.488968 1942

  22. [22]

    Optimization by Simulated Annealing,

    Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220(4598), 671–680 (1983) https://doi.org/10.1126/science.220.4598.671

    work page doi:10.1126/science.220.4598.671 1983

  23. [23]

    Korte and J

    Springer, Heidelberg (2018). https://doi.org/10.1007/978-3-662-56039-6

    work page doi:10.1007/978-3-662-56039-6 2018

  24. [24]

    Expert Systems with Applications 37(3), 2629–2636 (2010) https: //doi.org/10.1016/j.eswa.2009.08.015 27 Lourenço, H.R., Martin, O.C., Stützle, T.: Iterated local search

    Kuo, I.-H.: An efficient job-shop scheduling algorithm based on particle swarm optimization. Expert Systems with Applications 37(3), 2629–2636 (2010) https: //doi.org/10.1016/j.eswa.2009.08.015 27 Lourenço, H.R., Martin, O.C., Stützle, T.: Iterated local search. In: Glover, F.,

    work page doi:10.1016/j.eswa.2009.08.015 2010

  25. [25]

    https://doi.org/10.1007/0-306-48056-5_11

    Boston, MA (2003). https://doi.org/10.1007/0-306-48056-5_11

    work page doi:10.1007/0-306-48056-5_11 2003

  26. [26]

    Transportation Science 26(3), 185–200 (1992) https://doi.org/10.1287/trsc.26.3.185 Mladenović, N., Hansen, P.: Variable neighborhood search

    Malandraki, C., Daskin, M.S.: Time dependent vehicle routing problems: Formula- tions, properties and heuristic algorithms. Transportation Science 26(3), 185–200 (1992) https://doi.org/10.1287/trsc.26.3.185 Mladenović, N., Hansen, P.: Variable neighborhood search. Computers & Operations Research 24(11), 1097–1100 (1997) https://doi.org/10.1016/S0305-0548(...

    work page doi:10.1287/trsc.26.3.185 1992

  27. [27]

    In: Anais do Simpó- sio Brasileiro de Pesquisa Operacional

    Mangussi, A.D., Pola, H., Macedo, H.G., Julião, L.A., Proença, M.P.T., Gianfe- lice, P.R.L., Salezze, B.V., Chaves, A.A.: Meta-heurísticas via chaves aleatórias aplicadas ao problema de localização de hubs em árvore. In: Anais do Simpó- sio Brasileiro de Pesquisa Operacional. Galoá, São José dos Campos (2023). https://doi.org/10.59254/sbpo-2023-174934

    work page doi:10.59254/sbpo-2023-174934 2023

  28. [28]

    The Computer Journal 7(4), 308–313 (1965)

    Nelder, J.A., Mead, R.: A simplex method for function minimization. The Computer Journal 7(4), 308–313 (1965)

    work page 1965

  29. [29]

    Soft Computing 19, 1099–1106 (2015) https://doi.org/ 10.1007/s00500-014-1322-9

    Ouaarab, A., Ahiod, B., Yang, X.-S.: Random-key Cuckoo Search for the travel- ling salesman problem. Soft Computing 19, 1099–1106 (2015) https://doi.org/ 10.1007/s00500-014-1322-9

    work page doi:10.1007/s00500-014-1322-9 2015

  30. [30]

    European Journal of Operational Research 266(3), 950–962 (2018) https://doi.org/10.1016/j.ejor.2017.10.045

    Pessoa, L.S., Andrade, C.E.: Heuristics for a flowshop scheduling problem with step- wise job objective function. European Journal of Operational Research 266(3), 950–962 (2018) https://doi.org/10.1016/j.ejor.2017.10.045

    work page doi:10.1016/j.ejor.2017.10.045 2018

  31. [31]

    (eds.) Large Neighborhood Search, pp

    Pisinger, D., Ropke, S.: In: Gendreau, M., Potvin, J.-Y. (eds.) Large Neighborhood Search, pp. 399–419. Springer, Boston, MA (2010). https://doi.org/10.1007/ 978-1-4419-1665-5_13

    work page 2010

  32. [32]

    Prentice-Hall, Inc., USA (1982)

    Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Inc., USA (1982)

    work page 1982

  33. [33]

    Phys- ical Review Applied 18(5) (2022) https://doi.org/10.1103/PhysRevApplied.18

    Schuetz, M.J.A., Brubaker, J.K., Montagu, H., van Dijk, Y., Klepsch, J., Ross, P., Luckow, A., Resende, M.G.C., Katzgraber, H.G.: Optimization of robot trajectory planning with nature-inspired and hybrid quantum algorithms. Phys- ical Review Applied 18(5) (2022) https://doi.org/10.1103/PhysRevApplied.18. 054045

    work page doi:10.1103/physrevapplied.18 2022

  34. [34]

    https://patentsgazette.uspto.gov/week42/OG/html/1539-3/ US12447617-20251021.html

    Schuetz, M., Brubaker, J.K., Resende, M., Katzgraber, H.G.: Random key opti- mization for generating sequencing plans, US patent number 12,447,617 B1 (2025). https://patentsgazette.uspto.gov/week42/OG/html/1539-3/ US12447617-20251021.html

    work page 2025

  35. [35]

    Computers & Operations Research 37(11), 1899–1911 (2010) https://doi.org/10

    Subramanian, A., Drummond, L.M., Bentes, C., Ochi, L.S., Farias, R.: A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery. Computers & Operations Research 37(11), 1899–1911 (2010) https://doi.org/10. 1016/j.cor.2009.10.011

    work page 1911

  36. [36]

    Journal of Global Optimization 60, 289–306 (2014) https://doi.org/ 10.1007/s10898-013-0105-7

    Silva, R.M., Resende, M.G., Pardalos, P.M.: Finding multiple roots of a box- constrained system of nonlinear equations with a biased random-key genetic algorithm. Journal of Global Optimization 60, 289–306 (2014) https://doi.org/ 10.1007/s10898-013-0105-7

    work page doi:10.1007/s10898-013-0105-7 2014

  37. [37]

    In: 2009 World Congress on 28 Nature & Biologically Inspired Computing (NaBIC), pp

    Yang, X.-S., Deb, S.: Cuckoo Search via Lévy flights. In: 2009 World Congress on 28 Nature & Biologically Inspired Computing (NaBIC), pp. 210–214 (2009). https: //doi.org/10.1109/NABIC.2009.5393690 . IEEE 29

    work page doi:10.1109/nabic.2009.5393690 2009