×

zbMATH — the first resource for mathematics

Introduction to ABACUS – a branch-and-cut system. (English) Zbl 0911.90282
Summary: The software system ABACUS is an object-oriented framework for the implementation of branch-and-cut and branch-and-price algorithms. This paper shows the basics of its application to combinatorial and mixed integer optimization problems.

MSC:
90C27 Combinatorial optimization
90C11 Mixed integer programming
Software:
MINTO; OSL; ABACUS; CPLEX; SoPlex
PDF BibTeX Cite
Full Text: DOI
References:
[1] C. Barnhart, E.L. Johnson, G.L. Nemhauser, M.W.P. Savelsbergh, P.H. Vance, Branch-and-price: column generation for huge integer programs, Oper. Res. (1998), to appear. · Zbl 0979.90092
[2] T. Christof, Low-dimensional0/1-polytopes and branch-and-cut in combinatorial optimization, Ph.D. Thesis, Universität Heidelberg, 1997. · Zbl 0911.90280
[3] T. Christof, M. Jünger, J. Kececioglu, P. Mutzel, G. Reinelt, A branch-and-cut approach to physical mapping with end-probes, in First Annual International Conference Molecular Biology, ACM, New York, 1997.
[4] CPLEX Optimization, Inc. (1995) Using the CPLEX^{TM} Callable Library.
[5] J. Esparza, S. Melzer, Verification of safety properties using integer programming: beyond the state equation, Technical Report, Technische Universität München, 1997.
[6] M. Funke, G. Reinelt, A polyhedral approach to the feedback vertex set, in: W.H. Cunningham, S.T. McCormick, M. Queyranne (Eds.), Integer Programming and Combinatorial Optimization (5th International IPCO Conference, Vancouver, Canada, June 1996, Proceedings), vol. 1084 of Lecture Notes in Computer Science, Springer, Berlin, 1996, pp. 445-459. · Zbl 1415.90063
[7] P. Gritzmann, D. Prangenberg, S. de Vries, M. Wiegelmann, Sucess and failure of certain reconstruction and uniqueness algorithms in discrete tomography, Technical Report, Technische Universität München, 1997.
[8] IBM Corporation, Optimization Subroutine Library - Guide and Reference, Release 2.1, 1995.
[9] M. Jünger, E.K. Lee, P. Mutzel, T. Odenthal, A polyhedal approach to the multi-layer crossing minimization problem, in: F. Di. Battista (ed.) Proc. Graph Drawing 1997, Lecture Notes in Computer Science 1353, Springer, Heidelberg, 1997, pp. 13-24.
[10] M. Jünger, G. Reinelt, S. Thienel, Practical problem solving with cutting plane algorithms in combinatorial optimization, in: W. Cook, L. Lovász, P. Seymour (Eds.), Combinatorial Optimization, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, Providence, RI, 1995, pp. 111-152. · Zbl 0835.90076
[11] M. Jünger, S. Thienel, The design of the branch-and-cut system ABACUS, Technical Report, Universität zu Köln, 1997.
[12] V. Kaibel, Polyhedral combinatorics of QAPs with less objects than locations (extended abstract), Technical Report 97.297, Universität zu Köln, 1997.
[13] Nemhauser, G.L.; Savelsbergh, M.W.P.; Sigismondi, G.C., MINTO, a mixed integer optimizer, Oper. res. lett., 15, 47-58, (1994) · Zbl 0806.90095
[14] K. Reinert, H.P. Lenhof, P. Mutzel, K. Mehlhorn, J.D. Kececioglou, A branch-and-cut algorithm for multiple sequence alignment, First Annual International Conference on Computational Molecular Biology, ACM, New York, 1997.
[15] S. Thienel, ABACUS - A Branch-And-CUt Sytem, Ph.D. Thesis, Universität zu Köln, 1995.
[16] S. Thienel, A simple TSP-solver, Technical Report, Universität zu Köln, 1996. http://www.informatik.uni-koeln.de/1s_juenger/ projects/abacus/abacus_tutorial.ps.gz.
[17] S. Thienel, ABACUS 2.0: User’s Guide and Reference Manual, Universität zu Köln, 1996. http://www.informatik.uni-koeln.de/ 1s_juenger/projects/abacus/manual.ps.gz.
[18] R. Wunderling, SoPlex, The Sequential object-oriented simplex class library, 1997. http://www.zib.de/Optimization/Software/ Sopolex/.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.