On Survival Time in Robust Optimization over Time for Discrete Search Spaces

Abstract

Robust Optimization Over Time (ROOT) addresses dynamic optimization problems where the goal is not to track the transient optimum but to identify solutions that remain effective across multiple future environments. Despite recent algorithmic advances, the theoretical foundations of ROOT remain limited, particularly regarding survival-time formulations in discrete search spaces. This paper bridges this gap by analyzing expected survival time in combinatorial ROOT under stochastic k-bit-flip dynamics. Using drift analysis and martingale techniques, we derive order-matching analytical bounds and phase transitions for dynamic OneMax, capturing gradual fitness degradation. For dynamic LeadingOnes, which models catastrophic structural failure, we prove that survival time follows an exact geometric distribution. Monte Carlo simulations empirically validate these analytical models. Ultimately, these results connect ROOT with classical runtime analysis, formalizing the mechanisms governing solution durability and providing a rigorous mathematical foundation for survival-aware heuristics in combinatorial environments.

Adjustable Robust Optimization with Discrete Uncertainty
Henri Lefebvre, Enrico Malaguti, Michele Monaci
INFORMS Journal on Computing14 Sep 2026Peer-reviewedLicence not statedFull text6 citedOptimisation & controlHAL
Distributionally Robust Optimization over Incomparable Spaces
Junyu Chen, Jieling Shi, Yong Sheng Soh
arXiv1 Nov 2026PreprintarXiv licenceFull textOptimisation & controlarXiv
Optimal Sample Exponents for Direct Discrete-Gaussian SVP Search on Haar Random Lattices
Masahiro Kaminaga
arXiv25 Sep 2026PreprintCC BY 4.0Full textProbabilityarXiv
Calibration-Free Robust Bayesian Inference for Discrete Unnormalized Models
Jiongran Wang, Debdeep Pati, Anirban Bhattacharya
arXiv6 Oct 2026PreprintCC BY 4.0Full textStatisticsarXiv
High Performance Computing of SDRE models with Discrete Kalman Filtering for Robust H_∞-Controls
Yunfeng Cai, Tiexiang Li, Wen-Wei Lin +1
arXiv29 Sep 2026PreprintarXiv licenceFull textNumerical analysis & scientific computingarXiv

Cite

BibTeX RIS

BibTeX

@article{novoahernandez2026survival,
  title = {{On Survival Time in Robust Optimization over Time for Discrete Search Spaces}},
  author = {Pavel Novoa-Hernández},
  journal = {Mathematics},
  year = {2026},
  month = nov,
  doi = {10.3390/math14213997},
  url = {https://www.mdpi.com/2227-7390/14/21/3997},
  note = {CC BY 4.0},
}

RIS

TY  - JOUR
TI  - On Survival Time in Robust Optimization over Time for Discrete Search Spaces
AU  - Pavel Novoa-Hernández
PY  - 2026
DA  - 2026/11/02
JO  - Mathematics
DO  - 10.3390/math14213997
UR  - https://www.mdpi.com/2227-7390/14/21/3997
AB  - Robust Optimization Over Time (ROOT) addresses dynamic optimization problems where the goal is not to track the transient optimum but to identify solutions that remain effective across multiple future environments. Despite recent algorithmic advances, the theoretical foundations of ROOT remain limited, particularly regarding survival-time formulations in discrete search spaces. This paper bridges this gap by analyzing expected survival time in combinatorial ROOT under stochastic k-bit-flip dynamics. Using drift analysis and martingale techniques, we derive order-matching analytical bounds and phase transitions for dynamic OneMax, capturing gradual fitness degradation. For dynamic LeadingOnes, which models catastrophic structural failure, we prove that survival time follows an exact geometric distribution. Monte Carlo simulations empirically validate these analytical models. Ultimately, these results connect ROOT with classical runtime analysis, formalizing the mechanisms governing solution durability and providing a rigorous mathematical foundation for survival-aware heuristics in combinatorial environments.
SN  - 2227-7390
ER  -

Abstract

Related

Cite