基于混合整数约束的数组排序通用约束构建及最少二进制变量方案

给定变量数组 $X = [X_1, X_2, ..., X_n]$，我们需要通过线性约束生成排序后的数组 $Y = [Y_1, Y_2, ..., Y_n]$，要求 $Y_1 \leq Y_2 \leq ... \leq Y_n$，且Y的元素是X元素的重排。

以n=2为例，$Y_1 = \min(X_1,X_2)$，$Y_2 = \max(X_1,X_2)$，可以用Big M方法配合1个二进制变量$B$实现，约束如下：

Y_1 <= X_1
Y_1 <= X_2
Y_1 + B * M >= X_1
Y_1 + (1 - B) * M >= X_2

Y_2 >= X_1
Y_2 >= X_2
Y_2 <= X_1 + (1 - B) * M
Y_2 <= X_2 + B * M

下面针对通用场景的约束构建和最少二进制变量的实现方法进行说明：

一、通用情况的约束构建 #

最常用的是排列矩阵+Big M的方案，步骤如下：

1. 定义二进制变量 $z_{i,j}$：当 $Y_i$ 等于 $X_j$ 时，$z_{i,j}=1$；否则为0。
2. 排列约束（确保每个X元素对应唯一Y元素，每个Y元素对应唯一X元素）：
   • 对每个X的索引 $j$：$\sum_{i=1}^n z_{i,j} = 1$（每个$X_j$必须被分配到某个$Y_i$）
   • 对每个Y的索引 $i$：$\sum_{j=1}^n z_{i,j} = 1$（每个$Y_i$必须对应某个$X_j$）
3. Y的单调性约束：
   • 对 $i=1$ 到 $n-1$：$Y_{i+1} \geq Y_i$
4. Y与X的关联约束（M取足够大的正数，需大于X元素的最大可能差值）：
   • 对所有 $i,j$：$Y_i \leq X_j + M(1 - z_{i,j})$（若$z_{i,j}=1$，则$Y_i \leq X_j$；否则约束自动生效）
   • 对所有 $i,j$：$Y_i \geq X_j - M(1 - z_{i,j})$（若$z_{i,j}=1$，则$Y_i \geq X_j$；结合上式可得$Y_i=X_j$）

这套约束组合起来，就能保证Y是X的升序排列结果。

二、最少二进制变量的实现 #

上面的方案用了 $n^2$ 个二进制变量，但理论上最少只需要 $\lceil \log_2(n!) \rceil$ 个——因为n个元素的排列总数是 $n!$，需要这么多二进制位才能编码所有可能的排列。

具体实现思路如下：

1. 计算 $k = \lceil \log_2(n!) \rceil$，定义k个二进制变量 $b_1, b_2, ..., b_k$（每个变量取0或1）。
2. 为每个升序排列$\sigma$（即满足$X_{\sigma(1)} \leq X_{\sigma(2)} \leq ... \leq X_{\sigma(n)}$的排列）分配一个唯一的k位二进制编码。
3. 定义指示变量 $c_\sigma$：当选择排列$\sigma$时，$c_\sigma=1$；否则为0。通过线性约束将$c_\sigma$与二进制变量的编码关联（比如用SOS-1约束，或者大M约束转化编码逻辑）。
4. 添加核心约束：
   • $\sum_\sigma c_\sigma = 1$（必须恰好选择一个有效升序排列）
   • 对每个 $i$：$Y_i = \sum_\sigma c_\sigma \cdot X_{\sigma(i)}$（$Y_i$等于选中排列对应的X元素）
   • 对每个排列$\sigma$：添加$X_{\sigma(1)} \leq X_{\sigma(2)} \leq ... \leq X_{\sigma(n)}$的约束（确保该排列是升序的）

不过要注意，这种方法的约束数量会随n快速增长，当n较大时（比如n>5），求解器处理起来反而不如排列矩阵方案高效——虽然排列矩阵用的变量多，但约束结构规整，求解器更容易优化。

另外还有一种折中方案：用$\binom{n}{2}$个二进制变量记录成对比较结果（$b_{i,j}=1$表示$X_i \leq X_j$，i<j），再通过这些变量关联Y的排序，但需要额外添加传递性约束（比如若$b_{i,j}=1$且$b_{j,k}=1$，则$b_{i,k}=1$），变量数比$n^2$少，但比理论下界多，适合对变量数有一定要求但不想处理复杂编码的场景。

内容的提问来源于stack exchange，提问作者ido kahana