The inheritance graph of any set of classes in C++ must be a directed acyclic graph. Very often these inheritance graphs form forests or trees. Also the inheritance graph of ABACUS is designed as a tree with a single exception where we use multiple inheritance.
The following sections and Table 4.1 give a survey of the different classes of ABACUS. The details are outlined in Section 4.2.
|
| ||||||||||||||||||||||||||||||
Basically the classes of ABACUS can be divided in three different main groups. The application base classes are the most important ones for the user. From these classes the user of the framework has to derive the classes for his applications. The pure kernel classes are usually invisible for the user. To this group belong, e.g., classes for supporting the branch-and-bound algorithm, for the solution of linear programs, and for the management of constraints and variables. Finally, there are the auxiliaries, i.e., classes providing basic data structures and tools, which can optionally be used for the implementation of an application.
The following classes are usually involved in the derivation process for the implementation of a new application.
The class ABA_MASTER is one of the central classes of the framework. It controls the optimization process and stores global data structures for the optimization. For each new application a class has to be derived from the class ABA_MASTER.
The class ABA_SUB represents a subproblem of the implicit enumeration, i.e., a node of the branch-and-bound tree. The subproblem optimization is performed by the solution of linear programming relaxations. Usually, most running time is spent within the member functions of this class. Also from the class ABA_SUB a new class has to be derived for each new application. By redefining virtual functions in the derived class problem specific algorithms as, e.g., cutting plane or column generation, can be embedded.
ABACUS provides some default concepts for the representation of constraints and variables. However, it still might be necessary that for a new application special classes have to be derived from the classes ABA_CONSTRAINT and ABA_VARIABLE, which then implement application specific methods and storage formats.
This group covers classes that are required for the implementation of the kernel of ABACUS but usually of no direct importance for the user of the framework.
All classes of ABACUS have the common base class ABA_ABACUSROOT.
The part of the inheritance graph related to the solution of linear programs contains several classes. There is a general interface to the linear program from which a class for the solution of linear programming relaxations within our branch-and-bound algorithm is derived. Both classes are independent from the used LP-solver, which can be plugged in via a separate class. Currently, we support the LP-solvers supported by the Open Solver Interface (Osi). In theory all these solvers can be used to solve the LP relaxations. We have tested ABACUS with CPLEX, Clp and Glpk.
Constraints and variables are stored in pools. We provide an abstract base class for the representation of pools and derive from this class a standard realization of a pool. Several other classes are required for a safe management of active and inactive constraints and variables.
Various classes are required to support the linear-programming based branch-and-bound algorithm, e.g., for the management of the branch-and-bound tree, for the storage of the active and inactive constraints, special buffers for newly generated constraints and variables, for the control of the tailing off effect, and for fixing variables by reduced costs. An important part of the inheritance graph in this context is formed by the various branching rules, which allow a very flexible implementation of branching strategies.
We use the following classes for the implementation of other classes within ABACUS, but they might also be useful for the implementation of new applications.
ABACUS is complemented by a set of basic data structures. Most of them are implemented as generic classes (templates).
Finally, we also provide some useful tools, e.g., for generating output, measuring time, and sorting.