Handbook of Optimization in Telecommunications M.G.C. Resende and P.M. Pardalos (Editors) Springer Science + Business Media, 2006.
Chapter 3
Integer programming for telecommunications
E.K. Lee and D.P. Lewis
Abstract
This chapter presents an overview of integer programming in the field of telecommunications. Various integer programming models are described, and computational strategies for solving the integer programming instances are summarized. Techniques such as branching variable selection and node selection schemes are discussed; and the concepts of problem preprocessing and reformulation, heuristics, and continuous reduced-cost fixing are outlined. These latter techniques have been shown to be very effective when embedded within a branch-and-bound algorithm. The use of an interior point method as a subproblem solver is also described. Finally, Lagrangian relaxation in the context of solving specific telecommunication instances is analyzed as an alternative relaxation for use within the branch-and-bound tree search environment.
Keywords: Integer programming, preprocessing, heuristics, branching, reduced-cost fixing, branch-and-bound, interior point methods, Lagrangian relaxation, Benders' decomposition, column generation, branch-and-cut.