Dual methods in mixed integer linear programming

The primary goal of this thesis is to investigate the extent to which the dual methods available for linear programs (LPs) can be extended to the case of mixed integer linear programs (MILPs) in which a specified subset of the variables of an LP must take integer values.;A central focus of duality in the integer programming setting is the value function that returns the optimal solution value of an MILP as a function of the right-hand side. Because it is difficult to obtain the value function explicitly, we focus on methods for obtaining approximations of the value function. We first discuss methods for constructing dual functions, which bound the value function from below, and discuss how these can be obtained from primal solution algorithms including branch-and-cut, the most common method in practice for solving MILPs.;Next, we detail the results of our theoretical examination of the structure of the value function, focusing on the case of an MILP with a single constraint. We show that the value function in this case is uniquely determined by a finite number of break points and is a piecewise-linear function with at most two slopes. We derive conditions under which the value function is continuous and suggest a method for systematically extending the value function from a specified neighborhood of the origin to the entire real line. Although we focus first on the case of an MILP with a single constraint for illustration, we extend a number of these results to more general settings.;For the value function of a general MILP, we discuss approximation methods that leverage our knowledge of the value functions of single row relaxations and other dual functions. We outline methods that enable us to use these approximations as a substitute for the value function in order to solve large instances of certain classes of multi-stage mathematical programming. We illustrate these methods for both stochastic mixed integer programs and mixed integer bilevel programs.;Finally, we discuss how dual information obtained from primal solution algorithms can be used for sensitivity analysis and warm starting the solution procedure of a modified problem from an advanced level. We give computational results for various applications including iterative combinatorial auctions, capacitated vehicle routing problems, feasibility algorithms (RINS), stochastic integer and bicriteria integer programs.