More Web Proxy on the site http://driver.im/

article

FiberSCIP-A Shared Memory Parallelization of SCIP

Authors:

Stefan Vigerske,

Michael WinklerAuthors Info & Claims

INFORMS Journal on Computing, Volume 30, Issue 1

Pages 11 - 30

Published: 01 February 2018 Publication History

Abstract

Recently, parallel computing environments have become significantly popular. In order to obtain the benefit of using parallel computing environments, we have to deploy our programs for these effectively. This paper focuses on a parallelization of SCIP Solving Constraint Integer Programs, which is a mixed-integer linear programming solver and constraint integer programming framework available in source code. There is a parallel extension of SCIP named ParaSCIP, which parallelizes SCIP on massively parallel distributed memory computing environments. This paper describes FiberSCIP, which is yet another parallel extension of SCIP to utilize multi-threaded parallel computation on shared memory computing environments, and has the following contributions: First, we present the basic concept of having two parallel extensions, and the relationship between them and the parallelization framework provided by UG Ubiquity Generator, including an implementation of deterministic parallelization. Second, we discuss the difficulties in achieving a good performance that utilizes all resources on an actual computing environment, and the difficulties of performance evaluation of the parallel solvers. Third, we present a way to evaluate the performance of new algorithms and parameter settings of the parallel extensions. Finally, we demonstrate the current performance of FiberSCIP for solving mixed-integer linear programs MIPs and mixed-integer nonlinear programs MINLPs in parallel.

The online appendix is available at <ext-link ext-link-type="uri" href="https://doi.org/10.1287/ijoc.2017.0762">https://doi.org/10.1287/ijoc.2017.0762</ext-link>.

References

[1]

Achterberg T (2007) Constraint integer programming. Doctoral thesis, Technische Universität, Berlin.

[2]

Achterberg T, Koch T, Martin A (2006) MIPLIB 2003. Oper. Res. Lett. 34(4):1-12.

Digital Library

[3]

Bendjoudi A, Melab N, Talbi EG (2012) An adaptive hierarchical master-worker (AHMW) framework for grids--Application to B&B algorithms. J. Parallel Distributed Comput. 72(2):120-131.

Digital Library

[4]

Berthold T (2013) Measuring the impact of primal heuristics. Oper. Res. Lett. 41(6):611-614.

Digital Library

[5]

Berthold T, Heinz S, Pfetsch ME (2009) Nonlinear pseudo-Boolean optimization: Relaxation or propagation? Kullmann O, ed. Theory and Applications of Satisfiability Testing--SAT 2009, Lecture Notes in Computer Science (Springer, Berlin), 441-446.

[6]

Berthold T, Heinz S, Vigerske S (2011) Extending a CIP framework to solve MIQCPs. Lee J, Leyffer S, eds. Mixed Integer Nonlinear Programming, The IMA Volumes in Mathematics and Its Applications, Vol. 154 (Springer, New York), 427-444.

[7]

Bixby RE, Cook W, Cox A, Lee EK (1999) Computational experience with parallel mixed integer programming in a distributed environment. Ann. Oper. Res. 90:19-43.

[8]

Bussieck MR, Drud AS, Meeraus A (2003) MINLPLib--A collection of test models for mixed-integer nonlinear programming. INFORMS J. Comput. 15(1):114-119.

Digital Library

[9]

Bussieck MR, Ferris MC, Meeraus A (2009) Grid-enabled optimization with GAMS. INFORMS J. Comput. 21(3):349-362.

Digital Library

[10]

Chen Q, Ferris MC (2000) FATCOP: A fault tolerant Condor-PVM mixed integer programming solver. SIAM J. Optim. 11(4): 1019-1036.

Digital Library

[11]

Chen Q, Ferris MC, Linderoth J (2001) FATCOP 2.0: Advanced features in an opportunistic mixed integer programming solver. Ann. Oper. Res. 103(1-4):17-32.

[12]

Dolan ED, Moré JJ (2002) Benchmarking optimization software with performance profiles. Math. Programming 91(2):201-213.

[13]

Eckstein J (1994) Parallel branch-and-bound algorithms for general mixed integer programming on the CM-5. SIAM J. Optim. 4(4):794-814.

[14]

Eckstein J, Hart WE, Phillips CA (2001) PICO: An object-oriented framework for parallel branch-and-bound. Butnariu D, Censor Y, Reich S, eds. Inherently Parallel Algorithms in Feasibility and Optimization and Their Applications, Elsevier Scientific Series on Studies in Computational Mathematics (Elsevier, Atlanta), 219-265.

[15]

Eckstein J, Phillips CA, Hart WE (2009) PEBBL 1.0 user guide. RUTCOR Research Report RRR 19-2006, Rutgers Center for Operations Research, Rutgers University.

[16]

Gamrath G, Koch T, Maher S, Rehfeldt D, Shinano Y (2014) SCIP-Jack-- A solver for STP and variants with parallelization extensions. 11th DIMACS Implementation Challenge Workshop in Collaboration with ICERM: Steiner Tree Problems.

[17]

Goux J-P, Kulkarni S, Yoder M, Linderoth J (2001) Master-worker: An enabling framework for applications on the computational grid. Cluster Comput. 4(1):63-70.

Digital Library

[18]

Koch T, Ralphs T, Shinano Y (2012) Could we use a million cores to solve an integer program? Math. Methods Oper. Res. 76(1):67-93.

[19]

Koch T, Achterberg T, Andersen E, Bastert O, Berthold T, Bixby RE, Danna E, et al. (2011) MIPLIB 2010--Mixed integer programming library version 5. Math. Programming Comput. 3(2):103-163.

[20]

Linderoth J (1998) Topics in parallel integer optimization. Unpublished doctoral thesis, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA.

[21]

Liu T, Curtsinger C, Berger ED (2011) Dthreads: Efficient deterministic multithreading. Proc. Twenty-Third ACM Sympos. Operating Systems Principles, SOSP '11 (ACM, New York), 327-336.

[22]

Lozi J-P, Lepers B, Funston J, Gaud F, Quéma V, Fedorova A (2016) The Linux scheduler: A decade of wasted cores. Proc. Eleventh Eur. Conf. Comput. Systems, EuroSys '16 (ACM, New York), 1-16.

[23]

Martins R, Manquinho V, Lynce I (2012) An overview of parallel SAT solving. Constraints 17(3):304-347.

Digital Library

[24]

Mitra G, Hai I, Hajian MT (1997) A distributed processing algorithm for solving integer programs using a cluster of workstations. Parallel Comput. 23(6):733-753.

Digital Library

[25]

Mittelmann H (2011) Mixed integer linear programming benchmark (serial codes).Accessed June 12, 2017, http://plato.asu.edu/ftp/milpf.html.

[26]

Montesinos P, Hicks M, King ST, Torrellas J (2009) Capo: A software-hardware interface for practical deterministic multiprocessor replay. ACM SIGPLAN Notices 44(3):73-84.

Digital Library

[27]

Nwana V, Darby-Dowman K, Mitra G (2004) A two-stage parallel branch and bound algorithm for mixed integer programs. IMA J. Management Math. 15(3):227-242.

[28]

Olszewski M, Ansel J, Amarasinghe S (2009) Kendo: Efficient deterministic multithreading in software. ACM SIGPLAN Notices 44(3):97-108.

Digital Library

[29]

Ralphs T, Shinano Y, Berthold T, Koch T (2017) Parallel solvers for mixed integer linear programing. ZIB-Report 16-74, Zuse Institute, Berlin.

[30]

Ralphs TK (2006) Parallel branch and cut. Talbi E, ed. Parallel Combinatorial Optimization (Wiley, New York), 53-101.

[31]

Ralphs TK, Güzelsoy M, Mahajan A (2011) SYMPHONY 5.4 user's manual. Technical report, COR@L Laboratory, Lehigh University, Bethlehem, PA.

[32]

Ralphs TK, Ladányi L, Saltzman MJ (2003) Parallel branch, cut, and price for large-scale discrete optimization. Math. Programming Ser. B 98(1-3):253-280.

Digital Library

[33]

Ralphs TK, Ladányi L, Saltzman MJ (2004) A library hierarchy for implementing scalable parallel search algorithms. J. Supercomput. 28(2):215-234.

[34]

Shinano Y, Fujie T (2007) Paralex: A parallel extension for the CPLEX mixed integer optimizer. Cappello F, Herault T, Dongarra J, eds. Recent Advances in Parallel Virtual Machine and Message Passing Interface, Lecture Notes in Computer Science, Vol. 4757 (Springer, Berlin), 97-106.

[35]

Shinano Y, Achterberg T, Fujie T (2008) A dynamic load balancing mechanism for new ParaLEX. Hobbs M, Xiang Y, Zhou W, eds. Proc. 14th Internat. Conf. Parallel Distributed Systems, ICPADS '08 (IEEE Computer Society, Washington, DC), 455-462.

[36]

Shinano Y, Achterberg T, Berthold T, Heinz S, Koch T (2012) ParaSCIP: A parallel extension of SCIP. Bischof C, Hegering HG, Nagel WE, Wittum G, eds. Proc. Internat. Conf. Competence in High Performance Computing 2010 (Springer, Berlin), 135-148.

[37]

Shinano Y, Achterberg T, Berthold T, Heinz S, Koch T, Winkler M (2015) Solving open MIP instances with ParaSCIP on supercomputers using up to 80,000 cores. ZIB-Report 15-53, Zuse Institute Berlin.

[38]

Shinano Y, Fujie T, Kounoike Y (2003) Effectiveness of parallelizing the ILOG-CPLEX mixed integer optimizer in the PUBB2 framework. Kosch H, Bszrmnyi L, Hellwagner H, eds. Euro-Par 2003 Parallel Processing, Lecture Notes in Computer Science, Vol. 2790 (Springer, Berlin), 451-460.

[39]

Shinano Y, Heinz S, Vigerske S, Winkler M (2013) FiberSCIP-- A shared memory parallelization of SCIP. ZIB-Report 13-55, Zuse Institute, Berlin.

[40]

Sun Y, Zheng G, Jetley P, Kalé LV (2011) ParSSSE: An adaptive parallel state space search engine. Parallel Processing Lett. 21(3): 319-338.

[41]

van Nieuwpoort RV, Wrzesinska G, Jacobs CJH, Bal HE (2010) Satin: A high-level and efficient grid programming model. ACM Trans. Programming Languages Systems 32(3):1-39.

Digital Library

[42]

Vigerske S (2013) Decomposition of multistage stochastic programs and a constraint integer programming approach to mixed-integer nonlinear programming. PhD thesis, Humboldt-Universität zu Berlin.

[43]

Vigerske S, Gleixner A (2016) SCIP: Global optimization of mixedinteger nonlinear programs in a branch-and-cut framework. ZIB Report 16-24, Zuse Institute Berlin.

[44]

Xu Y, Ralphs TK, Ladányi L, Saltzman MJ (2009) Computational experience with a software framework for parallel integer programming. INFORMS J. Comput. 21(3):383-397.

Digital Library

Cited By

Lin PZou MChen ZCai SLarson K(2024)ParaILPProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence10.24963/ijcai.2024/768(6949-6957)Online publication date: 3-Aug-2024
https://dl.acm.org/doi/10.24963/ijcai.2024/768
Munguía LOxberry GRajan DShinano Y(2019)Parallel PIPS-SBBComputational Optimization and Applications10.1007/s10589-019-00074-073:2(575-601)Online publication date: 17-May-2019
https://dl.acm.org/doi/10.1007/s10589-019-00074-0

FiberSCIP-A Shared Memory Parallelization of SCIP
1. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
      1. Mixed discrete-continuous optimization
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
      1. Mixed discrete-continuous optimization

Recommendations

Integrating SQP and Branch-and-Bound for Mixed Integer Nonlinear Programming

This paper considers the solution of Mixed Integer Nonlinear Programming (MINLP) problems. Classical methods for the solution of MINLP problems decompose the problem by separating the nonlinear part from the integer part. This approach is largely due to ...
Enabling Research through the SCIP Optimization Suite 8.0
The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. The focus of this article is on the role of the SCIP Optimization Suite in supporting ...
FATCOP: A Fault Tolerant Condor-PVM Mixed Integer Programming Solver

We describe FATCOP, a new parallel mixed integer program solver written in PVM. The implementation uses the Condor resource management system to provide a virtual machine composed of otherwise idle computers. The solver differs from previous parallel ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image INFORMS Journal on Computing

INFORMS Journal on Computing Volume 30, Issue 1

February 2018

201 pages

ISSN:1526-5528

Issue’s Table of Contents

Publisher

INFORMS

Linthicum, MD, United States

Publication History

Published: 01 February 2018

Accepted: 06 March 2017

Received: 27 September 2013

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Lin PZou MChen ZCai SLarson K(2024)ParaILPProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence10.24963/ijcai.2024/768(6949-6957)Online publication date: 3-Aug-2024
https://dl.acm.org/doi/10.24963/ijcai.2024/768
Munguía LOxberry GRajan DShinano Y(2019)Parallel PIPS-SBBComputational Optimization and Applications10.1007/s10589-019-00074-073:2(575-601)Online publication date: 17-May-2019
https://dl.acm.org/doi/10.1007/s10589-019-00074-0

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents