A descent approach to solving the complementary programming problem

In recent years, much attention has focused on mathematical programming problems with equilibrium constraints. This paper considers the case where the constraints are complementarity constraints. Problems of this type arise, for instance, in the design of traffic networks. Here the paper develops a descent algorithm for this problem that will converge to a local optimum in a finite number of iterations. The method involves solving a sequence of subproblems that are linear programs. Computational tests comparing the present algorithm with the branch-and-bound algorithm bear out the efficacy of the method. When solving large problems, there is a definite advantage to coupling both methods. A local optimum incumbent provided by the present algorithm can significantly reduce the computational effort required by the branch-and-bound algorithm.