Finding a representative nondominated set for multi-objective mixed integer programs

Date

2019-01-01

Author

Ceyhan, Gokhan
Koksalan, Murat
Lokman, Banu

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

183
views

0
downloads

In this paper, we develop algorithms to find small representative sets of nondominated points that are well spread over the nondominated frontiers for multi-objective mixed integer programs. We evaluate the quality of representations of the sets by a Tchebycheff distance-based coverage gap measure. The first algorithm aims to substantially improve the computational efficiency of an existing algorithm that is designed to continue generating new points until the decision maker (DM) finds the generated set satisfactory. The algorithm improves the coverage gap value in each iteration by including the worst represented point into the set. The second algorithm, on the other hand, guarantees to achieve a desired coverage gap value imposed by the DM at the outset. In generating a new point, the algorithm constructs territories around the previously generated points that are inadmissible for the new point based on the desired coverage gap value. The third algorithm brings a holistic approach considering the solution space and the number of representative points that will be generated together. The algorithm first approximates the nondominated set by a hypersurface and uses it to plan the locations of the representative points. We conduct computational experiments on randomly generated instances of multi-objective knapsack, assignment, and mixed integer knapsack problems and show that the algorithms work well.

Subject Keywords

Representative subset, Nondominated point, Mixed integer programming, Multiple objective programming

URI

https://hdl.handle.net/11511/30626

Journal

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH

DOI

https://doi.org/10.1016/j.ejor.2018.06.012

Collections

Graduate School of Natural and Applied Sciences, Article

Suggestions

OpenMETU
Core

Generating representative nondominated point subsets in multi-objective integer programs Ceyhan, Gökhan; Köksalan, Murat; Lokman, Banu; Department of Industrial Engineering (2014) In this thesis, we study generating a subset of all nondominated points of multi-objective integer programs in order to represent the nondominated frontier. Our motivation is based on the fact that generating all nondominated points of a multi-objective integer program is neither practical nor useful. The computational burden could be prohibitive and the resulting set could be huge. Instead of finding all nondominated points, we develop algorithms to generate a small representative subset of nondominated po...
Finding all nondominated points of multi-objective integer programs LOKMAN, BANU; Köksalan, Mustafa Murat (2013-10-01) We develop exact algorithms for multi-objective integer programming (MIP) problems. The algorithms iteratively generate nondominated points and exclude the regions that are dominated by the previously-generated nondominated points. One algorithm generates new points by solving models with additional binary variables and constraints. The other algorithm employs a search procedure and solves a number of models to find the next point avoiding any additional binary variables. Both algorithms guarantee to find a...
Finding highly preferred points for multi-objective integer programs LOKMAN, BANU; Köksalan, Mustafa Murat (Informa UK Limited, 2014-01-01) 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...
Optimising a nonlinear utility function in multi-objective integer programming Ozlen, Melih; Azizoğlu, Meral; Burton, Benjamin A. (2013-05-01) In this paper we develop an algorithm to optimise a nonlinear utility function of multiple objectives over the integer efficient set. Our approach is based on identifying and updating bounds on the individual objectives as well as the optimal utility value. This is done using already known solutions, linear programming relaxations, utility function inversion, and integer programming. We develop a general optimisation algorithm for use with k objectives, and we illustrate our approach using a tri-objective i...
An interactive approximation algorithm for multi-objective integer programs Lokman, Banu; Korhonen, Pekka J.; Wallenius, Jyrki (2018-08-01) We develop an interactive algorithm that approximates the most preferred solution for any multi-objective integer program with a desired level of accuracy, provided that the decision maker's (DM's) preferences are consistent with a nondecreasing quasiconcave value function. Using pairwise comparisons of the DM, we construct convex cones and eliminate the inferior regions that are close to being dominated by the cones in addition to the regions dominated by the cones. The algorithm allows the DM to change th...

Citation Formats

G. Ceyhan, M. Koksalan, and B. Lokman, “Finding a representative nondominated set for multi-objective mixed integer programs,” EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, pp. 61–77, 2019, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/30626.