求解整数线性规划的一种高效隐数搜寻

Efficient implicit enumerative search for solution to integer linear programs

提出了一种求解整数线性规划的新的隐数算法。首先,该算法引入了一组线性变换,将线性松弛问题的最优非基变量变换到一组新变量,使新变量有更小的取值范围。然后,在目标函数超平面上对非基变量和新变量进行隐数计算,从而大大提高了隐数搜寻的效率。

This paper presents a new implicit enumerative algorithm for integer linear programs.First of all,based on the optimality of the linear programming relaxation problem,a linear transformation of the optimal nonbasic variables into new variables is introduced so that the new variables have fewer intervals.Then,an efficient implicit enumerative search is done on the nonbasic variables and new ones on the objective function hyperplane.The algorithm is of interests in theory.