Closed-form formulas for evaluating r-flip moves to the unconstrained binary quadratic programming problem

Autor(es)

Anacleto, Eduardo A. J. ^[1] ; Meneses, Claudio N. ^[1] ; Ravelo, Santiago V. ^[2]

Afiliação do(s) autor(es)

^[1] Fed Univ ABC, Ctr Math Computat & Cognit, Santo Andre - Brazil

^[2] Univ Fed Rio Grande do Sul, Inst Informat, Porto Alegre, RS - Brazil

• Tipo de documento: Artigo Científico
• Fonte: Computers & Operations Research; v. 113, JAN 2020.
• Citações Web of Science: 0

Resumo

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)

• Processo FAPESP: 18/03819-4 - Métodos para Resolução de Problemas de Otimização Quadráticos Binários
• Beneficiário: Eduardo Alves de Jesus Anacleto
• Modalidade de apoio: Bolsas no Brasil - Doutorado