Dual formulations and subgradient optimization strategies for linear programming relaxations of mixed-integer programs

This paper examines algorithmic strategies relating to the formulation of Lagrangian duals, and their solution via subgradient optimization, in the context of solving linear programming relaxations of mixed-integer programs. As in the current trend in integer programming, several researchers have found it beneficial to generate and add additional constraints to the model, prior to its solution, in order to tighten its linear programming relaxation. It becomes necessary, therefore, to be able to efficiently derive strong surrogate constraints and bounds based on such reformulations. This paper addresses the design and testing of the most viable technique available for exploiting such tight reformulations, namely, using Lagrangian relaxation in coordination with subgradient optimization. A computational study is conducted to test the efficiency of various Lagrangian dual formulations, and to investigate in the context of using subgradient optimization the effects of step size choices, problem scaling, conducting pattern moves, and projecting dual solutions onto subsets of violated dual constraints. Based on this study, certain recommendations are made regarding the manner in which one should implement such an approach.