[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

ParaSCIP: A Parallel Extension of SCIP

  • Conference paper
  • First Online:
Competence in High Performance Computing 2010

Abstract

Mixed integer programming (MIP)has become one of the most important techniques in Operations Research and Discrete Optimization. SCIP (Solving Constraint Integer Programs) is currently one of the fastest non-commercial MIP solvers. It is based on the branchandboundprocedure in which the problem is recursively split into smaller subproblems, thereby creating a so-called branching tree. We present ParaSCIP, an extension of SCIP, which realizes a parallelization on a distributed memory computing environment. ParaSCIP uses SCIP solvers as independently running processes to solve subproblems (nodes of the branching tree) locally. This makes the parallelization development independent of the SCIP development. Thus, ParaSCIP directly profits from any algorithmic progress in future versions of SCIP. Using a first implementation of ParaSCIP, we were able to solve two previously unsolved instances from MIPLIB2003, a standard test set library for MIP solvers. For these computations, we used up to 2048 cores of the HLRN II supercomputer.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 71.50
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 89.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
GBP 89.99
Price includes VAT (United Kingdom)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Gurobi Optimizer. http://www.gurobi.com/

  2. HLRN – Norddeutscher Verbund zur Förderung des Hoch- und Höchstleistungsrechnens. http://www.hlrn.de/

  3. IBM ILOG CPLEX Optimizer. http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/

  4. Mixed Integer Problem Library (MIPLIB) 2003. http://miplib.zib.de/

  5. SCIP: Solving Constraint Integer Programs. http://scip.zib.de/

  6. TOP500 Supercomputer Sites. http://www.top500.org/list/2010/11/100

  7. Achterberg, T.: Constraint integer programming. Ph.D. thesis, Technische Universität Berlin (2007)

    Google Scholar 

  8. Achterberg, T.: SCIP: Solving constraint integer programs. Mathematical Programming Computation 1(1), 1–41 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  9. Achterberg, T., Koch, T., Martin, A.: MIPLIB 2003. Operations Research Letters 34(4), 1–12 (2006)

    Article  MathSciNet  Google Scholar 

  10. Bixby, R., Rothberg, E.: Progress in computational mixed integer programming – A look back from the other side of the tipping point. Annals of Operations Research 149(1), 37–41 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  11. Bixby, R.E., Boyd, E.A., Indovina, R.R.: MIPLIB: A test set of mixed integer programming problems. SIAM News 25, 16 (1992)

    Google Scholar 

  12. Karp, R.M.: Reducibility among combinatorial problems. In: R.E. Miller, J.W. Thatcher (eds.) Complexity of Computer Computations, pp. 85–103. Plenum Press, New York, USA (1972)

    Google Scholar 

  13. Laundy, R., Perregaard, M., Tavares, G., Tipi, H., Vazacopoulos, A.: Solving hard mixed-integer programming problems with Xpress-MP: A miplib 2003 case study. INFORMS Journal on Computing 21(2), 304–313 (2009)

    Article  MathSciNet  Google Scholar 

  14. Mittelmann, H.: Mixed integer linear programming benchmark (serial codes). http://plato.asu.edu/ftp/milpf.html

  15. Padberg, M., Rinaldi, G.: A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Review 33, 60–100 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  16. Ralphs, T.K., Ladányi, L., Saltzman, M.J.: Parallel branch, cut and price for large-scale discrete optimization. Mathematical Programming Series B 98(1–3), 253–280 (2003)

    Article  MATH  Google Scholar 

  17. Shinano, Y., Achterberg, T., t: Fujie: A dynamic load balancing mechanism for new paralex. In: Proceedings of ICPADS 2008, pp. 455–462 (2008)

    Google Scholar 

  18. Xu, Y., Ralphs, T.K., Ladányi, L., Saltzmann, M.J.: Computational experience with a software framework for parallel integer programming. INFORMS Journal on Computing 21(3), 383–397 (2009)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

Supported by the DFG Research Center Matheon Mathematics for key technologies in Berlin. We are thankful to the HRLN II supercompter stuff, a specially Bernd Kallies and Hinnerk Stüben which gave us support at any time we needed it.

Author information

Authors and Affiliations

  1. Zuse Institute Berlin, Takustr. 7, 14195, Berlin, Germany

    Yuji Shinano, Timo Berthold, Stefan Heinz & Thorsten Koch

  2. IBM Deutschland GmbH, Ober-Eschbacher Str. 109, 61352, Bad Homburg v.d.H., Germany

    Tobias Achterberg

Authors
  1. Yuji Shinano
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tobias Achterberg
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Timo Berthold
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Stefan Heinz
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Thorsten Koch
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Timo Berthold .

Editor information

Editors and Affiliations

  1. Technical University Darmstadt, Mornewegstr. 30, Darmstadt, 64293, Germany

    Christian Bischof

  2. Leibniz Rechenzentrum (LRZ), Boltzmannstr. 1, Garching, 85748, Germany

    Heinz-Gerd Hegering

  3. Center for Information Services, and High Performance Computing (ZIH), Technical University Dresden, Helmholtzstr. 10, Dresden, 01062, Germany

    Wolfgang E. Nagel

  4. , Goethe Center for Scientific Computing (, Goethe University Frankfurt, Kettenhofweg 139, Frankfurt, 60325, Hessen, Germany

    Gabriel Wittum

Rights and permissions

Reprints and permissions

Copyright information

© 2011 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Shinano, Y., Achterberg, T., Berthold, T., Heinz, S., Koch, T. (2011). ParaSCIP: A Parallel Extension of SCIP. In: Bischof, C., Hegering, HG., Nagel, W., Wittum, G. (eds) Competence in High Performance Computing 2010. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-24025-6_12

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-24025-6_12

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-24024-9

  • Online ISBN: 978-3-642-24025-6

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation