On linear problems with complementarity constraints

A mathematical program with complementarity constraints is an optimization problem with equality/inequality constraints in which a complementarity type constraint is considered in addition. This complementarity condition modifies the feasible region so as to remove many of those properties that are usually important to obtain the standard optimality conditions, e.g., convexity and constraint qualifications. In this paper, in the linear case, we introduce a decomposition method of the given problem in a sequence of parameterized problems, that aim to force complementarity. Once we obtain a feasible solution, by means of duality results, we are able to eliminate a set of parameterized problems which are not worthwhile to be considered. Furthermore, we provide some bounds for the optimal value of the objective function and we present an application of the proposed technique in a non trivial example and some numerical experiments.