{算法}整数线性规划(ILP)中非线性问题的线性化

[adream]

例如，X1、X2 取值均为0或1的整数，那么对于 X1*X2这类非线性元素可以按如下方式线性化：

令变量Y=X1*X2,同时增加两个约束方程：

1）X1 + X2 - Y <= 1

2) X1 + X2 - 2*Y >=0

因为，如果X1=0，那么上述两个方程就变成

X2 - Y <= 1

X2 - 2*Y >=0

又因为 X2的取值只能是 0 或 1 ，那么当 X1=0时，Y的取值只能是0

当X1=1是，上述两约束方程变为

Y >= X2

2*Y <= 1 + X2

又因为 X2 只能取 0 或 1 ，那么只能等于X2

所以对于 X1、X2只能取 0 或 1 这种情况，X1*X2 可以按照这样的方式线性化：

令Y=X1*X2, 同时增加两个约束方程：

1）X1 + X2 - Y <= 1

2) X1 + X2 - 2*Y >=0

现在我想把问题更一般化：

如果  0 <= X1 <= A1; 0 <= X2 <= A2; A1、A2均为正整数

那么 X1*X2 这一非线性元素是否与上面类似的线性化方法呢？

谢谢

[adream]

如果我们把新的问题也转化成0-1问题呢？

就是引入一组新变量x11,x12,....x21,x22...,这些变量只能取 0 或 1

令 X1=x11+x12+x13+x14+...

X2=x21+x22+x23+x24+...

那么 X1*X2 就可以表示成  x1i*x2j  之和的形式， 其中 x1i,x2j 只能 0 或 1

那样就可以用原先的方法处理了

但是这样显然看上去不够优雅

[Wu Yin]

你这种转化的意义很小，已经不是优雅不优雅的问题了。

大多数时候提到转化，都是有前提的，就是问题的规模不能比原问题的规模大得太多。这里的规模指的就是变量个数和约束个数。

你这个转化里赤裸裸的把变量的个数转化成了 相对原问题是指数级别 的规模，没有意义。

知道什么叫多项式规约不？

2011/2/18 adream <adre...@gmail.com>

--
滚滚长江东逝水，浪花淘尽英雄。
是非成败转头空。
青山依旧在，几度夕阳红。
白发渔樵江渚上，惯看秋月春风。
一壶浊酒喜相逢。
古今多少事，都付笑谈中。
----------

Xiamen University Cognitive Science Department, Brain-like Intelligent System Labs

Blog (all about mathematics & algorithms): http://wywcgs.wordpress.com.cn
Email: wyw...@gmail.com
Gtalk: wyw...@gmail.com
MSN: wyw...@hotmail.com

QQ: 346693733

TopCoder Handle: wywcgs

[adream]

我也就得这种转化没多大意义，仅仅只是一种思路而已：把大问题简化成小问题。

如果有X1，X2取值在0到2或3之类的表达式，那么我们是不是没必要把这个大问题转化到 1 这一级别，而是转化到2或3这一级别，那么变量是不是相对可以减少很多呢？

而且我做个简单的实验，采用上述方式转化之后的程序执行时间远不如下面的方法来的更快了：

分别计算 X1=0,1,2,3....A1，最后得到最优解

程序执行时间的差距在于一个的单位是分，另一个的的单位是秒

谢谢

[Wu Yin]

转化成2或3和转化成1没有本质的区别，都是O(A)数量级的变量

指数级规模的规约之所以没有太大意义，就是在于指数规约本质上还是在进行全枚举，就是你后面所说的枚举 X1=0,1,2,3....A1

一般的求解算法，计算复杂度函数相对变量个数的次数都不低，变量多A个的运算时间 肯定比连算A次要高的

2011/2/19 adream <adre...@gmail.com>