Distribution based representative sets for multi-objective integer programs

Ozarik, Sami Serkan
Lokman, Banu
Koksalan, Murat
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.


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.