关于在x₁,…,xₙ有界约束下用混合整数线性不等式实现y=min(x₁,…,xₙ)的问询

当然可以！我们只需要引入n个0-1整数变量（$z_1, z_2, \dots, z_n$）加上连续变量$y$，就能用一组线性约束精准刻画$y$是所有$x_i$最小值的逻辑，而且这套方案的变量和约束数量已经是尽可能少的最优配置。

需要的决策变量 #

• 原连续变量：$x_1, x_2, \dots, x_n$（满足原约束 $L_i \leq x_i \leq U_i$）
• 新增连续变量：$y$（用来表示$\min(x_1, \dots, x_n)$）
• 新增0-1整数变量：$z_1, z_2, \dots, z_n$（用来标记哪一个$x_i$取到了最小值）

混合整数线性约束系统 #

1. 保证$y$不大于任何一个$x_i$：
   $$y \leq x_i \quad \forall i = 1, 2, \dots, n$$
   这一步先把$y$限定为所有$x_i$的下界，确保$y$不会超过任何一个$x_i$的值。

2. 保证存在至少一个$x_i$等于$y$：
   $$y \geq x_i - U_i(1 - z_i) \quad \forall i = 1, 2, \dots, n$$
   $$\sum_{i=1}^n z_i = 1$$
   第二组约束的逻辑是：当$z_i=1$时（标记该$x_i$是最小值），约束简化为$y \geq x_i$，结合第一组的$y \leq x_i$，就直接得到$y = x_i$；当$z_i=0$时，约束变为$y \geq x_i - U_i$，而因为$x_i \leq U_i$，所以$x_i - U_i \leq 0$，$y$作为最小值本身就不小于所有$x_i$的下界$L_i$，因此这个约束会自动成立，不会对$y$造成额外限制。

   最后的求和约束确保恰好有一个$z_i$取1，也就是精准选中一个$x_i$作为最小值的对应项，结合前面的约束，就能保证$y$等于所有$x_i$中的最小值。

复杂度说明 #

• 额外决策变量数量：$n+1$（n个0-1变量+1个连续变量$y$）
• 额外约束数量：$2n+1$（n个下界约束 + n个选择约束 + 1个求和约束）

这套方案是刻画min函数的标准线性化方法，在变量和约束数量上已经是最优的——因为要确定n个变量中的最小值，至少需要n个0-1变量来标记选择，无法再减少变量数量，约束数量也已经是最紧凑的配置。

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