Binary NCP: a new approach for solving nonlinear complementarity problems

Abstract

A general nonlinear complementarity problem (NCP) is formulated as a finite set optimization problem called binary NCP, where design variables are identified by n-bit binary numbers. The binary NCP corresponds to the problem of finding a vertex of an n-dimensional unit cube with zero cost value. Two geometrically intuitive algorithms based on the geometry of the unit cube and another algebraically intuitive one based on the distribution of negative variables are implemented. They are called VSA (vertex search algorithm), FSA (face search algorithm), and NSA (negative-entry search algorithm). FSA and NSA are robust as shown by test problems of small to medium size. FSA, which is like a coordinate search algorithm, is much superior to the other two. It is simple to program and most reliable not only for NCPs but also for a new category called joker search problems.