Improving the solution of indefinite quadratic programs and linear programs with complementarity constraints by a progressive MIP method

Abstract Indefinite quadratic programs (QPs) are known to be very difficult to be solved to global optimality, so are linear programs with linear complementarity constraints (LPCCs). It is a classic result that for a QP with an optimal solution, the QP has an equivalent formulation as a certain LPCC in terms of their globally optimal solutions. Thus it is natural to attempt to solve an (indefinite) QP as a LPCC. This paper presents a progressive mixed integer linear programming method for solving a general LPCC. Instead of solving the LPCC with a full set of integer variables expressing the complementarity conditions, the presented method solves a finite number of mixed integer subprograms by starting with a small fraction of integer variables and progressively increasing this fraction. After describing the PIP (for progressive integer programming) method and providing some details for its implementation and tuning possibilities, we demonstrate, via an extensive set of computational experiments, the superior performance of the progressive approach over the direct solution of the full-integer formulation of the LPCCs in obtaining high-quality solutions. It is also shown that the solution obtained at the termination of the PIP method is a local minimizer of the LPCC, a property that cannot be claimed by any known non-enumerative method for solving this nonconvex program. In all the experiments, the PIP method is initiated at a feasible solution of the LPCC obtained from a nonlinear programming solver, and with high likelihood, can successfully improve it. Thus, the PIP method can improve a stationary solution of an indefinite QP, something that is not likely to be achievable by a nonlinear programming method. Finally, some analysis is presented that provides a better understanding of the roles of the LPCC suboptimal solutions in the local optimality of the indefinite QP. This local aspect of the connection between a QP and its LPCC formulation has seemingly not been addressed in the literature.