On linear problems with complementarity constraints

A mathematical program with complementarity constraints (MPCC) 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 the literature, these problems have been tackled in many different ways: methods that introduce a parameter in order to relax the complementarity constraint, modified simplex methods that use an appropriate rule for choosing the non basic variable in order to preserve complementarity. 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.