Solving binary programming problems using homotopy theory ideas

Abstract

Purpose

The aim of the study is to show that merging two areas of mathematics – topology and discrete optimization – could result in a viable option to solve classical or specialized integer problems.

Design/methodology/approach

In the paper, discrete topology concepts are applied to propose a metaheuristic algorithm that is capable to solve binary programming problems. Particularly, some of the homotopy for paths principles are used to explore the solution space associated with four well-known NP-hard problems herein considered as follows: knapsack, set covering, bi-level single plant location with order and one-max.

Findings

Computational experimentation confirms that the proposed algorithm performs in an effective manner, and it is able to efficiently solve the sets of instances used for the benchmark. Moreover, the performance of the proposed algorithm is compared with a standard genetic algorithm (GA), a scatter search (SS) method and a memetic algorithm (MA). Acceptable results are obtained for all four implemented metaheuristics, but the path homotopy algorithm stands out.

Originality/value

A novel metaheuristic is proposed for the first time. It uses topology concepts to design an algorithmic framework to solve binary programming problems in an effective and efficient manner.

Citation

Alanís-López, L., Casas-Ramírez, M.-S. and Camacho-Vallejo, J.-F. (2022), "Solving binary programming problems using homotopy theory ideas", Engineering Computations, Vol. 39 No. 5, pp. 1642-1668. https://doi.org/10.1108/EC-04-2021-0251