Weighted iterated local branching for mathematical programming problems with binary variables

Filipe Rodrigues, Agostinho Agra, Lars Magnus Hvattum () and Cristina Requejo
Additional contact information
Filipe Rodrigues: University of Lisbon
Agostinho Agra: University of Aveiro
Lars Magnus Hvattum: Molde University College
Cristina Requejo: University of Aveiro

Journal of Heuristics, 2022, vol. 28, issue 3, No 4, 329-350

Abstract: Abstract Local search algorithms are frequently used to handle complex optimization problems involving binary decision variables. One way of implementing a local search procedure is by using a mixed-integer programming solver to explore a neighborhood defined through a constraint that limits the number of binary variables whose values are allowed to change in a given iteration. Recognizing that not all variables are equally promising to change when searching for better neighboring solutions, we propose a weighted iterated local branching heuristic. This new procedure differs from similar existing methods since it considers groups of binary variables and associates with each group a limit on the number of variables that can change. The groups of variables are defined using weights that indicate the expected contribution of flipping the variables when trying to identify improving solutions in the current neighborhood. When the mixed-integer programming solver fails to identify an improving solution in a given iteration, the proposed heuristic may force the search into new regions of the search space by utilizing the group of variables that are least promising to flip. The weighted iterated local branching heuristic is tested on benchmark instances of the optimum satisfiability problem, and computational results show that the weighted method is superior to an alternative method without weights.

Keywords: Neighborhood search; Mixed-integer programming; Matheuristic; Boolean optimization (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-022-09496-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:28:y:2022:i:3:d:10.1007_s10732-022-09496-2

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-022-09496-2

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().