Finding Multiple Optimal Solutions to an Integer Linear Program by Random Perturbations of Its Objective Function
Open Access
- 4 March 2025
- journal article
- research article
- Published by MDPI AG in Algorithms
- Vol. 18 (3) , 140
Abstract
Integer linear programs (ILPs) and mixed integer programs (MIPs) often have multiple distinct optimal solutions, yet the widely used Gurobi optimization solver returns certain solutions at disproportionately high frequencies. This behavior is disadvantageous, as, in fields such as biomedicine, the identification and analysis of distinct optima yields valuable domain-specific insights that inform future research directions. In the present work, we introduce MORSE (Multiple Optima via Random Sampling and careful choice of the parameter Epsilon), a randomized, parallelizable algorithm to efficiently generate multiple optima for ILPs. MORSE maps multiplicative perturbations to the coefficients in an instance’s objective function, generating a modified instance that retains an optimum of the original problem. We formalize and prove the above claim in some practical conditions. Furthermore, we prove that for 0/1 selection problems, MORSE finds each distinct optimum with equal probability. We evaluate MORSE using two measures; the number of distinct optima found in r independent runs, and the diversity of the list (with repetitions) of solutions by average pairwise Hamming distance and Shannon entropy. Using these metrics, we provide empirical results demonstrating that MORSE outperforms the Gurobi method and unweighted variations of the MORSE method on a set of 20 Mixed Integer Programming Library (MIPLIB) instances and on a combinatorial optimization problem in cancer genomics.Keywords
All Related Versions
Funding Information
- Intramural research program of the National Institutes of Health, National Cancer Institute
- NIH Biowulf HPC cluster
- Office of the Provost, the Office for Research, and Northwestern University Information Technology
This publication has 46 references indexed in Scilit:
- Designing gene manipulation schedules for high throughput parallel construction of objective strainsBiotechnology Journal, 2023
- Efficient enumeration of the optimal solutions to the correlation clustering problemJournal of Global Optimization, 2023
- Obtaining Approximately Optimal and Diverse Solutions via Dispersion2022
- MIPLIB 2017: data-driven compilation of the 6th mixed-integer programming libraryMathematical Programming Computation, 2021
- Molecular mechanisms underlying gliomas and glioblastoma pathogenesis revealed by bioinformatics analysis of microarray dataMedical Oncology, 2017
- Diverse competitive design for topology optimizationStructural and Multidisciplinary Optimization, 2017
- MIPLIB 2010Mathematical Programming Computation, 2011
- Elementary mode analysis: a useful metabolic pathway analysis tool for characterizing cellular metabolismApplied Microbiology and Biotechnology, 2009
- Robust solutions of Linear Programming problems contaminated with uncertain dataMathematical Programming, 2000
- Some concepts of stability analysis in combinatorial optimizationDiscrete Applied Mathematics, 1995