Types of constraints and variables

BCP has three types of constraints (or cuts):

• Core constraints come from the initial LP formulation and are present in the LP at every node of the tree.

• Algorithmic constraints are cuts given implicitly by a separation algorithm. Algorithmic constraints, unlike core constraints, might be added or removed from the node LP. The user controls which cuts are added, but cut removal is done by BCP based on a value called ``row effectiveness'' (number of consecutive iterations for which the corresponding slack variable is zero, for example). Limited user input (through the parameter file discussed in Section 8) is used for the definition of row effectiveness.

• Indexed constraints are constraints in bijection with a set of integers, such that (user defined) functions to generate the constraint from the corresponding integer and vice-versa are available. Indexed constraints can be seen as a special type of algorithmic cuts, having an extremely compact representation. They might be removed from the node LP similarly to the algorithmic cuts.

A typical use of indexed constraints is in the situation where some of the constraints of the initial formulation are more important than others and the initial formulation has a large number of constraints: Important constraints will become core constraints and the remaining ones will be indexed constraints, stored in an (indexed) array of constraints,

When developing a new application, the first decision to make is how to partition the constraints into the three classes.

Example: For the example described in Section 2, the core constraints are chosen as:

$$\begin{array}{llrrrrrrrrrrr} & x_0 + x_1 & = & 1 \ [0.2cm] ... ... + x_{i+1} &\le &1, &{\rm for } i = 1, \ldots, 9. \end{array}$$

The indexed constraints are chosen as:

$$\begin{array}{llrrrrrrrrrrr} & x_1 + x_3 + x_9 &\le &1\ [0.... ... + x_7 &\le &1\ [0.2cm] & x_0 + x_6 + x_8 &\le &1. \end{array}$$

Finally, the algorithmic constraints are chosen as:

$$\begin{array}{llrrrrrrrrrrr} & x_i + x_{i+1} + x_{i+2} &\le &1, &{\rm for } i = 0, \ldots, 9. \end{array}$$

$\Box$

Instead of storing the sense (``$\ge$'', ``$\le$'', or ``$=$'') and right hand side of an inequality, BCP stores a lower bound and an upper bound for each inequality (``ranged'' constraints). Setting one of the bounds to $\pm \infty$, or setting both bounds to the same value allows for the three possible senses.

BCP does not have have (yet) the possibility of using global cuts: all cuts passed to BCP are handled as local cuts, valid only in the subtree rooted at the node where the constraint is generated. The user may of course implement pools for holding global cuts, but he will then be responsible for the management of those cuts. While this might be done relatively easily for a non-parallel implementation, this becomes trickier when parallelism is involved.

In the example, coefficients of core and indexed constraints are stored in CoinPackedMatrices in the class BB_prob. To store algorithmic cuts, the class BB_cut is used (file include/BB_cut.hpp and Member/BB_cut.cpp). It implements in a standard way a representation of a cut as its set of nonzero coefficients.

The variables in BCP may also be of one of the three types: core, algorithmic, or indexed. Since we focus here on a Branch-and-Cut, all variables are core variables. Each variable has an upper and a lower bound, possibly $\pm \infty$. In addition, each variable is labeled as integer, binary or continuous. Variables are internally numbered with integers, starting at 0. When BCP reports information related to variables, it is with respect to its internal numbering.