Probing through the intersection of hyperplanes (Q1262211)

The authors study the linear programming problem of the form max \(c^ Tx\) subject to \(Ax=b\) and \(x=0\) where the elements of A and b are assumed to be nonnegative. The pivot and probe algorithm is as follows. A relaxed linear program is solved. If the solution to the relaxed program is feasible to the original program, it is also optimal. Otherwise some most violated constraints are added to the relaxed program and the new relaxed linear program is solved again. This process is repeated until an optimal solution is found. In this paper, a variant of probe is suggested. Computational results show that this algorithm is faster than the simplex algorithm.