Rose classifies the constraints in your problem into 17 distinct types. The table is sorted from the most specific to the most general constraint types. Even empty, free, and singleton constraints are listed, although these are removed during trivial pre-solving.
Identifying constraint types helps ensure your model is correctly formulated. If a constraint is classified unexpectedly, it may indicate an error in its logic, a misinterpretation of business rules, or numerical inconsistencies. Reviewing these classifications allows you to verify the structure of your model and provides a clearer way to explain its constraints to others.
When determining constraint types, binary variables may be negated to ensure positive coefficients where required. For example, a binary variable \(x\) may be rewritten as \(1−\bar{x}\) to match specific classification rules. In particular, this is performed for classes that require positive coefficients for a match. For instance, the constraint \(x_1+x_2−x_3−x_4=0\) will be transformed to \(x_1+x_2+\bar{x}_3+\bar{x}_4=2\) and classified as a cardinality constraint for the purposes of constraint classification.
The table below defines the constraint classifications.
Classification |
Linear Constraint Definition |
| Empty | Has no variables |
| Free | With no finite side |
| Singleton | With a single variable |
| Aggregation | Of the type \(ax + by = c\) |
| Precedence | Of the type \(ax−ay ≤ b\) where \(x\) and \(y\) must have the same type |
| Variable bound | Of the form \(ax + by \le c, x \in {0,1}\) |
| Set partitioning | Of the form \( \sum x_i = 1, x_i \in \{0,1\} \forall i \) |
| Set packing | Of the form \( \sum x_i \le 1, x_i \in \{0,1\} \forall i \) |
| Set covering | Of the form \( \sum x_i \ge 1, x_i \in \{0,1\} \forall i \) |
| Cardinality | Of the form \( \sum x_i = k, x_i \in \{0,1\} \forall i, k \le 2 \) |
| Invariant knapsack | Of the form \( \sum x_i \le b, x_i \in \{0,1\} \forall i, b \in N \ge 2 \) |
| Equation knapsack | Of the form \( \sum a_i x_i = b, x_ \in \{0,1\} \forall i, b \in N \ge 2 \) |
| Binpacking | Of the form \( \sum a_i x_i + ax \le a, x, x_i \in \{0,1\} \forall i, a \in N \ge 2 \) |
| Knapsack | Of the form \( \sum a_k x_k \le b, x_i \in \{0,1\} \forall i, b \in N \ge 2 \) |
| Integer knapsack | Of the form \( \sum a_k x_k \le b, x_i \in Z \forall i, b \in N \) |
| Mixed binary | Of the form \( \sum a_k x_k + \sum p_j s_j \{≤,=\}b, x_i \in \{0,1\} \forall i, s_j \) cont. \( \forall j \) |
| General linear | With no special structure |
Note, these constraint classification definitions come from a research paper by Gleixner et al.
Comments
0 comments
Please sign in to leave a comment.