Typical output from an optimization solver is a single optimal solution. At the same time, a set of high-quality and diverse solutions could be beneficial in a variety of contexts, 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 new method to obtain multiple high-quality yet diverse solutions 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 i) individual performance and, as a whole, ii) mutual variety. Experiments on a number of test instances yield encouraging computational results.
Citation
Technical Report October, 2013 School of Business Worcester Polytechnic Institute 100 Institute Rd., Worcester, MA 01609, USA