Abstract
In this paper we consider efficient parallel Branch and Bound (B&B) algorithms for Integer Linear Programming (ILP) and Mixed ILP (MILP) Problems in a MIMD distributed memory environment. The algorithms are scalable and run on a cluster of workstations under PVM. To achieve efficient parallel implementation and to speedup the computations in our approach, firstly, we apply various preprocessing techniques in order to reduce the problem size prior to optimization, and secondly, we apply B&B algorithms with dynamic distribution of tasks among the processors.
The efficiency of the algorithms has been investigated and the test results on examples from MIPLIB library and real life problems arising in Printed Circuit Boards and Multi Chip Modules layout are presented.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
D.A. Babayev and S.S. Mardanov, Reducing the Number of Variables in Integer and Linear Programming Problems, Computational Optimization and Applications, 3, 1994, pp99–109.
Bixby, Cook, Cox and Lee, Computational Experience with Parallel Mixed Integer Programming in a Distributed Environment, (submitted to Annals of Operations Research.
J. Eckstein, Parallel Branch-and-Bound Algorithm for General Integer Programming on the CM-5, TMC-257, Thinking Machines Corporation, 1993.
A. Ferreira and P. Pardalos, Solving Combinatorial Optimization Problems in Parallel, Lecture Notes in Computer Science, No 1054, Springer, 1996.
Gendron B. and Crainic T.G., Parallel Branch and Bound algorithms: survey and synthesis, Operations Research, Vol:42, pp.1042–66.
P. Indaco, PCB Final Placement by Mixed Integer Linear Optimization, MSC. Dissertation, Dec. 1996.
P.S. Laursen, Simple Approaches to Parallel Branch and Bound, Parallel Computing, 19, pp143–152, 1993.
G.L. Nemhauser and L.A.Wolsey, Integer and Combinatorial Optimization, John Wiley and Sons, 1988.
S. Sutanthavibul, E. Shragowitz, Rozen, An Analytical Approach to Floorplan Design and Optimization IEEE Transactions on Computer Aided Design, Vol. 10, No 6, June 1991.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Alonso, J.L., Schmidt, H., Alexandrov, V.N. (1997). Parallel Branch and Bound algorithms for integer and mixed integer linear programming problems under PVM. In: Bubak, M., Dongarra, J., Waśniewski, J. (eds) Recent Advances in Parallel Virtual Machine and Message Passing Interface. EuroPVM/MPI 1997. Lecture Notes in Computer Science, vol 1332. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-63697-8_99
Download citation
DOI: https://doi.org/10.1007/3-540-63697-8_99
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63697-7
Online ISBN: 978-3-540-69629-2
eBook Packages: Springer Book Archive