Constraints

Because the global list of potential constraints (also called cuts) is not usually known a priori or is extremely large, constraints cannot generally be represented simply by a user-assigned index. Instead, each constraint is assigned a global index only after it becomes active in some subproblem. It is up to the user, if desired, to designate a compact representation for each class of constraints that is to be generated and to implement subroutines for converting from this compact representation to a matrix row, given the list of active variables. For instance, suppose that the set of nonzero variables in a particular class of constraints corresponds to the set of edges across a cut in a graph. Instead of storing the indices of each variable explicitly, one could simply store the set of nodes on one side (``shore'') of the cut as a bit array. The constraint could then be constructed easily for any particular set of active variables (edges).

Just as with variables, the constraints are divided into core constraints and extra constraints. The core constraints are those that are active in every subproblem, whereas the extra constraints can be generated dynamically and are free to enter and leave as appropriate. Obviously, the set of core constraints must be known and constructed explicitly by the user. Extra constraints, on the other hand, are generated dynamically by the cut generator as they are violated. As with variables, a good set of core constraints can have a significant effect on efficiency.

Note that the user is not required to designate a compact representation scheme. Constraints can simply be represented explicitly as matrix rows with respect to the global set of variables. However, designating a compact form can result in large reductions in memory use if the number of variables in the problem is large.