Dimensionality reduction for binary quadratic programming problems

Abstract This paper addresses the constrained binary quadratic problem (QP). This problem consists in minimizing a quadratic function a binary variables (0-1 variables) with linear constraints. Accordingly, in this work, We have generalized reliable fixing criteria (F₀) and (F₁) for the (QP) problem. The purpose of these fixing criteria is to facilitate the resolution of the initial problem (QP) where through these criteria we can decrease the dimension of the (QP) problem when it is possible and sometimes we can solve this problem completely by using a repeat loop based on these criteria (QPFA algorithm). Numerical results are presented to consolidate the demonstrated theoretical results and prove efficiency and performance in terms of speed, quality and robustness of our work. Mathematics Subject Classification: 90C20 , 90C27 , 90C10