Consistent neighborhood search for combinatorial optimization
Summary: Many optimization problems (from academia or industry) require the use of a local search to find a satisfying solution in a reasonable amount of time, even if the optimality is not guaranteed. Usually, local search algorithms operate in a search space which contains complete solutions (feasible or not) to the problem. In contrast, in consistent neighborhood search (CNS), after each variable assignment, the conflicting variables are deleted to keep the partial solution feasible, and the search can stop when all the variables have a value. In this paper, we formally propose a new heuristic solution method, CNS, which has a search behavior between exhaustive tree search and local search working with complete solutions. We then discuss, with a unified view, the great success of some existing heuristics, which can however be considered within the CNS framework, in various fields: graph coloring, frequency assignment in telecommunication networks, vehicle fleet management with maintenance constraints, and satellite range scheduling. Moreover, some lessons are given in order to have guidelines for the adaptation of CNS to other problems.
- A ``logic-constrained knapsack formulation and a tabu algorithm for the daily photograph scheduling of an earth observation satellite
- A graph coloring heuristic using partial solutions and a reactive tabu scheme
- A heuristic approach for antenna positioning in cellular networks
- A metaheuristic approach for the vertex coloring problem
- A solution method for a car fleet management problem with maintenance constraints
- A survey of local search methods for graph coloring
- An adaptive memory algorithm for the k-coloring problem
- Bounding the optimum for the problem of scheduling the photographs of an agile Earth observing satellite
- Consistent neighborhood search for combinatorial optimization
- Earth observation satellite management
- Efficient filtering and tabu search on a consistent neighbourhood for the frequency assignment problem with polarisation
- Graph colouring approaches for a satellite range scheduling problem
- Guided local search and its application to the traveling salesman problem
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1062113 (Why is no real title available?)
- scientific article; zbMATH DE number 956854 (Why is no real title available?)
- Hybrid evolutionary algorithms for graph coloring
- Optimization by simulated annealing
- Resolution search
- Tabu Search—Part I
- The dynamic frequency assignment problem
- The noising method: A new method for combinatorial optimization
- Using tabu search techniques for graph coloring
- Variable neighborhood search
- Across neighborhood search for numerical optimization
- A generalized variable neighborhood search for combinatorial optimization problems
- scientific article; zbMATH DE number 2156686 (Why is no real title available?)
- A Generalized Consistent Neighborhood Search for Satellite Range Scheduling Problems
- Consistency checking within local search applied to the frequency assignment with polarization problem
- Consistent neighborhood search for combinatorial optimization
This page was built for publication: Consistent neighborhood search for combinatorial optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q693704)
