On the big

When the affine scaling algorithm is applied to a linear program, an artificial linear program having an interior feasible solution is usually constructed, from which the algorithm starts. The artificial linear program involves a positive number called the big ℳ. Theoretically, there exists an ℳ* such that the original problem to be solved is equivalent to the artificial linear program if ℳ>ℳ*. Practically, however, such an ℳ* is unknown and a safe estimate of ℳ is often too large. This paper proposes a method of updating ℳ to a suitable value during the iteration of the affine scaling algorithm. As ℳ becomes large, the method gives information on infeasibility of the original problem or its dual.