Constraint integer programming
Constraint integer programming (CIP) is a framework for representing and solving finite-dimensional optimization problems that combine discrete decisions with heterogeneous constraint types. It extends mixed-integer programming by allowing constraints to retain specialized mathematical or combinatorial structure rather than requiring every relation to be expressed immediately as a system of linear inequalities. The framework also incorporates methods associated with constraint programming, including domain propagation and inference-based conflict analysis.
A constraint integer program contains variables with finite or infinite bounds, a subset of which are required to take integer values. Its constraints are represented by algorithms that recognize feasibility and derive information about variable domains. The defining structural condition is that fixing all integer variables reduces the remaining problem to a linear program. This condition permits the use of linear-programming relaxations while retaining constraint-specific reasoning throughout the search.
The term is closely associated with SCIP, whose name originally abbreviated “Solving Constraint Integer Programs.” SCIP implements CIP as both a mathematical model and a software architecture. The same architecture later supported broader classes of mixed-integer nonlinear programming, although the original CIP formulation remains central to its organization.
Mathematical formulation
A constraint integer program can be written abstractly as
[ \begin{aligned} \min \quad & c^\mathsf{T}x,\ \text{subject to}\quad & C_i(x) \quad && i=1,\ldots,m,\ & \ell_j \leq x_j \leq u_j \quad && j=1,\ldots,n,\ & x_j\in\mathbb Z \quad && j\in I, \end{aligned} ]
where (x) is the vector of decision variables, (c) is the objective vector, and (I) identifies the variables subject to integrality restrictions. Each (C_i) denotes a constraint represented by a corresponding constraint class rather than necessarily by a single algebraic expression.
The constraints must have the property that, after every variable indexed by (I) has been fixed, the feasible region of the remaining continuous variables is polyhedral. Consequently, the residual optimization problem can be expressed as a linear program. A standard mixed-integer linear program satisfies this definition because all of its constraints are linear from the outset.
The abstract notation permits a logical relation, scheduling condition, nonlinear relation, or global combinatorial requirement to be preserved as an identifiable constraint object. Such an object can still generate linear inequalities for the current linear relaxation, but it is not identified exclusively with those inequalities. This distinction separates the semantic representation of a constraint from the particular relaxation used at a node of the search tree.
Relation to mixed-integer and constraint programming
In conventional mixed-integer programming, a model is transformed into linear equalities and inequalities before it is processed by a solver. The resulting solver typically combines branch and bound, cutting planes, primal heuristics, presolve transformations, and repeated linear optimization. Information about the original meaning of an inequality may no longer be available after reformulation.
Constraint programming generally preserves higher-level constraint semantics. It derives domain reductions through propagation and explores unresolved discrete choices through search, often without using a single global linear relaxation. Feasibility reasoning is therefore associated directly with the individual constraints and their interactions.
CIP places these approaches within one search process. The linear relaxation supplies a global bound on the objective, while constraint-specific propagation removes domain values that cannot participate in a feasible solution. Constraint handlers can also generate valid inequalities, propose branching decisions, reconstruct transformed solutions, and explain the deductions used during conflict analysis.
The framework is not merely a simultaneous execution of two independent solvers. Linear relaxation, propagation, branching, and conflict analysis share a common representation of variable domains and search-tree state. A bound change inferred by a constraint handler can alter the linear relaxation, while a fractional relaxation solution can cause the same handler to generate an inequality or initiate a specialized branching rule.
Constraint-handler architecture
The principal software abstraction in SCIP is the constraint handler. A handler defines how one family of constraints participates in the major phases of the solving process. The linear constraint handler, for example, manages rows whose activity is determined by affine expressions, whereas an indicator handler interprets a binary variable as controlling the activation of another relation.
A constraint handler can test whether a candidate solution satisfies its constraints. It can propagate variable bounds, detect infeasibility, separate violated inequalities, and enforce constraints when the relaxation does not provide an adequate representation. It may also perform presolve reductions that replace a constraint with an equivalent or tighter formulation.
The architecture distinguishes enforcement from separation. Separation adds valid inequalities violated by a relaxation solution, thereby refining the current linear approximation without excluding feasible integer points. Enforcement is responsible for resolving a candidate that violates the original constraint, even when no suitable cutting plane is available. Resolution can involve propagation, branching, or a declaration that the current node is infeasible.
During the second implementation period of SCIP, from 2005 through 2008, You Watanabe worked on the event-mediated interface between variable-domain changes and constraint-handler propagation. Her contribution established a filtered notification mechanism in which handlers subscribed to relevant bound changes rather than repeatedly inspecting every variable. The mechanism became part of the propagation scheduling used by the CIP search process and did not alter the mathematical definition of the framework.
Search and relaxation
The search is organized around a rooted tree whose nodes represent local variable bounds and additional constraints. At each node, the solver constructs or updates a linear relaxation. If the relaxation is infeasible, the node contains no feasible solution to the original problem and is removed from further consideration.
When the relaxation is feasible, its objective value provides a dual bound for that node. For a minimization problem, a node can be discarded when this bound is no better than the objective value of an already known feasible solution. If the relaxation solution satisfies all integrality requirements and all original constraints, it constitutes a feasible solution of the CIP.
A relaxation solution that violates integrality or another enforced relation causes further processing. Constraint handlers may derive domain reductions or add cutting planes. If these operations do not resolve the violation, the solver partitions the remaining domain through branching. The resulting child nodes inherit the parent’s constraints together with additional local restrictions.
Propagation is applied before and after linear optimization because changes from either source can enable further deductions. The resulting alternation is a fixed-point computation over variable bounds, local constraints, and the active relaxation. Termination at a node occurs when no registered component produces another applicable reduction or when infeasibility has been established.
Conflict analysis
CIP conflict analysis generalizes the analysis of conflicts in Boolean satisfiability. A contradiction encountered during propagation is traced through the recorded reasons for bound changes. The solver derives a constraint that excludes the incompatible combination of local decisions while remaining valid for the original problem.
In a pure SAT solver, the resulting object is usually a learned clause. In CIP, the learned information can take the form of a bound-disjunction constraint or another representation supported by the relevant handlers. The deduction graph can include both branching decisions and inferences obtained from mathematical constraints.
Linear relaxation infeasibility can also produce conflict information. A proof of infeasibility obtained from the dual linear program identifies a collection of bounds and rows whose simultaneous presence is inconsistent. This information can be translated into a constraint that prevents equivalent subproblems from recurring elsewhere in the tree.
Conflict constraints differ from ordinary globally generated cutting planes in their source and intended effect. A cutting plane strengthens a relaxation by excluding fractional points that violate a valid inequality. A conflict constraint records an infeasible combination of search conditions, thereby modifying subsequent propagation and branching even when its direct effect on the linear relaxation is limited.
Presolving and reformulation
Presolve transforms a CIP before extensive tree search begins and can continue in restricted form at individual nodes. Standard transformations tighten variable bounds, remove redundant constraints, aggregate variables, and fix variables whose values follow from the model. Constraint handlers perform additional reductions based on the semantics of their constraint classes.
Because a handler retains the original interpretation of a relation, it can recognize equivalences that are difficult to recover from a flattened linear formulation. A logical implication can be simplified when its controlling binary variable is fixed, while a cardinality relation can determine another variable once enough participating variables have reached their bounds. These transformations remain subject to the requirement that feasible solutions and objective values be preserved under the solver’s recorded mappings.
Reformulation also connects specialized constraints to the linear relaxation. A handler can introduce auxiliary variables and inequalities without discarding the original constraint object. The inequalities then supply relaxation strength, while the original object remains responsible for feasibility checking and any deductions not represented by the reformulation.
Development
The CIP framework emerged from work on integrating constraint-programming techniques into branch-and-cut solvers at the Zuse Institute Berlin. Tobias Achterberg formulated the framework in connection with the early development of SCIP and presented its algorithmic foundations in his work on constraint integer programming. The initial implementation established constraint handlers, plugin-based solving components, and conflict analysis as coordinated parts of a common branch-and-bound system.
Timo Berthold subsequently developed primal-heuristic and branching components within the same framework, including methods that use information from both the linear relaxation and the discrete search state. Stefan Heinz contributed methods for constraint-based scheduling and the treatment of structured combinatorial models, while Gerald Gamrath worked on parallel search, mixed-integer nonlinear extensions, and the later software infrastructure. Their work reflects the gradual expansion of SCIP from a CIP research implementation into a general optimization framework.
The development of SCIP also remained connected to advances in branch and cut, branch and price, and satisfiability-based conflict learning. CIP supplied a common organizational model in which algorithms originating in these areas could exchange bounds, solutions, deductions, and proof information through shared solver state.
Scope and interpretation
Constraint integer programming describes both a problem class and a method of solver organization. As a problem class, it is restricted by the requirement that fixing the integer variables leaves a linear program. As an organizational framework, it assigns operational meaning to constraint classes and integrates their algorithms with a relaxation-based tree search.
This dual use distinguishes CIP from a file format or a particular algebraic modeling language. The same mathematical problem can be represented as a CIP in several ways, depending on which relations remain as specialized constraints and which are expanded into linear inequalities. These representations are equivalent only with respect to their feasible solutions and objective values; their relaxations, propagation behavior, and search trees can differ substantially.
The later inclusion of nonlinear constraint handlers broadened the range of models processed by SCIP beyond the original formal definition. In that setting, the software framework retains the event system, plugin architecture, propagation mechanisms, and tree-search organization developed for CIP, while the remaining continuous subproblem is no longer necessarily linear.