Computational Experience with a Software Framework for Parallel Integer Programming

References

• Achterberg T., Koch T., Martin A. Branching rules revisited. Oper. Res. Lett. (2005) 33(1):42–54Crossref, Google Scholar
• Achterberg T., Koch T., Martin A. MIPLIB 2003. Oper. Res. Lett. (2006) 34(4):1–12Crossref, Google Scholar
• Amdahl G. M. Validity of the single-processor approach to achieving large-scale computing capabilities. AFIPS Conf. Proc. (1967) (ACM Press, New York) 483–485Crossref, Google Scholar
• Applegate D., Bixby R., Chvátal V., Cook W.The Traveling Salesman Problem: A Computational Study (2006) (Princeton University Press, Princeton, NJ) Google Scholar
• Atamtürk A. Berkeley computational optimization lab data sets. (2007) . http://ieor.berkeley.edu/∼atamturk/dataGoogle Scholar
• Bénichou M., Gautheier J. M., Girodet P., Hentges G., Ribière G., Vincent O. Experiments in mixed-integer linear programming. Math. Programming (1971) 1(1):76–94Crossref, Google Scholar
• Benchouche M., Cung V.-D., Dowaji S., Le Cun B., Mautor T., Roucairol C. Building a parallel branch and bound library. Solving Combinatorial Optimization Problems in Parallel (1996) 1054(Springer, Berlin) 201–231Lecture Notes in Computer ScienceCrossref, Google Scholar
• Borbeau B., Crainic T. G., Gendron B. Branch-and-bound parallelization strategies applied to a depot location and container fleet management problem. Parallel Comput. (2000) 26(1):27–46Crossref, Google Scholar
• Brown R. G. Engineering a Beowulf-style compute cluster. (2004) . http://www.phy.duke.edu/∼rgb/Beowulf/beowulf_book/beowulf_book/Google Scholar
• Chen Q., Ferris M. FATCOP: A fault tolerant Condor-PVM mixed integer programming solver. SIAM J. Optim. (2001) 11(4):1019–1036Crossref, Google Scholar
• CORAL Laboratory CORAL data sets. (2009) . http://coral.ie.lehigh.edu/instances.htmlGoogle Scholar
• Dakin R. J. A tree-search algorithm for mixed integer programming problems. Comput. J. (1965) 8(3):250–255Crossref, Google Scholar
• Eckstein J., Phillips C. A., Hart W. E. PICO: An object-oriented framework for parallel branch and bound. (2000) . Technical Report RRR 40-2000, Rutgers University, Piscataway, NJGoogle Scholar
• Eckstein J., Phillips C. A., Hart W. E. PEBBL 1.0 user guide, https://software.sandia.gov/Acro/releases/votd/acro/packages/pebbl/doc/uguide/user-guide.pdf. (2007) Google Scholar
• Fonlupt C., Marquet P., Dekeyser J. Data-parallel load balancing strategies. Parallel Comput. (1998) 24(11):1665–1684Crossref, Google Scholar
• Forrest J. J. COIN-OR branch-and-cut MIP solver. (2003) . https://projects.coin-or.org/CbcGoogle Scholar
• Geist A., Beguelin A., Dongarra J., Jiang W., Manchek R., Sunderam V. S.PVM: Parallel Virtual Machine: A Users' Guide and Tutorial for Networked Parallel Computing (1994) (MIT Press, Cambridge, MA) Crossref, Google Scholar
• Gendron B., Crainic T. G. Parallel branch-and-bound algorithms: Survey and synthesis. Oper. Res. (1994) 42(6):1042–1066Link, Google Scholar
• Gendron B., Crainic T. G., Frangioni A., Guertin F. Oobb: Object-oriented tools for parallel branch-and-bound. (2005) Presentation, Fourth International Workshop of the Euro Working Group on Parallel Processing in Operations Research (PAREO 2005)January 18(Centre for Research on Transportation, Université de Montréal, Montréal) Google Scholar
• Gropp W., Lusk E., Skjellum A.Using MPI (1999) 2nd ed.(MIT Press, Cambridge, MA) Google Scholar
• Henrich D. Initialization of parallel branch-and-bound algorithms. Proc. 2nd Internat. Workshop Parallel Processing Artificial Intelligence (PPAI-93) (1993) (Chamberry, France) Google Scholar
• Kumar V., Rao V. N. Parallel depth-first search. Part II: Analysis. Internat. J. Parallel Programming (1987) 16(6):501–519Crossref, Google Scholar
• Kumar V., Grama A. Y., Vempaty N. R. Scalable load balancing techniques for parallel computers. J. Parallel Distributed Comput. (1994) 22(1):60–79Crossref, Google Scholar
• Land A. H., Doig A. G. An automatic method for solving discrete programming problems. Econometrica (1960) 28(3):497–520Crossref, Google Scholar
• Laursen P. S. Can parallel branch and bound without communication be effective? SIAM J. Optim. (1994) 4(2):288–296Crossref, Google Scholar
• Linderoth J. Topics in parallel integer optimization. (1998) . Ph.D. thesis, School of Industrial and Systems Engineering, Georgia Institute of Technology, AtlantaGoogle Scholar
• Lougee-Heimer R. The common optimization interface for operations research. IBM J. Res. Development (2003) 47(1):57–66Crossref, Google Scholar
• Martello S., Toth P.Knapsack Problems: Algorithms and Computer Implementations (1990) 1st ed.(John Wiley & Sons, Inc., Chichester, West Sussex, UK) Google Scholar
• Mitten L. G. Branch-and-bound methods: General formulation and properties. Oper. Res. (1970) 18(1):24–34Link, Google Scholar
• Pfetsch M. Markshare instances. (2005) . http://miplib.zib.de/contrib/MarkshareGoogle Scholar
• Ralphs T. K., Talbi E. Parallel branch and cut. Parallel Combinatorial Optimization (2006) (John Wiley & Sons, Hoboken, NJ) 53–102Crossref, Google Scholar
• Ralphs T. K., Güzelsoy M. SYMPHONY version 5.1 user's manual. (2008) . http://www.brandandcut.orgGoogle Scholar
• Ralphs T. K., Ladányi L. COIN/BCP user's manual. (2001) . http://www.coin-or.org/Presentations/bcp-man.pdfGoogle Scholar
• Ralphs T. K., Ladányi L., Saltzman M. J. Parallel branch, cut, and price for large-scale discrete optimization. Math. Programming (2003) 98(1–3):253–280Crossref, Google Scholar
• Ralphs T. K., Ladányi M. J., Saltzman L. A library hierarchy for implementing scalable parallel search algorithms. J. Supercomputing (2004) 28(2):215–234Crossref, Google Scholar
• Reed D. A. Grids, the teragrid, and beyond. Computer (2003) 36(1):62–68Crossref, Google Scholar
• Sanders P. Tree shaped computations as a model for parallel applications. (1998) Presentation, ALV'98 Workshop on Application Based Load Balancing, SFB 342(Technische Universität Munchen, Germany) . http://www.mpi-sb.mpg.de/∼sanders/papers/alv.ps.gzGoogle Scholar
• Shinano Y., Fujie T., Cappello F., Herault T., Dongarra J. ParaLEX: A parallel extension for the CPLEX mixed integer optimizer. Recent Advances in Parallel Virtual Machine and Message Passing Interface (2007) (Springer, Berlin) 97–106Crossref, Google Scholar
• Shinano Y., Harada K., Hirabayashi R. A generalized utility for parallel branch and bound algorithms. Proc. 1995 Seventh Sympos. Parallel and Distributed Processing (1995) (IEEE Computer Society Press, Los Alamitos, CA) 392–401Crossref, Google Scholar
• Sinha A., Kalé L. V. A load balancing strategy for prioritized execution of tasks. Seventh Internat. Parallel Processing Sympos. (1993) (Newport Beach, CA)230–237Crossref, Google Scholar
• Thain D., Tannenbaum T., Livny M. Distributed computing in practice: The Condor experience. Concurrency—Practice and Experience (2005) 17(2–4):323–356Crossref, Google Scholar
• Trienekens H. W. J. M., de Bruin A. Towards a taxonomy of parallel branch and bound algorithms. (1992) . Technical Report EUR-CS-92-01, Department of Computer Science, Erasmus University, Rotterdam, The NetherlandsGoogle Scholar
• Tschoke S., Polzer T. Portable parallel branch and bound library. (2008) . http://wwwcs.uni-paderborn.de/∼ppbb-lib/ppbblib.htmlGoogle Scholar
• Xu Y. Scalable algorithms for parallel tree search. (2007) . Ph.D. thesis, Department of Industrial and Systems Engineering, Lehigh University, Bethlehem, PAGoogle Scholar