A Sectional Pricing Strategy for the Phase-1 Simplex Method

GAO Peiwang

Abstract：The paper presents a sectional pricing strategy for the phase-1 simplex algorithm.Based on this,two variants are derived.Firstly,all nonbasic variables are partitioned into four sections,one of which includes the nonbasic variables in an optimal solution.In the iterative process,pricing is implemented alter-natively in turns in other three sections according to the possibility of those variables remaining nonbasis. Variant 1 uses Cheng's two criteria to change the composition of components in four sections at the outset of the iteration.So it greatly decreases the amount of pricing computation,but spends much more time than the classical simplex algorithm.Variant 2 starts section when the obj ective value arrives at two third of the optimum value,and changes sections by only one of Cheng's criteria.A preliminary test is accomplished on a set of 27 standard instances from NETLIB and MIPLIB.The computational results show that variant 2 uses fewer iterations in total,probes fewer columns,and spend much less computational time than the classical simplex algorithm.Therefore,variant 2 is of the interest in computational performance.