The cutting plane procedure was invented in 1954 by Dantzig~et.~al.~{dan:ful:joh} for the traveling salesman problem. The branch-and-cut-paradigm was first formulated for and successfully applied to the linear ordering problem by Gr"otschel~et.~al. in 1984~{gr:jue:rei}. The first state-of-the-art BCP algorithm was developed in 1991 by Padberg and Rinaldi~{pad:rin}. Since then, the method was applied to a huge number of problems. The LP-solver was treated as an independent black-box almost from the beginning. The software system ABACUS~{jue:thi} is an object oriented software framework for BCP-algorithms. It provides the problem independent part, e.g., the enumeration tree, the interface with the LP-solver and various standard strategies, e.g. for branching or exploiting LP properties. It has concepts like subproblem, cut-generation, and pricing. It has no modeling language and does not provide a library of separation and pricing routines.
Another direction are general ILP-solvers using the BC-paradigm. These solvers are mostly extensions of existing linear programming solvers, e.g. CPLEX {cplex} or XPRESS~{xpress}. They solve arbitrary ILPs using general cuts, e.g., Gomory cuts. Modeling languages, such as AMPL~{AMPL} or GAMS~{gams}, can be used to specify the ILP. However, modeling is on the level of ILPs, all constraints must be given explicitly, and the support of problem specific cuts and variable generation is rudimentary. Modeling systems for general ILP solvers translate a high-level problem description into a matrix. During this process most of the structural knowledge contained in the model gets lost. The solver only sees a matrix.
Symbolic constraints are one of the main achievements of {constraint programming} (CP). They were first introduced under the name {global constraints} in the CP-system CHIP~{BC94,CHIP} and later used in further CP-systems like ILOG OPL Studio~{ILOG} and OZ~{OZ}. On the one hand, symbolic constraints allow for high-level and intuitive problem formulations. On the other hand, they improve efficiency by integrating problem-specific algorithms into a general solver.
Bockmayr and Kasper~{Bockmayr-Kasper,kasper:thesis} suggested to extend ILP by symbolic constraints. SCIL realizes this suggestion. An optimization problem is specified by a set of variables (ranging over the rational numbers) a linear objective function and a set of constraints. A constraint may be a {linear constraint} (a linear inequality or equation) or a {symbolic constraint}. In principle, a symbolic constraint can be every subset of the set of all assignments of values to variables. Note, however, that not all subsets of assignments are realizable in our framework. The system of linear constraints can be solved efficiently by an LP-solver whereas the symbolic constraints typically make the problem hard.
Symbolic constraints in integer programming allow the modeler to include large families of linear constraints, variables, and branching rules into the model, without writing them down explicitly. An important symbolic constraint is the integrality constraint. It is the only symbolic constraint which is available in all BCP-systems. In its simplest form the integrality constraint for a variable $x$ includes only the branching rules $x c x c+1$ for all integers $c$ into the system. Another example, is the TOUR constraint mentioned earlier in the paper. It includes the degree and the subtour elimination constraints into the model. Declaratively, this constraint is equivalent to exponentially many linear inequalities. Operationally, however, only some of these inequalities will be added to the model at runtime (as cutting planes). Concerning efficiency, symbolic constraints allow one to integrate specialized cutting plane algorithms based on polyhedral combinatorics into a general branch-and-cut solver. Symbolic constraints give the modeler the possibility to identify some specific structure in the problem, which later can be exploited when the model is solved. For example, when we solve a model containing the symbolic constraint ${tour}$, we can enhance our general branch-and-cut solver by computing specialized cutting planes for the traveling salesman problem instead of using general cutting planes for arbitrary linear 0-1 programs.
All available systems for ILP have in common that the variables are only an indexed set. But as mentioned above we often have a correspondence between combinatorial objects and variables and constraints. This turns out to be a key to elegant modeling. SCIL takes this into account by introducing variable maps and constraint maps. See section a first program} for details.
1.6.3