Copyright © 2013 Placido Rogerio Pinheiro and Paulo Roberto Oliveira. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

Consider a large mixed integer linear problem where structure of the constraint matrix is sparse, with independent blocks, and coupling constraints and variables. There is one of the groups of constraints to make difficult the application of Benders scheme decomposition. In this work, we propose the following algorithm; a Lagrangian relaxation is made on the mentioned set of constraints; we presented a process heuristic for the calculation of the multiplier through the resolution of the dual problem, structured starting from the bundle methods. According to the methodology proposed, for each iteration of the algorithm, we propose Benders decomposition where quotas are provided for the value function and -subgradient.