New approach to solve unconstrained binary quadratic problem

¹ Normandie Univ., Univ.Le Havre, LMAH, FR CNRS 3335, 76600 Le Havre, France
² Lebanese University, Laboratory of Informatics and Applications LIA, Doctoral School in Science and Technology DSST, Mitein street Tripoli, Lebanon
³ Université Toulouse II, 5 Allée Antonio Machado, 31058 Toulouse, CEDEX 9, France
⁴ Normandie Univ., Univ.Le Havre, ISEL, 76600 Le Havre, France

^* Corresponding author: r_battikh@hotmail.com

Received: 23 May 2023
Accepted: 16 April 2024

Abstract

This paper addresses the unconstrained binary quadratic problem (UQP). This problem consists in minimizing a quadratic function a binary variables (0−1 variables). Accordingly, in this work, a hybrid algorithm called (HA), based on simulated annealing algorithm with some combination procedures, have been proposed and a branch and bound procedure, based on this algorithm (HA) and semidefinite programming problem (SDP), has been applied. The purpose of this approach is to facilitate the resolution of the initial problem and reduce its dimension by using some fixing criteria in a repeat loop. Numerical results are presented to consolidate the demonstrated theoretical results and prove effectiveness and performance in speed and quality of our new approach.