On the resolution of general multiobjective discrete optimization problems

Tóm tắt báo cáo

In this paper, we present two new algorithms for finding the whole set of nondominated solutions for general multiobjective discrete optimization problems. One of them is our new method  based on a simple and straightforward  approach in which all nondominated solutions are obtained by solving a sequence of singleobjective problems over suitable domains.

The search regions are managed by using the variant concepts of polyblock and  copolyblock  in theory of monotonic optimization. The remaining algorithm is an improved version of the recent algorithm of Kirlik and Sayin  [A new algorithm for generating all nondominated solutions of multiobjective discrete optimization problems.  Eur. J. Oper. Res., 232: 479-488, 2014].

We show the efficiency of the new algorithms  by testing on benchmarking examples in Kirlik and Sayin's paper and other randomly generated multiobjective knapsack and multiobjective assignment problems with the higher number of criteria as well as decision variables. Our new algorithm is verified as the best of running time among them.