Computational Experience with a Software Framework for Parallel Integer Programming

Autor:	Matthew J. Saltzman, Ted K. Ralphs, Laszlo Ladanyi, Yan Xu
Rok vydání:	2009
Předmět:	Software framework Theoretical computer science Computer science Branch and price General Engineering Parallel algorithm Overhead (computing) Relaxation (approximation) computer.software_genre Branch and cut Integer programming computer Integer (computer science)
Zdroj:	INFORMS Journal on Computing. 21:383-397
ISSN:	1526-5528 1091-9856
Popis:	In this paper, we discuss the challenges that arise in parallelizing algorithms for solving generic mixed integer linear programs and introduce a software framework that aims to address these challenges. Although the framework makes few algorithmic assumptions, it was designed specifically with support for implementation of relaxation-based branch-and-bound algorithms in mind. Achieving efficiency for such algorithms is particularly challenging and involves a careful analysis of the trade-offs inherent in the mechanisms for sharing the large amounts of information that can be generated. We present computational results that illustrate the degree to which various sources of parallel overhead affect scalability and discuss why properties of the problem class itself can have a substantial effect on the efficiency of a particular methodology.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::33e738e608894ca7aab245c647646f95 https://doi.org/10.1287/ijoc.1090.0347 Zobrazit plný text záznamu Plný text ve formátu PDF