Classical optimization methods determine a single optimal or near-optimal solution for a decision problem. In many applications, however, the decision maker is interested in evaluating a pool of high-quality solutions, to encode fairness-oriented criteria or to obtain a portfolio of alternatives to use in case of unexpected scenarios.
In this paper, we consider the problem of computing a pool of near-optimal solutions to a given optimization problem while maximizing their total pairwise distance.
In particular, we focus on Mixed-Integer Linear Programming (MILP) problems where a subset of variables are binary and consider the Hamming distance over these variables.
We introduce mathematical formulations for the problem, including one model having an exponential number of variables, for which we develop a column-generation based algorithm.
Computational experiments show that, for general MILPs, our modelling framework and solution approaches allow to obtain more diverse pools of solutions compared with the existing literature. Furthermore, for a specific application to the assignment problem, we are able to attack instances of large size in a reasonable amount of time.