Extending a classic result of Giannessi and Tomasin [\textit{Lecture Notes in Comput. Sci. 3}, Springer, 1973, pp. 437–449], this paper shows that a binary-constrained quadratic-defined optimization problem can be formulated as a binary-constrained linear program with linear complementarity constraints (Bi-LPCC). The term “quadratic-defined problems” encompasses many problems that are defined by quadratic functions in the objective, constraints, and even in a lower-level problem. The binary restriction of some variables adds to the challenge in the rigorous solution of these problems. The Bi-LPCC formulation enables all these special cases to be solvable by mixed-integer linear programming, either in their full integer (denoted FMIP) formulation, or by the progressive integer programming (PIP) enhancement. The superior performance of the PIP method over the FMIP version is demonstrated by some extensive computational results on some test problems of binary-constrained quadratic programs with linear complementarity and variants of the simplex constraints. Theoretically, assuming solvability of the given problem, the solution obtained by PIP is provably to be a locally optimal solution of the problem, which is globally optimal if the full-IP version is solved to optimality.
Citation
Technical Report, Daniel J. Epstein Department of Industrial and Systems Engineering, University of Southern California, Los Angeles, U.S.A. (2026)