Back to SYMPHONY Home Page
Just as with variables, the constraints are divided into base constraints and extra constraints. The base constraints are those that are included in every LP relaxation, whereas the extra constraints are generated dynamically and are free to enter and leave the relaxation. Typically, the base constraints are some subset of the constraints in the integer programming formulation of the problem. For example, in the Traveling Salesman Problem, the set of base constraints could simply consist of the degree constraints. Obviously, the set of base constraints must be known explicitly. Extra constraints, on the other hand, are generated dynamically by the cut generator as they are violated. As with variables, the constraints in the current relaxation are called the active constraints.
Since SYMPHONY has no knowledge of the structure of the cuts being generated, it is up to the user, if desired, to designate a packed form for each class of cut and to implement cut packing and unpacking subroutines. For instance, suppose that the set of nonzero variables in a particular class of cuts corresponds to the set of edges across a cut in a graph. Instead of storing the indices of each variable explicitly, it is more efficient to simply store the set of nodes on one side of the cut as a bit array. The cut can then be constructed easily for the particular set of active variables (edges) in the problem at the time.