Finding all nondominated points of multi-objective integer programs

Date

2013-10-01

Author

LOKMAN, BANU
Köksalan, Mustafa Murat

Metadata

Show full item record

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

Item Usage Stats

201
views

0
downloads

We develop exact algorithms for multi-objective integer programming (MIP) problems. The algorithms iteratively generate nondominated points and exclude the regions that are dominated by the previously-generated nondominated points. One algorithm generates new points by solving models with additional binary variables and constraints. The other algorithm employs a search procedure and solves a number of models to find the next point avoiding any additional binary variables. Both algorithms guarantee to find all nondominated points for any MIP problem. We test the performance of the algorithms on randomly-generated instances of the multi-objective knapsack, multi-objective shortest path and multi-objective spanning tree problems. The computational results show that the algorithms work well.

Subject Keywords

Multiple criteria, Combinatorial optimization, Nondominated point

URI

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

Journal

JOURNAL OF GLOBAL OPTIMIZATION

DOI

https://doi.org/10.1007/s10898-012-9955-7

Collections

Department of Industrial Engineering, Article

Suggestions

OpenMETU
Core

Identifying preferred solutions in multiobjective combinatorial optimization problems Lokman, Banu (2019-01-01) We develop an evolutionary algorithm for multiobjective combinatorial optimization problems. The algorithm aims at converging the preferred solutions of a decision-maker. We test the performance of the algorithm on the multiobjective knapsack and multiobjective spanning tree problems. We generate the true nondominated solutions using an exact algorithm and compare the results with those of the evolutionary algorithm. We observe that the evolutionary algorithm works well in approximating the solutions in the...
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...
Finding highly preferred points for multi-objective integer programs LOKMAN, BANU; Köksalan, Mustafa Murat (Informa UK Limited, 2014-01-01) This article develops exact algorithms to generate all non-dominated points in a specified region of the criteria space in Multi-Objective Integer Programs (MOIPs). Typically, there are too many non-dominated points in large MOIPs and it is not practical to generate them all. Therefore, the problem of generating non-dominated points in the preferred region of the decision-maker is addressed. To define the preferred region, the non-dominated set is approximated using a hyper-surface. A procedure is developed...
An interactive approach for biobjective integer programs under quasiconvex preference functions Ozturk, Diclehan Tezcaner; Köksalan, Mustafa Murat (2016-09-01) We develop an interactive algorithm for biobjective integer programs that finds the most preferred solution of a decision maker whose preferences are consistent with a quasiconvex preference function to be minimized. During the algorithm, preference information is elicited from the decision maker. Based on this preference information and the properties of the underlying quasiconvex preference function, the algorithm reduces the search region and converges to the most preferred solution progressively. Findin...
Efficient and Accurate Electromagnetic Optimizations Based on Approximate Forms of the Multilevel Fast Multipole Algorithm Onol, Can; Karaosmanoglu, Bariscan; Ergül, Özgür Salih (2016-01-01) We present electromagnetic optimizations by heuristic algorithms supported by approximate forms of the multilevel fast multipole algorithm (MLFMA). Optimizations of complex structures, such as antennas, are performed by considering each trial as an electromagnetic problem that can be analyzed via MLFMA and its approximate forms. A dynamic accuracy control is utilized in order to increase the efficiency of optimizations. Specifically, in the proposed scheme, the accuracy is used as a parameter of the optimiz...

Citation Formats

B. LOKMAN and M. M. Köksalan, “Finding all nondominated points of multi-objective integer programs,” JOURNAL OF GLOBAL OPTIMIZATION, pp. 347–365, 2013, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/57724.