Integer programming based search

When integer programming (IP) models are used in operational situations there is a need to consider the tradeoff between the conflicting goals of solution quality and solution time, since for many problems solving realistic-size instances to a tight tolerance is still beyond the capability of state-of-the-art solvers. However, by appropriately defining small instances, good primal solutions frequently can be found quickly. We explore this approach in this thesis by studying the design of algorithms that produce solutions to an integer program by solving restrictions of the problem via integer programming technology. We refer to this type of algorithm as IP-based search.;This approach is also taken, for example, within LP-based branch-and-bound algorithms using techniques such as Local Branching and Relaxation Induced Neighborhood Search (RINS). These techniques use information from the LP solution and incumbent solution to define a small IP, which is then optimized. These techniques can be applied to any integer program and are available in commercial solvers such as CPLEX. We develop new IP-based search approaches for specific problems that exploit problem structure and an approach that can be easily applied to general integer programs. Finally, we leverage some of the strengths of IP-based search to develop new and more accurate models of a network design problem faced by freight transportation carriers.;In the first part of the thesis we present a heuristic for the classical Multi-Commodity Fixed Charge Network Flow (MCFCNF) model that exploits problem structure to produce high quality solutions quickly. The solution approach combines mathematical programming and heuristic search techniques. To obtain high-quality solutions it relies on neighborhood search with neighborhoods that involve solving carefully chosen integer programs derived from the arc-based formulation of MCFCNF. To obtain lower bounds, the linear programming relaxation of the path-based formulation is used and strengthened with cuts discovered during the neighborhood search. Computational experiments demonstrate that the proposed approach outperforms both best-known meta-heuristics and a state-of-the-art MIP solver.;In the second part of the thesis we present an IP-based search algorithm for mixed integer programs that does not depend on problem structure. We formalize IP-based search as solving a restriction of the original problem and then develop an extended formulation to model the choice of restriction to solve. We propose a parallelized branch-and-price scheme for solving the extended formulation that is designed to produce high quality solutions quickly. We illustrate the application of the algorithm on the MCFCNF and computational experiments indicate it is competitive both with a state-of-the-art MIP solver and the structure-based heuristic presented in the previous part, even though it is a more general algorithm.;Lastly, the thesis addresses the applicability of IP-based search to a real-world problem; namely the Service Network Design problem faced by Less-Than-Truckload (LTL) freight transportation carriers. In this part we present advances both in modeling and algorithm design. The developed models more accurately capture key operations of today's carriers: decisions for loaded and empty trailer movements are considered simultaneously, and a time discretization is used that can appropriately model the timing of freight consolidation opportunities. Along with providing decision support for traditional service network plans used by LTL carriers, the models also enable the development of plans that allow more flexibility, such as allowing certain freight routes to vary by weekday. Given the additional detail within the proposed models, very large problem instances result when they are applied to large-scale LTL networks. Yet computational experiments using data from a large U.S. carrier demonstrate that the proposed modeling and IP-based search approach has the potential to generate significant cost savings.