单纯形算法的两种部分定价策略

Two Partial Pricing Strategies for the Simplex Algorithm

根据Hu和Johnson的原始一对偶单纯形算法原理，提出了两种部分定价策略．给定一组原始一对偶可行解，首先，选择与原始问题简约价值系数为负且对偶松弛变量取零值相应的非基变量作为部分定价变量，再用Dantzig准则的单纯形算法求解该原始子问题．其次，针对原始退化问题，选择相应于原始问题简约价值系数小于某个适当小正数的非基变量进行部分定价，然后应用Bland准则的单纯形算法求解原始子问题，以克服退化可能引起的循环现象．最后，对来自NETLIB和MIPLIB的一些典型算例执行初步数值试验，结果表明，与经典单纯形算法相比，提出的算法具有更好的计算表现．

Based on the principle of the primal-dual simplex algorithm from Hu and Johnson, this paper presents two partial pricing strategies for the simplex algorithm. Given a set of primal and dual feasible solutions, first of all, the nonbasic variables corresponding to the reduced costs with the nonnegative value at the primal basis and the dual relaxed variables with zero are selected as the partial pricing ones, and then the simplex algorithm by Dantzig rule is applied to solve the associated linear subprograms. Next, for degenerate problems, the nonbasic variables corresponding to the reduced costs smaller than one positive number are used to perform the partial pricing, and then the simplex algorithm by Bland rule is applied to solve the associated linear subprograms. So, cycling is avoided. Finally, numerical test on some standard instances from NETLIB and MIPLIB is accomplished. The computational results show that comparing to the classical simplex algorithm, our algorithms are better in computational performance.