Generalized combinatorial optimization problems

This paper presents a general variable neighborhood search (GVNS) heuristic for solving the maximum diverse grouping problem. Extensive computational experiments performed on a series of large random graphs as well as on several instances of the maximum diversity problem taken from the literature show that the results obtained by GVNS consistently outperform the best heuristics from the literature.

13p vinguyentuongdanh 19-12-2018 26 0   Download

Classical combinatorial optimization problems can be generalized in a natural way by considering a related problem relative to a given partition of the nodes of the graph into node sets. In the literature one can find generalized problems such as: Generalized minimum spanning tree, generalized traveling salesman problem, generalized Steiner tree problem, generalized vehicle routing problem, etc. These generalized problems typically belong to the class of NP-complete problems.

12p vinguyentuongdanh 19-12-2018 35 2   Download

Upon reading Cook’s paper, I realized at once that his concept of an archetypal combinatorial problem was a formalization of an idea that had long been part of the folklore of combinatorial optimization. Workers in that field knew that the integer programming problem, which is essentially the problem of deciding whether a system of linear inequalities has a solution in integers, was general enough to express the constraints of any of the commonly encountered combinatorial optimization problems. Dantzig had published a paper on that theme in 1960.

0p ledung 13-03-2009 96 5   Download