Edit on GitHub

Set bridges

ConstraintProgrammingExtensions.Bridges.AbsoluteValue2MILPBridge — Type

Bridges CP.AbsoluteValue to linear constraints and integer constraints.

The implemented model is the most generic one, so that the absolute value always has a well-defined value. This requires the use of a binary variable. In many cases, this is not necessary, and simpler models could be used, but checking this automatically would require access to the whole model.

Based on Mosek's modelling cookbook.

YALMIP implements a similar formulation, with big-M and small-m values computed based on the bounds for each variable.

source
ConstraintProgrammingExtensions.Bridges.DifferentFrom2PseudoMILPBridge — Type

Bridges CP.DifferentFrom to linear constraints (including, possibly, strict inequalities). This constraint adds one variable to store the absolute value of the difference, and constrains it to be nonzero.

For AbstractFloat arguments (like Float64): equivalent to abs(x) > 0.0, i.e. a Strictly(GreaterThan(0.0)).

source
ConstraintProgrammingExtensions.Bridges.Sort2MILPBridge — Type

Bridges CP.Sort to MILP constraints by adding O(n²) binary variables, with a transportation-like model.

Detailed model

Let x be the array to sort and y its sorted copy, both vectors having length n. This bridge handles the constraint [y..., x...]-in-CP.Sort(n).

Two sets of variables:

  • f[i, j]: real variable, i from 1 to n; the "flow" from the array to sort to the sorted copy, equal to the value of x[i] and y[j]
  • a[i, j]: binary variable, i from 1 to n; a[i, j] indicates whether the flow f[i, j] is nonzero

Constraints:

  • Flow coming from the array to sort x: $x_i = \sum_{j=1}^n f_{i,j} \qquad \forall i \in \{1, 2\dots n\}$
  • Flow going to the sorted array: $y_j = \sum_{i=1}^n f_{i,j} \qquad \forall j \in \{1, 2\dots n\}$
  • The flow from one value of the array to sort can only go to one element of the sorted array: $\sum_{i=1}^n a_{i,j} = 1 \qquad \forall j \in \{1, 2\dots n\}$
  • The flow to one value of the sorted array can only come from one element of the array to sort: $\sum_{j=1}^n a_{i,j} = 1 \qquad \forall i \in \{1, 2\dots n\}$
  • The flow f[i, j] is related to the binary variable a[i, j]: $U a_{i,j} \leq f_{i,j} \leq L a_{i,j} \qquad \forall (i,j) \in \{1, 2\dots n\}^2$
  • The array y must be sorted: $y_{j-1} \leq y_{j} \qquad \forall j \in \{2, 3\dots n\}$
source