这种约束的名称是什么?

计算科学 优化 线性规划 混合整数规划 术语
2021-12-23 03:50:04

我有一个简单的混合整数线性规划问题,除了一些约束的形式f(x1,x2,x3,,xn)<c, 在哪里f是'取最大坐标的最大值和所有较小坐标的和'

在口齿不清:

(defn f [& l]
  (let [sl (reverse (sort l))]
    (max (first sl) (reduce + (rest sl)))))

(f 1 2 3 4 5) -> 10

在三个维度中,例如,我想我可以将其改写为f<10作为

(defn constraint [x,y,z]
  (or
   (and (<= x 10)
        (<= (+ y z) 10))
   (and (<= y 10)
        (<= (+ x z) 10))
   (and (<= z 10)
        (<= (+ x y) 10))))

这显然是联合3(或者n) 凸物体(棱镜)。

这种类型的约束有名称吗?是否有解决此类问题的技术和软件包?

1个回答

我将约束称为“最大元素的上限和下限”。请注意,您实际上是在处理两个单独的约束。定义最大元素函数如下

max:RnRmax(x)maxi{1,,n}xn.
您的第一个约束是“取最大元素并确保它小于 ”: 而第二个约束是“取和,减去最大元素,并确保结果小于 ": 其中是通常的列向量。上的凸上界,而 (2)是非凸下界。c
(1)max(x)<c,
c
(2)1Txmax(x)<c,
1=[1,,1]Tmax(x)

此类具有固定上限的问题通过 Big-M 方法有一个非常优雅的解决方案。是一个任意大数,对于 x的所有可能选择那么很容易验证 使用上述恒等式,我们可以将 (1) 和 (2)完全实现 为以下混合整数约束 我们方便地使用作为 Big-M 参数。Mmax(x)Mx

α=max(x)Mαxα(1z)M,1Tz=1,z{0,1}n.
f(x)<c1Txc<α<cα(1z)cxααR,z{0,1}n
c