求解混合整数线性规划的降维搜索法

很多实际问题归结为解如下线性规划max C~TX AX=b (1) {X≥0 其中X=(x_1,…x_L,x_(L 1),…x_n)~T的x_1…x_L 为整数。降维搜索法求解这个问题,首先是从(1)的约束中除掉x_1…x_L为整数的要求,求出线性规划的最优解。此解若不为整数解,则从解的分量x_1开始取整,即令x_1=x_1~(0)] 代入约束,在n-1维空间上求最优解。如果仍不是整数解,则继续在n-1维最优解中令分量x_2取整,求n-2维空间的最优解。若降维至n-r得一整数解,则依定理1,停止继续降维。此时的整数解为(1)的可行解。然后在此可行解的基础上在x的两边进行左右搜索,用新的更优的可行整数解代替原有的可行整数解。用定理(2)和(3)判别是否停止搜索,搜索完毕便得n-r 1维(1≤r≤L)的一个最优整数解。然后求出所有n-r 1维的最优整数解,比较所有n-r 1维的最优解,得n-r 2维的一个最优整数解,如此类推,一定可求得原问题(1)的最优整数解。降维搜索法可以完全平行地推广到求非线性规划的整数解。