Constraints and variables have several common features, which we consider in a common base class.
A constraint/variable is active if it belongs to the constraint/variable set of an active subproblem. An active constraint/variable must not be removed from its pool. As in a parallel implementation of ABACUS there can be several active subproblems, each constraint/variable has a counter for the number of active subproblems, in which it is active.
Besides being active there can be other reasons why a constraint/variable
should not be deleted from its pool, e.g., if the constraint/variable
has just been generated, then it is put into a buffer,
but is not yet activated (we explain the details in
Section 
).
In such a case we want to set a
lock
on the constraint that it cannot
be removed. Again, in a parallel implementation, but also in a
sequential one, we may want to set locks at the same time on the same
constraint for different reasons. Hence, we count the number of locks
of each constraint/variable.
Constraints and variables can be locally or globally valid . Therefore, we provide a flag in the common base class of constraints and variables. The functions to determine if a local constraint or variable is valid for a certain subproblem are associated directly with the classes for constraints and variables, respectively.
It has been stated that the use of locally valid constraints and variables should be avoided as it requires a nasty bookkeeping [PR91]. In order to free the user from this, we have embedded the management of local constraints and variables in ABACUS. The validity of a constraint/variable is automatically checked if it is regenerated from the pool.
We also distinguish between dynamic variables/constraints and static ones. As soon as a static variable/constraint becomes active it cannot be deactivated. An example for static variables are the variables in a general mixed integer optimization problem, examples for static constraints are the constraints of the problem formulation of a general mixed integer optimization problem or the degree constraints of the traveling salesman problem. Dynamic constraints are usually cutting planes. In column generation algorithm variables can be dynamic, too.
A crucial point in the implementation of a special variable or constraint class is the tradeoff between performance and memory usage. We have observed that a memory efficient storage format can be one of the keys to the solutions of larger instances. Such formats are in general not very useful for the computation of the coefficient of a single variable/constraint. Moreover, if the coefficients of a constraint for several variables or the coefficients of a variable for several constraints have to be computed, e.g., when the row/column format of the constraint/variable is generated in order to add it to the LP-solver, then these operations can become a bottleneck. However, given a different format, using more memory, it might be possible to perform these operations more efficiently.
Therefore, we distinguish between the compressed format and the expanded format of a constraint/variable. Before a bigger number of time consuming coefficient computations is performed, we try to generate the expanded format, afterwards the constraint/variable is compressed.
Of course, both expanded and compressed formats are rather constraint/variable specific. But we provide the bookkeeping already in the common base class and try to expand the constraint/variable, e.g., when it is added to the linear program. Afterwards it is compressed again. The implementation of the expansion and compression is optional.
We use again the
subtour elimination constraint
of the traveling salesman problem as an example for the compressed
and expanded format. For an inequality 
we store
the nodes of the set W in the compressed format. The computation
of the coefficient of an edge (t,h) requires 
time
and space.
As expanded format we use an array
inSubtour of type bool of length n (n
is the number of nodes of the graph) and
inSubtour[v] is true if and only if
. Now, we can determine the coefficient of an edge (variable)
in constant time.