Alternate Optima in Combinatorial Optimization

Marc Benito-Marimón (), Anna Martínez-Gavara () and Rafael Martí ()
Additional contact information
Marc Benito-Marimón: Universidad de Valencia
Anna Martínez-Gavara: Universidad de Valencia
Rafael Martí: University of Valencia, Operations Research and Statistics Department, School of Mathematics

Chapter 34 in Handbook of Heuristics, 2025, pp 1011-1029 from Springer

Abstract: Abstract This chapter explores the importance of studying the entire set of optimal solutions in combinatorial optimization problems, rather than focusing solely on a single optimum. Understanding alternate optima is crucial for robust decision-making and comprehensive problem analysis. Using the Linear Ordering Problem (LOP) as a primary example, we illustrate how multiple optimal rankings can lead to significantly different interpretations of results, potentially affecting real-world decisions. This chapter discusses various motivations for considering the optimal solution set, including improved insight into problem structure, enhanced stability analysis, and more accurate decision support. We examine how this approach can reveal hidden trade-offs, identify critical variables, and provide a more complete understanding of the solution space. By highlighting these motivations across various domains, we aim to encourage a shift in perspective within the field of combinatorial optimization, promoting more thorough and reliable analysis of complex problems. Although single optimum models can be extended to identify multiple optimal solutions, they have important limitations to target medium and large instances, as can be expected. We illustrate this typical performance on the LOP and how heuristics constitute a practical alternative.

Keywords: Multiple optimal solutions; Linear ordering problem; Variable neighborhood search metaheuristics (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-032-00385-0_81

Ordering information: This item can be ordered from
http://www.springer.com/9783032003850

DOI: 10.1007/978-3-032-00385-0_81

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().