Representing the nondominated set with a small subset in multi-objective mixed integer programs

Download

index.pdf

Date

2018

Author

Doğan, Ilgın

Metadata

Show full item record

Item Usage Stats

150
views

78
downloads

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 representative subset to be generated. Based on our observations, we develop algorithms to generate a small subset of nondominated points that represents the nondominated set with a prespecified coverage gap. Our computational experiments show that our algorithms outperform the existing algorithms in terms of the cardinality of the generated representative set and the solution time.

Subject Keywords

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

URI

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

Collections

Graduate School of Natural and Applied Sciences, Thesis

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 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...
Optimization of water distribution networks using mixed-integer linear programming Uzun, Eren; Altan Sakarya, Ayşe Burcu; Department of Civil Engineering (2016) The present study aims to discuss the advantages and disadvantages of the design of water distribution networks by making use of mixed integer linear programming. The developed optimization algorithm considers the minimization of the total cost as the objective function. The total cost of water distribution network is defined as cost of pipes, reservoirs and pumps. Nodal demands, nodal pressure limits and pipe velocity limits are satisfied while optimizing the network. Energy equation is the equality constr...
Converging preferred regions in multi-objective combinatorial optimization problems Lokman, Banu; Köksalan, Murat; Department of Industrial Engineering (2011) Finding the true nondominated points is typically hard for Multi-objective Combinatorial Optimization (MOCO) problems. Furthermore, it is not practical to generate all of them since the number of nondominated points may grow exponentially as the problem size increases. In this thesis, we develop an exact algorithm to find all nondominated points in a specified region. We combine this exact algorithm with a heuristic algorithm that approximates the possible locations of the nondominated points. Interacting w...

Citation Formats

I. Doğan, “Representing the nondominated set with a small subset in multi-objective mixed integer programs,” M.S. - Master of Science, Middle East Technical University, 2018.