Large scale mixed-integer optimization: A solution method with supply chain applications

In this paper we investigate lagrangian duality for a class of mixed integer programs which is of wide practical interest as it appears in many application domains, such as power systems or logistics. For this problem structure, we provide a new solution method that is simple to implement, is distributable and has convergence and performance guarantees. To obtain it, we borrow ideas and results from the convex optimization field, and exploit the special geometric features arising from the specific structure studied. The performance bound indicates that the quality of the solutions recovered improves as the size of the problem increases, making it particularly useful for very large instances. We verify the efficacy of the proposed method on industrial-sized instances of a problem stemming from supply chain optimization.