| Full text | |
| Author(s): |
Total Authors: 3
|
| Affiliation: | [1] Fed Univ ABC, Ctr Math Computat & Cognit, Santo Andre - Brazil
[2] Univ Fed Rio Grande do Sul, Inst Informat, Porto Alegre, RS - Brazil
Total Affiliations: 2
|
| Document type: | Journal article |
| Source: | Computers & Operations Research; v. 113, JAN 2020. |
| Web of Science Citations: | 0 |
| Abstract | |
The Unconstrained Binary Quadratic Programming problem (UBQP) belongs to the NP-hard class and has become a framework for modeling a variety of combinatorial optimization problems. The methods most commonly used to solve instances of the UBQP explore the concept of neighborhood of a solution. Given a binary vector x is an element of[0, 1](n), solution to a UBQP instance, a neighborhood of x can be defined by flip moves. Flip moves consist on selecting one or more elements (positions) of x and ``flip{''} their values to their complementary values (i.e., from 1 to 0 or from 0 to 1). Normally, those methods compute a large number of flip moves, and so the whole process to solve an instance can be quite time consuming. In order to reduce this time, some works have proposed ways to efficiently evaluate one or two flip moves, and also extensions to higher order moves. In this paper we propose two closed-form formulas for evaluating quickly any order of flip moves. To test our theoretical findings, we executed an extensive set of computational experiments over well-known instances for the problem. Against common belief, our results show that it is possible to compute high order flip moves very fast. (C) 2019 Elsevier Ltd. All rights reserved. (AU) | |
| FAPESP's process: | 18/03819-4 - Methods for Solving Quadratic Binary Optimization Problems |
| Grantee: | Eduardo Alves de Jesus Anacleto |
| Support Opportunities: | Scholarships in Brazil - Doctorate |