Finding Multiple Optimal Solutions to an Integer Linear Program by Random Perturbations of Its Objective Function
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 i...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-03-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/18/3/140 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850094124368134144 |
|---|---|
| author | Noah Schulhof Pattara Sukprasert Eytan Ruppin Samir Khuller Alejandro A. Schäffer |
| author_facet | Noah Schulhof Pattara Sukprasert Eytan Ruppin Samir Khuller Alejandro A. Schäffer |
| author_sort | Noah Schulhof |
| collection | DOAJ |
| description | 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 <i>r</i> 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. |
| format | Article |
| id | doaj-art-60ac731e8db94f3f8b6f8f148cd10e4b |
| institution | DOAJ |
| issn | 1999-4893 |
| language | English |
| publishDate | 2025-03-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj-art-60ac731e8db94f3f8b6f8f148cd10e4b2025-08-20T02:41:44ZengMDPI AGAlgorithms1999-48932025-03-0118314010.3390/a18030140Finding Multiple Optimal Solutions to an Integer Linear Program by Random Perturbations of Its Objective FunctionNoah Schulhof0Pattara Sukprasert1Eytan Ruppin2Samir Khuller3Alejandro A. Schäffer4Cancer Data Science Laboratory, National Cancer Institute, National Institutes of Health, Bethesda, MD 20892, USADatabricks Inc., San Francisco, CA 94105, USACancer Data Science Laboratory, National Cancer Institute, National Institutes of Health, Bethesda, MD 20892, USADepartment of Computer Science, Northwestern University, Evanston, IL 60201, USACancer Data Science Laboratory, National Cancer Institute, National Institutes of Health, Bethesda, MD 20892, USAInteger 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 <i>r</i> 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.https://www.mdpi.com/1999-4893/18/3/140integer linear programselection problemsmultiple optimarandomized algorithmsparallel algorithms |
| spellingShingle | Noah Schulhof Pattara Sukprasert Eytan Ruppin Samir Khuller Alejandro A. Schäffer Finding Multiple Optimal Solutions to an Integer Linear Program by Random Perturbations of Its Objective Function Algorithms integer linear program selection problems multiple optima randomized algorithms parallel algorithms |
| title | Finding Multiple Optimal Solutions to an Integer Linear Program by Random Perturbations of Its Objective Function |
| title_full | Finding Multiple Optimal Solutions to an Integer Linear Program by Random Perturbations of Its Objective Function |
| title_fullStr | Finding Multiple Optimal Solutions to an Integer Linear Program by Random Perturbations of Its Objective Function |
| title_full_unstemmed | Finding Multiple Optimal Solutions to an Integer Linear Program by Random Perturbations of Its Objective Function |
| title_short | Finding Multiple Optimal Solutions to an Integer Linear Program by Random Perturbations of Its Objective Function |
| title_sort | finding multiple optimal solutions to an integer linear program by random perturbations of its objective function |
| topic | integer linear program selection problems multiple optima randomized algorithms parallel algorithms |
| url | https://www.mdpi.com/1999-4893/18/3/140 |
| work_keys_str_mv | AT noahschulhof findingmultipleoptimalsolutionstoanintegerlinearprogrambyrandomperturbationsofitsobjectivefunction AT pattarasukprasert findingmultipleoptimalsolutionstoanintegerlinearprogrambyrandomperturbationsofitsobjectivefunction AT eytanruppin findingmultipleoptimalsolutionstoanintegerlinearprogrambyrandomperturbationsofitsobjectivefunction AT samirkhuller findingmultipleoptimalsolutionstoanintegerlinearprogrambyrandomperturbationsofitsobjectivefunction AT alejandroaschaffer findingmultipleoptimalsolutionstoanintegerlinearprogrambyrandomperturbationsofitsobjectivefunction |