Finding diverse optima and near-optima to binary integer programs

摘要

Typical output from an optimization solver is a single optimal solution. There are contexts, however, where a set of high-quality and diverse solutions may be beneficial; for example, problems involving imperfect information or those for which the structure of high-quality solution vectors can reveal meaningful insights. In view of this, we discuss a novel method to obtain multiple diverse optima / near optima to pure binary (0-1) integer programs, employing fractional programming techniques to manage these typically competing goals. Specifically, we develop a general approach that makes use of Dinkelbach's algorithm to sequentially generate solutions that evaluate well with respect to both (ⅰ) individual performance and as a whole and (ⅱ) mutual variety. We assess the performance of our approach on a number of MIPLIB test instances from the literature. Using two diversity metrics, computational results show that our method provides an efficient way to optimize the fractional objective while sequentially generating multiple high-quality and diverse solutions.