Technical Note—The Use of Cuts in Complementary Programming

A complementary programming problem is a linear programming problem with the additional restriction that x_px_q = 0 holds for each specified pair (x_p, x_q). This paper obtains constraints called C-cuts from the restriction x_px_q = 0, and uses them to facilitate the computation of the branch-and-bound procedure proposed in an earlier paper [Opns. Res. 19, 1523–1528 (1971)]. Some computational results are also reported.