Distribution based representative sets for multi-objective integer programs

Date

2020-07-16

Author

Ozarik, Sami Serkan
Lokman, Banu
Koksalan, Murat

Metadata

Show full item record

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

Item Usage Stats

215
views

0
downloads

We study and exploit the characteristics of the nondominated sets of Multi-objective Integer Programs (MOIPs). We introduce a density measure and search for common properties of the distributions of nondominated points for different MOIPs. We design a procedure that categorizes the nondominated set into regions based on the densities of nondominated points. We develop an approach that generates representative sets of nondominated points using the estimated density information in different regions for general MOIPs. Experiments show that our approach is robust across different types of MOIPs.

Subject Keywords

Nondominated point, Representative set, Multi-Objective Integer Programs, Density-based quality measure

URI

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

Journal

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH

DOI

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

Collections

Graduate School of Natural and Applied Sciences, Article

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...
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...
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...
Basis reduction and the complexity of branch-and-bound Pataki, Gábor; Tural, Mustafa Kemal; Wong, Erick B. (2010-05-06) The classical branch-and-bound algorithm for the integer feasibility problem [GRAPHICS] has exponential worst case complexity. We prove that, it. is surprisingly efficient on reformulations of (01), in which the columns of the constraint, matrix are short and near orthogonal, i e, a reduced basis of the generated lattice. when the entries of A ale from {1, ,M} for a large enough M, branch-and-bound solves almost all reformulated instances at the root. node For all A matrices we prove an upper bound on th...
Power-delay optimized VLSI threshold detection circuits and their use in parallel integer multiplication Ercan, Furkan; Muhtaroğlu, Ali; Sustainable Environment and Energy Systems (2015-6) Threshold detection is a fundamental logic function that has broad use in arithmetic processors, and other digital applications. Thus, any improvement in threshold detection in terms of power and/or delay contributes significantly to the field of digital circuit design. A recently reported parallel integer multiplier architecture, ABACUS, uses column compression networks to compress partial products through the final addition network. Architecture of column compression network of ABACUS is suitable for thre...

Citation Formats

S. S. Ozarik, B. Lokman, and M. Koksalan, “Distribution based representative sets for multi-objective integer programs,” EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, pp. 632–643, 2020, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/29871.