Hybrid algorithms for combinatorial optimization problems.

摘要

Many real-world operational level optimization problems contain several challenges: the problem sizes are often very large and frequently the problems are time-sensitive in nature. Hence the effectiveness of a solution depends on both its quality and the speed at which it can be generated. The problems are often NP-hard and therefore it is unlikely that one will find fast algorithms that will be guaranteed to solve them to optimality.; In this dissertation, different methods are proposed to hybridize exact methods with heuristics for solving combinatorial optimization problems with the aim of combining the strengths of both approaches to find better quality solutions within a reasonable amount of computational time.; The first approach used in this dissertation is the divide-and-merge algorithm, which divides the given instance into smaller instances, optimizes these instances and then merges their solutions to obtain a complete solution to the original problem.; The second approach is the reduce-and-optimize algorithm, which is based on solving the problem over a small subset of the solution space with the goal that this reduced space contains the optimal solution. The interval-indexed formulation, and Integer Programming and Linear Programming-based heuristics are introduced for solving single machine scheduling problems.; The reduce-and-optimize approach can be used to improve a set of solutions obtained by other heuristics. To illustrate this, the interval-indexed formulation based heuristic is used to improve a population of a genetic algorithm as the third approach. The interval-indexed based heuristic is applied at each iteration of the genetic algorithm and the population is updated based on the solutions obtained.; Ways to improve the intervals of the interval-indexed formulation are also studied as the fourth approach. A linear programming based approach is suggested and computational experiments give promising results.; To test the approaches introduced, single machine total weighted tardiness problem instances are used. But the algorithms that are introduced in the dissertation can be generalized and applied to many other scheduling and combinatorial optimization problems, with small modifications in the algorithms.