最近在做linear programming时总结的一些tricks

以前沒幹過類似的，下麵說的東西都是自己山寨出來的。
如果哪位仁兄知道更好的解決方法，麻煩指導下， bow//

1. absolute value
如果是| ... | <= 非常好办,直接展开就是了.
但如果是| ... | >= 就麻烦点, 转化为了 一个 or 的不等式组.
比如| x - 5 | >= y  变为  x - 5 >= y or x-5 <= -y.
于是问题变为如何线性化 or

2. not equal
A =/= B 这个展开后,变为 A<B or A>B
还是按照or的方法来做

3. "or" / disjunctive
这个比较tricky, 还要结合整个系统.
举一个例子表明思路, 假设原来的条件是
X  >= Y +5 or X - 5 <= -Y ( see absolute value )

我们先整理成这样:
1) X - Y >= 5
2) -Y - X >= - 5

使用一个binary控制变量C,以及一个足够大的常数M, 来写成这样的constriants:
1') X + MC >= 5
2') -Y - X + M(1-C) >= - 5

可以看到,当C=1时, 由于M足够大, 因此 1') 自动满足了.  而2') 变为了 -Y - X >= -5 ,正是or 右边的条件.
而C=0, 1') 变为 X >= 5, 2') 自动满足.

同理可以使用n个控制变量达到 2^n 个contraint or起来的情况.
比如 A or B or C or D.
然后用2个control variable:
M(c1+c2)
M(c1+1-c2)
M(1-c1+c2)
M(2-c1-c2)
这样就可以使得它们中有且仅有一个为0,其余均为M或2M,因此该constraint能被自动满足.

4. "if" condition(special order set.)
lp_solve里面支持一种叫SOS的东西,具体参见manual
简单来说, 就是定义一堆变量a1,a2,...,an
使得sum ai = 1
也就是说仅有一个为1 (lp_solve里面的SOS能做得更强大)
这样可以模拟一些分段函数以及if的条件
比如
y=5, 当0<=x<=10
y=7, 当10<x<=20
则可以定义a0~a20
使得y=5*a0+5*a1+...+7*a11+...+7*a20
看起来有点傻,不过是我能想到的唯一的表达手段...