整数规划的凝聚函数法

An aggregate function method for integer programming

传统的代理约束方法虽可加速分支定界法或割平面法的求解速度,但往往会扩大原问题的可行域,不能保证得到原问题的最优解.考虑到代理约束乘子的取值特点,利用极大熵原理对传统代理约束方法进行了改进,给出求解整数规划问题的凝聚函数法,并研究了其理论可行性.当参数取适当大时,该方法得到的问题与原问题完全等价,从而可以通过该方法得到原问题的最优解,且无需对偶计算.算例结果阐释了凝聚函数法的有效性和可行性.

The conventional surrogate constraint method, which can improve the efficiency of branch-and-bound or cutting plane algorithms, can not guarantee to find the optimal solution of the primal problem. A duality gap which is caused by the relaxation of the feasible region of the primal problem often exists. Combining the surrogate constraint method and the maximum entropy principle,an aggregate function method for integer programming is given, which can obtain an absolutely equivalent single constraint problem for the primal problem, and the theoretical feasibility of this method is also studied. Furthermore, this method is guaranteed to succeed in identifying an optimal solution of the primal problem without any actual dual search when parameters are set above the threshold value. The results of the example illustrate the validity and feasibility of the aggregate function method.