Journal of Applied Mathematics
Volume 2013 (2013), Article ID 678783, 11 pages
Research Article

A Hybrid Approach of Bundle and Benders Applied Large Mixed Linear Integer Problem

1University of Fortaleza (UNIFOR), Graduate Program in Applied Informatics, Avenida Washington Soares 1321, 60811-905 Fortaleza, CE, Brazil
2Federal University of Rio de Janeiro, Computing and Systems Engineering Department, 21945-970 Rio de Janeiro, RJ, Brazil

Received 2 February 2013; Accepted 19 May 2013

Academic Editor: Farhad Hosseinzadeh Lotfi

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.


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.