The design of the branch-and-cut system ABACUS：（ABACUS branch-and-cut的设计系统）.pdfVIP

The Design of the BranchandCut System ABACUS Michael Junger and Stefan Thienel January Abstract The software system ABACUS is an ob jectoriented framework for the implementation of branchandcut and branchandprice algorithms This pap er describ es the design of ABACUS including the design principles and the most imp ortant classes Intro duction Branchandb ound cutting planes and column generation are classical to ols for the solution of mixed integer optimization problems and combinatorial optimization problems While the rst technique has b een used and rened continuously since its development in the early sixties the later techniques had to b e rediscovered for the practical solution of hard optimization problems during the last ten to fteen years although they have their origin also in the fties and sixties Studying the mathematical programming literature of the last decades one can observe that the numb er of theoretical pap ers ab out linear programming based branchandb ound eg ab out p olyhedral combinatorics or cutting plane generation clearly dominates the numb er of publications with a more computational avor There might b e several reasons The implementation of these algorithm was not regarded as a challenge for a long time The LPsolvers were not fast and numerically robust enough for the solution of the linear programming relaxations of hard mixed integer optimization problems The computer hardware was often not adequate for the ecient implementation of such pro grams Esp ecially the lack of main memory was an obstacle for the ecient implementation of such algorithms The implementation of a linear pro