Generating representative nondominated point subsets in multi-objective integer programs

Download

index.pdf

Date

2014

Author

Ceyhan, Gökhan

Metadata

Show full item record

Item Usage Stats

184
views

109
downloads

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 points. In order to assess the quality of representative subsets, we conduct computational experiments on randomly generated instances of combinatorial optimization problems and show that the algorithms work well.

Subject Keywords

Integer programming., Programming (Mathematics)., Mathematical optimization.

URI

http://etd.lib.metu.edu.tr/upload/12617675/index.pdf
https://hdl.handle.net/11511/23908

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

Finding a representative nondominated set for multi-objective mixed integer programs Ceyhan, Gokhan; Koksalan, Murat; Lokman, Banu (2019-01-01) 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 sat...
Representing the nondominated set with a small subset in multi-objective mixed integer programs Doğan, Ilgın; Lokman, Banu; Köksalan, M. Murat; Department of Industrial Engineering (2018) Multi-Objective Mixed Integer Programs (MOMIPs) have a wide variety of application areas in real-life decision making problems. Since the number of nondominated points grows exponentially with the problem size and finding all nondominated points is typically hard and impractical in MOMIPs, generating a subset having “desired properties” rises as an important problem. Motivated with this fact, we observe that the distribution of nondominated points may be critical in defining the desired properties of the re...
Optimization approaches for classification and feature selection using overlapping hyperboxes Akbulut, Derya; Özdemirel, Nur Evin; İyigün, Cem; Department of Industrial Engineering (2019) In this thesis, an optimization approach is proposed for the binary classification problem. A mixed integer programming (MIP) model formulation is used to generate hyperboxes as classifiers. The hyperboxes are determined by lower and upper bounds on the feature values, and overlapping of hyperboxes is allowed to reach a balance between misclassification and overfitting. For the test phase, distance-based heuristic algorithms are also developed to classify the overlap and uncovered samples that are not class...
Derivative free algorithms for large scale non-smooth optimization and their applications Tor, Ali Hakan; Karasözen, Bülent; Department of Mathematics (2013) In this thesis, various numerical methods are developed to solve nonsmooth and in particular, nonconvex optimization problems. More speciﬁcally, three numerical algorithms are developed for solving nonsmooth convex optimization problems and one algorithm is proposed to solve nonsmooth nonconvex optimization problems. In general, main diﬀerences between algorithms of smooth optimization are in the calculation of search directions, line searches for ﬁnding step-sizes and stopping criteria. However, in nonsmoo...
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...

Citation Formats

G. Ceyhan, “Generating representative nondominated point subsets in multi-objective integer programs,” M.S. - Master of Science, Middle East Technical University, 2014.