Very large-scale neighborhood search heuristics for combinatorial optimization problems

Combinatorial optimization plays an important role in decision-making since optimal decisions often depend on a nontrivial combination of various factors. Most combinatorial optimization problems are NP-hard and sharp bounds on the optimal value are typically hard to derive. This means that partial enumeration based exact algorithms have a slow convergence rate, and they can solve only small instances to optimality. But real-life combinatorial optimization problems are typically of big size and since exact approaches are inadequate, heuristics are commonly used in practice. Over the last 15 years much of the research effort has been concentrated on the development of local search heuristics. In local search methods, an intensive exploration of the solution space is performed by moving at each step from the current solution to another promising solution in its neighborhood. As a rule of thumb, there is a better probability of finding a promising solution, if the neighborhood size is larger. In this dissertation, we have developed algorithms, which perform intensive searches in a very large size neighborhood. We have used the concepts of network flow algorithms to make our algorithms computationally efficient.; In Chapter 2, we propose very large-scale neighborhood (VLSN) search algorithms for the quadratic assignment problems (QAP), and we propose a novel search procedure to enumerate good neighbors heuristically. Our search procedure relies on the concept of an improvement graph, which allows us to evaluate neighbors much faster than the existing methods. We present extensive computational results of our algorithms on a standard benchmark QAP instances. In Chapter 3, we suggest linear programming, integer programming, and network flow based lower bounding; using these methods, we obtain several branch and bound algorithms for the weapon-target assignment problem. We also propose a network flow based construction heuristic and a very large-scale neighborhood (VLSN) search algorithm. In Chapter 4, we have developed VLSN search heuristics in conjunction with tabu search to solve a university course-timetabling problem. We have developed a generic model for the problem and have performed computational experiments on randomly generated test instances.; In Chapter 5, we have given integer programming formulations of the block-to-train assignment problem; propose several exact and heuristic algorithms to solve this problem, and present computational results on the data provided by a major US railroad. In chapter 6, we have proposed a decomposition based approach to solve another railroad scheduling problem, called the train schedule design problem. We have developed VLSN search heuristics to solve the sub-problem in first phase and have formulated the problem in second phase as a minimum cost flow problem.