Types of constraints and variables (2024)

BCP has three types of constraints (or cuts):

• Core constraints come from the initial LP formulation and arepresent 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, butcut removal is done by BCP based on a value called ``row effectiveness''(number of consecutive iterations for which the corresponding slack variableis zero, for example). Limited user input (through the parameter file discussedin 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 integerand 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 thenode LP similarly to the algorithmic cuts.

A typical use of indexed constraints is in the situation wheresome of the constraints of the initial formulationare more important than others and the initial formulation has a largenumber of constraints: Important constraints will become core constraints andthe remaining ones will be indexed constraints, stored in an (indexed) array of constraints,

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

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

The indexed constraints are chosen as:

Finally, the algorithmic constraints are chosen as:

Instead of storing the sense (``'', ``'', or ``'') and righthand side of an inequality, BCP stores a lower bound and an upper boundfor each inequality (``ranged'' constraints). Setting one of the boundsto , or setting both bounds to the same valueallows 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 courseimplement pools for holding global cuts, but he will then be responsible forthe management of those cuts. While this might be done relatively easilyfor a non-parallel implementation, this becomes trickier when parallelism is involved.

In the example, coefficients of core and indexed constraints are stored in CoinPackedMatricesin the class BB_prob. To store algorithmic cuts, the class BB_cutis used (file include/BB_cut.hpp and Member/BB_cut.cpp). It implementsin 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 .In addition, each variable is labeled as integer, binary or continuous.Variables are internally numbered with integers, starting at 0. WhenBCP reports information related to variables, it is with respect to its internal numbering.