Full Description
Combinatorial optimization is the process of finding the best, or optimal, so lution for problems with a discrete set of feasible solutions. Applications arise in numerous settings involving operations management and logistics, such as routing, scheduling, packing, inventory and production management, lo cation, logic, and assignment of resources. The economic impact of combi natorial optimization is profound, affecting sectors as diverse as transporta tion (airlines, trucking, rail, and shipping), forestry, manufacturing, logistics, aerospace, energy (electrical power, petroleum, and natural gas), telecommu nications, biotechnology, financial services, and agriculture. While much progress has been made in finding exact (provably optimal) so lutions to some combinatorial optimization problems, using techniques such as dynamic programming, cutting planes, and branch and cut methods, many hard combinatorial problems are still not solved exactly and require good heuristic methods. Moreover, reaching "optimal solutions" is in many cases meaningless, as in practice we are often dealing with models that are rough simplifications of reality. The aim of heuristic methods for combinatorial op timization is to quickly produce good-quality solutions, without necessarily providing any guarantee of solution quality. Metaheuristics are high level procedures that coordinate simple heuristics, such as local search, to find solu tions that are of better quality than those found by the simple heuristics alone: Modem metaheuristics include simulated annealing, genetic algorithms, tabu search, GRASP, scatter search, ant colony optimization, variable neighborhood search, and their hybrids.
Contents
1 A path relinking algorithm for the generalized assignment problem.- 2 The PROBE metaheuristic for the multiconstraint knapsack problem.- 3 Lagrangian heuristics for the linear ordering problem.- 4 Enhancing MA performance by using matching-based recombination.- 5 Multi-cast ant colony system for the bus routing problem.- 6 Study of genetic algorithms with crossover based on confidence intervals as an alternative to classical least squares estimation methods for nonlinear models.- 7 Variable neighborhood search for nurse rostering problems.- 8 A Potts neural network heuristic for the class/teacher timetabling problem.- 9 Genetic algorithms for the single source capacitated location problem.- 10 An elitist genetic algorithm for multiobjective optimization.- 11 HSF: The iOpt's framework to sasily design metaheuristic methods.- 12 A distance-based selection of parents in genetic algorithms.- 13 Experimental pool design: Input, output and combination strategies for scatter search.- 14 Evolutionary proxy tuning for expensive evaluation functions: A real-case application to petroleum reservoir optimization.- 15 An analysis of solution properties of the graph coloring problem.- 16 Developing classification techniques from biological databases using simulated annealing.- 17 A new look at solving minimax problems with coevolutionary genetic algorithms.- 18 A performance analysis of tabu search for discrete-continuous scheduling problems.- 19 Elements for the description of fitness landscapes associated with local operators for layered drawings of directed graphs.- 20 Training multi layer perceptron network using a genetic algorithm as a global optimizer.- 21 Metaheuristics applied to power systems.- 22 On the behavior of ACO algorithms: Studies on simple problems.- 23Variable neighborhood search for the k-cardinality tree.- 24 Heuristics for large strip packing problems with guillotine patterns: An empirical study.- 25 Choosing search heuristics by non-stationary reinforcement learning.- 26 GRASP for linear integer programming.- 27 Random start local search and tabu search for a discrete lot-sizing and scheduling problem.- 28 New benchmark instances for the Steiner problem in graphs.- 29 A memetic algorithm for communication network design taking into consideration an existing network.- 30 A GRASP heuristic for the capacitated minimum spanning tree problem using a memory-based local search strategy.- 31 A GRASP-tabu search algorithm for school timetabling problems.- 32 A local search approach for the pattern restricted one dimensional cutting stock problem.- 33 An ant system algorithm for the mixed vehicle routing problem with backhauls.
