Large scale integer programming: A novel solution method and application.

摘要

Integer programming is a powerful modeling tool for a variety of decision making problems such as in telecommunications network design and in routing and scheduling. Integer programming models of realistic problems are large in size and pose serious challenge to available software. This creates an urgent need for solution methodologies that can deal with their size and complexity. In this thesis, we focus on the theoretical development, implementation and testing of a novel methodology: an interior-point branch-and-price algorithm with cut generation for large scale integer programming.; The methodology applies to any integer program but is built for a general class of integer programming that has a large, possibly exponential set of constraints. It starts by applying a decomposition method to the complicating constraints. We focus on Lagrangian relaxation or Dantzig-Wolfe decomposition; both lead to a master problem with an exponential number of variables and constraints. The same analysis applies when one starts by relaxing the exponential constraints and then applying a decomposition method. In both cases, one has to solve iteratively a master problem that is updated by appending violated cuts and columns. For that, we propose a cut and column generation algorithm based on analytic centers.; The cut and column generation algorithm solves a restricted master problem using a primal analytic center cutting plane method to obtain a bound on the original problem. The bound may be poor in quality since most of the complicating constraints are relaxed. To strengthen the bound, we generate violated constraints and append them to the master problem. At this point we use available information to warm-start the solution of the updated restricted master problem. This is done using a dual Newton method to calculate the next analytic center, after which we proceed with the primal method.; The bound is then embedded within a branch-and-bound algorithm leading to a branch-and-price algorithm. In fact, the algorithm is more than a branchand-price since it is able to deal with valid cuts added at the level of the master problem. This is a major step towards an interior-point branch-andcut-and-price algorithm. For an efficient integration of the cut and column generation algorithm within branch-and-bound, we use available information from a parent node to warm-start the calculation of the bound at child nodes. This is achieved by a dual Newton method. (Abstract shortened by UMI.)