Optimization Online


Finding Diverse Solutions of High Quality to Binary Integer Programs

Andrew C. Trapp(atrapp***at***wpi.edu)
Renata A. Konrad(rkonrad***at***wpi.edu)

Abstract: 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.

Keywords: binary (0–1) integer programming; fractional programming; Dinkelbach’s algorithm; decision making; multiple solutions; solution diversity; solution quality

Category 1: Nonlinear Optimization (Other )

Category 2: Integer Programming (0-1 Programming )

Category 3: Other Topics (Multi-Criteria Optimization )

Citation: Technical Report October, 2013 School of Business Worcester Polytechnic Institute 100 Institute Rd., Worcester, MA 01609, USA

Download: [PDF]

Entry Submitted: 10/31/2013
Entry Accepted: 10/31/2013
Entry Last Modified: 10/31/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society