Alternate Optima in Combinatorial Optimization

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.