TAILIEUCHUNG - Variable neighborhood search for maximum diverse grouping problem

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. | Yugoslav Journal of Operations Research 24 (2014) Number 1, 21-33 DOI: VARIABLE NEIGHBORHOOD SEARCH FOR MAXIMUM DIVERSE GROUPING PROBLEM Dragan UROŠEVIĆ Mathematical Institute SANU draganu@ Received: December 2012 / Accepted: January 2013 Abstract: 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. Keywords: Combinatorial optimization, Maximum Diverse Grouping, Metaheuristics, Variable Neighborhood Search. MSC: 90C59, 90C27, 90C06, 90C20. 1. INTRODUCTION The maximum diverse grouping problem (MDGP) consists of finding a way to divide a set of n elements into m mutually disjoint groups so that the total diversity among the elements belonging to the same group is maximized. The diversity among the elements in a group is calculated as the sum of the individual distance between each pair of elements. The objective of the problem is to maximize the overall diversity, ., the sum of the diversity of all groups. Feo and Khellaf [10] proved that the MDGP is NP-hard. The MDGP is also known as the k-partition problem (Feo et al. [9]), and the equitable partition problem (Mingers and O’Brien [17], O’Brien and Mingers [20]) that appears in a wide range of real life situations. The first application is in designing of VLSI circuits (Chen [4]; Feo and Khellaf [10]). Also, it can be applied in storing large programs onto paged memory (Kral, [15]), where the subroutines of a program have to be stored onto pages of available memory. In this case, the objective is to maximize data transfer between subroutines on D. Urošević / Variable Neighborhood Search 22 the same page (minimizing in this way .

• Toán học
• Combinatorial optimization
• Maximum Diverse Grouping
• Variable Neighborhood Search
• Extensive computational
• Diversity problem
• Ecosystem management
• Combinatorial optimization techniques
• Meta heuristic
• Economical values
• Probabilistic Combinatorial Optimization
• Probabilistic Graph problems
• Probabilistic Minimum Coloring
• The Probabilistic Longest Path
• Probabilistic Minimum Vertex
• the Probabilistic Maximum Independen
• Efficient transformations
• Generalized combinatorial optimization problems
• Integer programming
• Graph into node sets
• Extremal graph theory
• Mathematical programming
• Efficient algorithms
• Information sciences
• Multiobjective combinatorial optimization problems
• Well spread set
• Well spread non dominated points
• State of the art
• Ebook Linear optimization
• Linear optimization
• Linear extensions
• Projective algorithms
• Ellipsoid algorithms
• Optimization software
• Minimum cost network flow problem
• Optimization software packages
• Meta–Heuristic methods
• Swarm intelligence
• Scheduling problems
• Foraging habits of honeybees
• Center location problems
• Reverse optimization
• Tree graphs
• Time complexity
• Hamming norms
• Gaussian variable neighborhood search
• File transfer scheduling problem
• Optimization problems
• Báo cáo sinh học hay
• cách trình bày báo cáo
• báo cáo sinh học
• công trình nghiên cứu sinh học
• tài liệu về sinh học
• Dynamic memory allocation Ppblem
• Regarding quality
• Metaheuristic approach
• Transportation problem
• Bottleneck transportation problem
• Bi criteria transportation problem
• Efficient points
• Salesman problem
• System of vertexr equisitions
• Local search
• Efficient point
• Evolutionary algorithms
• Runtime analysis
• Fitness level
• Strong metric dimension
• Graph problems
• Computational approaches
• Historical and scientific framework
• Music generation
• Evolutionary approach
• Algorithm composing
• Music compositions
• Genetic Algorithm
• Optimal Recombination Problem
• Boolean Linear Programming
• Optimal recombination
• Operations research
• Exteriorpoint simplex type
• Network dual simplex algorithm
• Electromagnetism like metaheuristic
• Maximum set splitting problem
• Steiner triple systems
• Fast implementation
• Evolutionary computation
• Graph coloring problem
• Bandwidth multicoloring problem
• Bandwidth coloring problem
• Quadratic assignment problem
• Modified genetic operators
• Weighted graphs
• Minimal branching
• Asymetric weight matrix
• Minimal s branching