Finding highly preferred points for multi-objective integer programs

Abstract

This article develops exact algorithms to generate all non-dominated points in a specified region of the criteria space in Multi-Objective Integer Programs (MOIPs). Typically, there are too many non-dominated points in large MOIPs and it is not practical to generate them all. Therefore, the problem of generating non-dominated points in the preferred region of the decision-maker is addressed. To define the preferred region, the non-dominated set is approximated using a hyper-surface. A procedure is developed that then finds a preferred hypothetical point on this surface and defines a preferred region around the hypothetical point. Once the preferred region is defined, all non-dominated points in that region are generated. The performance of the proposed approach is tested on multi-objective assignment, multi-objective knapsack, and multi-objective shortest path problems with three and four objectives. Computational results show that a small set of non-dominated points is generated that contains highly preferred points in a reasonable time.

Keywords:

• Multiple objectives
• integer programming
• non-dominated points
• preferred subset

Additional information

Notes on contributors

Banu Lokman

Banu Lokman is an Assistant Professor in the Industrial Engineering Department of TED University. She received her Ph.D. degree from the Industrial Engineering Department of the Middle East Technical University in 2011. Her dissertation was on multiple criteria combinatorial optimization. During 2005–2006, she worked for the Microelectronics, Guidance and Electro-Optics Division of ASELSAN as a planning engineer. She was a research assistant in the IE Department of METU from 2006 to 2011. From May 2012 to June 2013, she worked as a visiting researcher in the Aalto University, School of Business. Her current research interests are in different areas under the umbrella of multiple criteria decision making, including combinatorial optimization, evolutionary algorithms, and applications.

Murat Köksalan

Murat Köksalan is a Professor in the Industrial Engineering Department of the Middle East Technical University. He holds a Ph.D. degree from the Industrial Engineering Department at SUNY Buffalo. He has worked as a visiting professor at SUNY Buffalo, Purdue University, and Aalto University. He was the founding President of INFORMS Section on MCDM and is the President Elect of the International Society on MCDM. He is in the Editorial Boards of several journals. His research interests include multiple criteria decision making, combinatorial optimization, and modern heuristic search. The MCDM Gold Medal, given by the International Society on MCDM; the Science Award, given by the Parlar Foundation; the Young Investigator award of the Turkish Scientific and Technological Research Council; the first prizes in the INFORMS case competitions in 2002, 2006, 2007, and 2012, are among the awards he has received.