×

The ABACUS system for branch-and-cut-and-price algorithms in integer programming and combinatorial optimization. (English) Zbl 1147.90416

Summary: The development of new mathematical theory and its application in software systems for the solution of hard optimization problems have a long tradition in mathematical programming. In this tradition we implemented ABACUS, an object-oriented software framework for branch-and-cut-and-price algorithms for the solution of mixed integer and combinatorial optimization problems. The paper discusses some difficulties in the implementation of branch-and-cut-and-price algorithms for combinatorial optimization problems and shows how they are managed by ABACUS.

MSC:

90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C27 Combinatorial optimization
90C10 Integer programming
68N19 Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Linear Programming and Extensions. Princeton University Press: Princeton, 1963. · Zbl 0108.33103 · doi:10.1515/9781400884179
[2] Mathematical programming: Journal, society, recollections. History of Mathematical Programming, (eds.). CWI North-Holland, 1991; 5-18.
[3] Charnes, Econometrica 20 (1952)
[4] Gomory, Bulletin of the American Mathematical Society 64 pp 275– (1958) · Zbl 0085.35807 · doi:10.1090/S0002-9904-1958-10224-4
[5] Balas, OR Letters 19 pp 1– (1996)
[6] Land, Econometrica 28 pp 493– (1960) · Zbl 0101.37004 · doi:10.2307/1910129
[7] Kruskal, Proceedings of the American Mathematical Society 7 pp 48– (1956) · Zbl 0070.18404 · doi:10.1090/S0002-9939-1956-0078686-7
[8] Dijkstra, Numerische Mathematik 1 pp 269– (1959) · Zbl 0092.16002 · doi:10.1007/BF01386390
[9] Edmonds, Canadian Journal of Mathematics 17 pp 449– (1965) · Zbl 0132.20903 · doi:10.4153/CJM-1965-045-4
[10] Dantzig, Operations Research 2 pp 393– (1954) · Zbl 0204.18701
[11] Grötschel, Operations Research 32 pp 1195– (1984) · Zbl 0554.90077 · doi:10.1287/opre.32.6.1195
[12] Karp, SIAM Journal on Computing 11 pp 620– (1982) · Zbl 0505.65020 · doi:10.1137/0211053
[13] Low-dimensional 0/1-polytopes and branch-and-cut in combinatorial optimization. PhD Thesis, Universität Heidelberg, 1997.
[14] Padberg, SIAM Review 33 pp 60– (1991) · Zbl 0734.90060 · doi:10.1137/1033004
[15] The traveling salesman problem. Network Models (Handbook on Operations Research and Management Sciences, vol. 7), (eds.). North-Holland: Amsterdam, 1995; 225-330. · Zbl 0832.90118 · doi:10.1016/S0927-0507(05)80121-5
[16] Practical problem solving with cutting plane algorithms in combinatorial optimization. Combinatorial Optimization (DIMACS Series in Discrete Mathematics and Theoretical Computer Science), (eds.). American Mathematical Society, 1995; 111-152. · Zbl 0835.90076 · doi:10.1090/dimacs/020/02
[17] Branch-and-cut algorithms. Annotated Bibliographies in Combinatorial Optimization, (eds.). Wiley, 1997; 45-64.
[18] Gilmore, Operations Research 9 pp 849– (1961) · Zbl 0096.35501 · doi:10.1287/opre.9.6.849
[19] IBM Corporation. IBM Mathematical Programming System Extended/370 (MPSX/370), Mixed Integer Programming/370 (MIP/370), 1979.
[20] Minos 5.4 user’s guide. Technical Report, Stanford University, Department of Operations Research, 1995.
[21] LINDO SYSTEMS Inc., LINDO user’s manual, 1997.
[22] Marsten, ACM Transations of Mathematical Software 7 pp 481– (1981) · doi:10.1145/355972.355976
[23] IBM Corporation, Optimization Subroutine Library - Guide and Reference, Release 2.1, 1995.
[24] Cplex. Using the Cplex Callable Library. Cplex Optimization, Inc, 1997.
[25] Dash Associates. XPRESS-MP, Optimisation Subroutine Library, 1995.
[26] Suhl, European Journal of Operational Research 72 pp 312– (1994) · Zbl 0800.90690 · doi:10.1016/0377-2217(94)90312-3
[27] Functional description of MINTO, a Mixed INTeger Optimizer, version 2.3. Technical Report, Georgia Institute of Technology, School of Industrial and Systems Engineering, 1996.
[28] Software Engineering. Addison-Wesley: Reading, MA, 1992. · Zbl 0782.68001
[29] Object-Oriented Analysis and Design with Applications. The Benjamin Cummings Publishing Company: Redwood City, CA, 1994.
[30] The C++ Programming Language (2nd edn). Addison-Wesley: Reading, MA, 1993.
[31] ABACUS?A Branch-And-CUt system. PhD Thesis, Institut für Informatik, Universität zu Köln, 1995.
[32] The design of the branch-and-cut system ABACUS. Technical Report, Institut für Informatik, Universität zu Köln, 1997.
[33] Jünger, Operations Research Letters 22 pp 83– (1998) · Zbl 0911.90282 · doi:10.1016/S0167-6377(98)00013-3
[34] A simple TSP-solver. Technical Report, Institut für Informatik, Universität zu Köln, http://www.informatik.uni-koeln.de/ls_juenger/projects/abacus/abacus_tutorial.ps.gz, 1996.
[35] ABACUS 2.0: User’s Guide and Reference Manual. Institut für Informatik, Universität zu Köln, 1997. http://www.informatik.uni-koeln.de/ls_juenger/projects/abacus/manual.ps.gz.
[36] Reusable Software, The Base Object-Oriented Component Libraries. Prentice-Hall: Hertfordshire, 1994.
[37] Johnson, Journal of Object-Oriented Programming 1 pp 22– (1988)
[38] ABACUS 1.2: User’s guide and reference manual. Technical Report, Institut für Informatik, Universität zu Köln, 1996.
[39] A simple TSP-solver. Technical Report, Institut für Informatik, Universität zu Köln, http://www.informatik.uni-koeln.de/ls_juenger/projects/abacus/abacus_tutorial.ps.gz, 1996.
[40] INFORMATION PROCESSING SYSTEM Accredited Standards Committee, X3. The ISO/ANSI C++ Draft, 1995. http://www.cygnus.com/misc/wp/.
[41] The LEDA User Manual Version R 3.4.1. Max-Planck-Institut für Informatik, Saarbrücken, 1996.
[42] Data Abstraction and Object-Oriented Programming in C++. John Wiley, 1990.
[43] The standard template library. Technical Report, Rensselaer Polytechnic Institute, 1995. http://www.cs.rpi.edu/?musser/stl.html.
[44] On the SQAP polytope. Technical Report, Institut für Informatik, Universität zu Köln, 1996. To appear in SIAM Journal of Optimization.
[45] Vance, Computational Optimization and Applications 3 pp 111– (1994) · Zbl 0801.90080 · doi:10.1007/BF01300970
[46] Balas, Mathematical Programming 58 pp 295– (1993) · Zbl 0796.90041 · doi:10.1007/BF01581273
[47] Polyhedral combinatorics (Handbook of Combinatorics, vol. 2), (eds.). Elsevier, 1995; 1649-1704. · Zbl 0845.90103
[48] Chvátal, Mathematical Programming 5 pp 29– (1973) · Zbl 0267.05118 · doi:10.1007/BF01580109
[49] Padberg, Mathematics of Operations Research 7 pp 67– (1982) · Zbl 0499.90056 · doi:10.1287/moor.7.1.67
[50] Jünger, Zeitschrift für Operations Research 40 pp 183– (1994)
[51] Reinelt, ORSA Journal on Computing 3 pp 376– (1991) · Zbl 0775.90293 · doi:10.1287/ijoc.3.4.376
[52] Efficient separation routines for the symmetric traveling salesman problem I: general tools and comb separation. Technical Report, Institut für Informatik, Universität zu Köln, 1999, to appear.
[53] Efficient separation routines for the symmetric traveling salesman problem II: separating multi handle inequalities. Technical Report, Institut für Informatik, Universität zu Köln, 1999, to appear.
[54] Solving mixed 0-1 programs by a lift-and-project method. Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 1993; 232-242. · Zbl 0808.90100
[55] Hoffman, Management Science 39 pp 657– (1993) · Zbl 0783.90051 · doi:10.1287/mnsc.39.6.657
[56] SoPlex, The Sequential object-oriented simplex class library, 1997. http://www.zib.de/Optimization/Software/Soplex/.
[57] Savelsbergh, ORSA Journal on Computing 6 pp 445– (1994) · Zbl 0814.90093 · doi:10.1287/ijoc.6.4.445
[58] Using path inequalities in a branch-and-cut code for the symmetric traveling salesman problem. Proceedings on the Third IPCO Conference, (eds.). 1993; 291-311. · Zbl 0924.90125
[59] An integer programming approach to scheduling. Computer Scheduling of Public Transport Urban Passenger Vehicle and Crew Scheduling, (ed.). North-Holland: Amsterdam, 1981; 269-280.
[60] lp_solve 2.0, 1995. ftp://ftp.es.ele.tue.nl/pub/lp_solve.
[61] Broad selection of software packages available OR/MS Today 1994; 42-51.
[62] Nemhauser, Operations Research Letters 15 pp 47– (1994) · Zbl 0806.90095 · doi:10.1016/0167-6377(94)90013-2
[63] Branching algorithms for crew scheduling problems. Master’s Thesis, Chalmers University, 1997.
[64] The constrained crossing minimization problem?a first approach. Operations Research Proceedings 1998. Springer, 1999; 125-134. · doi:10.1007/978-3-642-58409-1_11
[65] Success and failure of certain reconstruction and uniqueness algorithms in discrete tomography. Technical Report, Technische Universität München, 1997.
[66] A polyhedral approach to the feedback vertex set. Integer Programming and Combinatorial Optimization (Proceedings of the 5th International IPCO Conference, Vancouver, Canada, June 1996) (Lecture Notes in Computer Science, vol. 1084), (eds.). Springer Verlag, 1996; 445-459. · doi:10.1007/3-540-61310-2_33
[67] Ein Branch-and-Price Algorithmus für das ganzzahlige Verschnittproblem. Master’s Thesis, Institut für Informatik, Universität zu Köln, 1998.
[68] Christof, TOP (Spanish Statistical and Operations Research Society) 4 pp 1– (1996)
[69] Relaxations of the max cut problem and computation of spin glass ground states. Operations Research Proceedings, et al. (eds.). Springer: Heidelberg, 1997; 74-83.
[70] A polyhedral approach to the multi-layer crossing minimization problem. Proceedings of Graph Drawing ’97 (Lecture Notes in Computer Science, vol. 1353), (ed.). Springer: Heidelberg, 1997; 13-24. · doi:10.1007/3-540-63938-1_46
[71] A branch-and-cut algorithm for multiple sequence alignment. First Annual International Conference on Computational Molecular Biology. ACM, 1997.
[72] Christof, Journal Computational Biology 4 pp 433– (1997) · doi:10.1089/cmb.1997.4.433
[73] Das pickup-and-delivery problem?betrachtet als modifiziertes traveling-salesman-problem. Master’s Thesis, Institut für Informatik, Universität zu Köln, 1998.
[74] Das Planare Augmentierungsproblem. Master’s Thesis, Universität des Saarlandes, Saar-brücken, 1997.
[75] Design of survivable networks with bounded rings. PhD Thesis, Service de Mathématiques de la Gestion, Université Libre de Bruxelles, 1998.
[76] Polyhedral combinatorics of QAPs with less objects than locations. Proceedings of the Sixth Conference on Integer Programming and Combinatorial Optimization. Springer, 1998; 409-422. · Zbl 0910.90238 · doi:10.1007/3-540-69346-7_31
[77] A polyhedral approach to RNA sequence structure alignment. Proceedings of the Second Annual International Conference on Computational Molecular Biology RECOMB, 1998.
[78] On an integer multicommodity flow problem from the airplane industry. Technical Report UU-CS-1997-38, Department of Computer Science, Utrecht University, Utrecht, 1997.
[79] An alternative method for crossing minimization on hierarchical graphs. Proceedings of the Graph Drawing ’96 (Lecture Notes in Computer Science, vol. 1190), (ed.). Springer Verlag, 1997; 318-333. · doi:10.1007/3-540-62495-3_57
[80] Two layer planarization in graph drawing. Proceedings of the ISAAC ’98 (Lecture Notes in Computer Science, vol. 1533), (eds.). Springer Verlag, 1998; 69-78. · Zbl 0948.68136
[81] Optimal compaction of orthogonal grid drawings Proceedings of the Seventh Conference on Integer Programming and Combinatorial Optimization IPCO’99, 1999.
[82] Verification of safety properties using integer programming: Beyond the state equation. Technical Report, Technische Universität München, 1997.
[83] Consecutive ones and a betweenness problem in computational biology. Proceedings of the 6th Conference on Integer Programming and Combinatorial Optimization (IPCO98), 1998. · Zbl 0910.90219
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.