Generating representative nondominated point subsets in multi-objective integer programs

Ceyhan, Gökhan
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.


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...
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...
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...
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 specifically, 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 differences between algorithms of smooth optimization are in the calculation of search directions, line searches for finding step-sizes and stopping criteria. However, in nonsmoo...
Isomorphism classes of elliptic curves over finite fields of characteristic two
Kırlar, Barış Bülent; Akyıldız, Ersan; Department of Mathematics (2005)
In this thesis, the work of Menezes on the isomorphism classes of elliptic curves over finite fields of characteristic two is studied. Basic definitions and some facts of the elliptic curves required in this context are reviewed and group structure of elliptic curves are constructed. A fairly detailed investigation is made for the isomorphism classes of elliptic curves due to Menezes and Schoof. This work plays an important role in Elliptic Curve Digital Signature Algorithm. In this context, those isomorphi...
Citation Formats
G. Ceyhan, “Generating representative nondominated point subsets in multi-objective integer programs,” M.S. - Master of Science, Middle East Technical University, 2014.