3.5 New Features of ABACUS 2.0

This section summarizes all new features that have been introduced since the release of ABACUS 1.2.

3.5.1 LP-Solver Soplex

Besides Cplex ABACUS provides now an interface to the LP-Solver Soplex [Wun97].

If Soplex is used as LP-solver, it might be required to switch to the new include file structure (see Section 3.5.3) in order to avoid name conflicts. Both Soplex and ABACUS provide include files with the name timer.h.

3.5.2 Naming Conventions

The previous version did not use any prefix for all globally visible names in order to avoid name collisions with other libraries since the C++ concept of namespaces should make this technique redundant. Unfortunately, it turned out that the GNU C++ compiler does still not support namespaces. The G++-FAQ mentions that even in the next release 2.8 this concept might not be supported.

In order to provide the possibility of avoiding name collisions without namespaces, we added to all globally visible names the prefix ABA_. There are two possibilities for reusing your old codes together with the new name concept.

The first method is to include the file oldnames.h into every file using ABACUS names without the prefix ABA_. In the compilation the preprocessor flag ABACUS_OLD_NAMES must be set. With preprocessor definitions the old names are converted to new names. You should be aware that this technique can have dangerous side effects. Therefore, this procedure should not be applied if you combine ABACUS with any other library in your application.

The second method is the better method and is not much more work than the first one. In the tools subdirectory of the ABACUS distribution you can find the Perl script upd-names-2.0. If you apply this script to all source files of your ABACUS application by calling

a copy of each file given in <files> is made in the subdirectory new-files and the old names are replaced by the new names.

3.5.3 Include File Path

Another problem are header files of different libraries with the same name. It can happen that due to the inclusion structure it is not possible to avoid these conflicts by the order of the include file search paths. Therefore, every ABACUS include file (*.h and *.inc) is included now from the subdirectory abacus. You can continue using the old include file structure by setting the preprocessor flag ABACUS_OLD_INCLUDE. Here is an example how an ABACUS file includes other ABACUS files:

We strongly recommend the use of the new include file structure. In combination with the LP-solver Soplex the new include file structure is sometimes required (it depends which ABACUS and which Soplex files you include). There may be name conflicts since both systems have a file timer.h.

Due to this concept also the directory structure of the ABACUS distribution has changed. All include files are now in the subdirectory include/abacus.

A conversion can be performed with the help of the Perl script tools/upd-includes-2.0. Calling

makes a copy of all <files> into the subdirectory new-includes and adapts them to the new include structure, e.g.,

is replaced by

in the new files.

3.5.4 Advanced Control of the Tailing Off Effect

ABACUS automatically controls the tailing off effect according to the parameters TailOffNLps and TailOffPercent of the configuration file .abacus. Solutions of LP-relaxations can be skipped in this control by calling the function ignoreInTailingOff() (see Section 5.2.25).

3.5.5 Problem Specific Fathoming

Problem specific fathoming criteria can be added by the redefinition of the virtual function ABA_SUB::exceptionFathom() (see Section 5.2.23).

3.5.6 Problem Specific Branching

A problem specific branching step can be enforced by the redefinition of the virtual function ABA_SUB::exceptionBranch() (see Section 5.2.24).

3.5.7 Generalized Strong Branching

Generalized strong branching is the possibility of evaluating different branching rules and selecting the best ones. If branching on variables is performed, e.g., the first linear programs of the (potential) sons for various branching variables are solved, in order to find the most promising variable. Together with the built-in branching strategies this feature can be controlled with the new entry NBranchingVariableCandidates of the configuration file (Section 5.2.26). Moreover, also other branching strategies can be evaluated as explained in Section 5.2.8.

3.5.8 Pool without Constraint Duplication

One problem in using ABACUS can be the large number of generated constraints and variables that use a lot of memory. In order to reduce the memory usage we provide a new pool class ABA_NONDUPLPOOL that avoids the multiple storage of the same constraint or variable in the same pool. The details are explained in Section 5.2.2.

3.5.9 Visual C++ Compiler

In addition to the GNU C++ compiler on UNIX operating systems, ABACUS is now also available on Windows NT in combination with the Visual C++ compiler. Further details for using ABACUS in this new environment can be found in Section 2

3.5.10 Compiler Preprocessor Flag

In the compilation of an ABACUS-application the used compiler must be specified by a preprocessor flag (see Section 2.1).

3.5.11 LP-Solver Preprocessor Flag

The LP-solvers that are used have to be specified by a preprocessor flag (see Section 2.3). Also the flags for the LP-solver Cplex changed.

3.5.12 Parameters of Configuration File

Three new parameters have been added to the configuration file .abacus.

3.5.12.1 NBranchingVariableCandidates

The parameter NBranchingVariableCandidates can be used to control the number of tested branching variables if our extended strong branching concept is used (see Section 5.2.8).

3.5.12.2 DefaultLpSolver

An other new parameter is DefaultLpSolver allows to choose either Cplex or Soplex as default LP-solver for the solution of the LP-relaxations.

3.5.12.3 SoPlexRepresentation

Soplex works internally either with column or a row basis. This basis representation can be selected with the parameter SoPlexRepresentation. Our tests show that only the row basis works stable in Soplex 1.0. Further details are explained in Section 5.2.26.

3.5.13 New Functions

We implemented several new functions. Some of them might be also interesting for the users of ABACUS. For the detailed documentation we refer to the reference manual.

• ABA_BPRIOQUEUE::getMinKey()
• ABA_BHEAP::getMinKey()
• bool ABA_GLOBAL::isInteger(double x)
• In addition to the function

  void MASTER::initializePools(ABA_BUFFER<ABA_CONSTRAINT*> &constraints,                                      ABA_BUFFER<ABA_VARIABLE*> &Variables,                                      int varPoolSize,                                      int cutPoolSize,                                      bool dynamicCutPool = false);

  the function

  void MASTER::initializePools(ABA_BUFFER<ABA_CONSTRAINT*> &constraints,                                       ABA_BUFFER<ABA_CONSTRAINT*> &cuts,                                       ABA_BUFFER<ABA_VARIABLE*> &Variables,                                       int varPoolSize,                                       int cutPoolSize,                                       bool dynamicCutPool = false);

  also allows the insertion of some initial cuts into the cut pool.

• Manipulators for setting the width and the precision of ABA_OSTREAM have been added that work like the corresponding manipulators of the class ostream.

  ABA_OSTREAM_MANIP_INT setWidth(int w);         ABA_OSTREAM_MANIP_INT setPrecision(int p);

• ABA_OSTREAM::setFormatFlag(fmtflags)
• The objective function sense can be changed in the ABA_LP classes with the function

  void ABA_LP::sense(const ABA_OPTSENSE &newSense).

• The != operator is now available for the class ABA_STRING.

3.5.14 Miscellaneous

Besides some bug fixes we made many minor improvements. The most important ones are listed here.

• The output for the output levels SubProblem and LinearProgram is formatted in a nicer way.
• Besides those Cplex parameters that could be directly controlled by ABACUS functions, it is now possible to get or to modify any Cplex 4.0 and 5.0 parameter with the functions:

  int CPLEXIF::CPXgetdblparam(int whichParam, double *value);         int CPLEXIF::CPXsetdblparam(int whichParam, double value);         int CPLEXIF::CPXgetintparam(int whichParam, int *value);         int CPLEXIF::CPXsetintparam(int whichParam, int value);

• If a linear program is solved with the barrier method, then usually a cross over to an optimal basic solution is performed. The value of a variable in the optimal solution of the barrier method before the cross over can be obtained with the function double barXVal(int i). If this “pre-cross over” solution is available, can be checked with the function SOLSTAT barXValStatus() const.
• The minimal required violation of a constraint or variable in a pool separation or pool pricing, respectively, can be specified as a parameter of the functions ABA_SUB::constraintPoolSeparation and ABA_SUB::variablePoolSeparation. The minimal violation is also a parameter of the function ABA_POOL::separate and of redefinitions of this function in derived classes.