Constraint Type Definitions

Each constraint in a MIP instance is classified by its variable composition and its structure. A constraint can carry one tag from each category.

Describes the types of variables appearing in the constraint.

continuous

All variables are continuous.

pure binary

All variables are binary.

mixed binary

Contains both binary and continuous variables (no general integers).

mixed integer

Contains at least one general integer variable.

Describes the mathematical structure of the constraint. Where $x_i \in \{0,1\}$ denotes binary variables and $b$ is a constant.

set partitioning

All binary variables with coefficients of 1, equality with RHS = 1.

$$\sum_{i} x_i = 1$$

set packing

All binary variables with coefficients of 1, $\leq$ constraint with RHS = 1.

$$\sum_{i} x_i \leq 1$$

set covering

All binary variables with coefficients of 1, $\geq$ constraint with RHS = 1.

$$\sum_{i} x_i \geq 1$$

cardinality

All binary variables with unit coefficients $(\pm 1)$.

$$\sum_{i} \pm x_i \leq b$$

knapsack

All binary variables with non-unit coefficients, $\leq$ or $\geq$ constraint.

$$\sum_{i} a_i x_i \leq b$$

bin. knapsack eq.

All binary variables with non-unit coefficients, equality constraint.

$$\sum_{i} a_i x_i = b$$

integer knapsack

No continuous variables, at least one general integer, $\leq$ or $\geq$ constraint.

$$\sum_{i} a_i y_i \leq b, \quad y_i \in \mathbb{Z}$$

variable bound

Exactly 2 variables: one binary and one continuous or general integer.

$$a \cdot x + b \cdot y \leq c, \quad x \in \{0,1\}$$

bound

Single-variable constraint (effectively an explicit bound on one variable).

$$l \leq a \cdot x \leq u$$

equality

Any equality constraint not already classified as set partitioning or binary knapsack equality.

$$\sum_{i} a_i x_i = b$$

empty

Constraint with no variables (zero terms).