Solving binary programming problems using homotopy theory ideas. Issue 5 (30th November 2021)

• Record Type: Journal Article
• Authors: Alanís-López, Lilia; Casas-Ramírez, Martha-Selene; Camacho-Vallejo, José-Fernando
• Is Part Of: Engineering computations. Volume 39:Issue 5(2022)
• Page Start: 1642
• Page End: 1668
• Publication Date: 2021-11-30
• Subjects: Homotopy theory -- Binary optimization -- Metaheuristics; Computer-aided engineering -- Periodicals; Computer graphics -- Periodicals; 620.00285
• DOI: 10.1108/EC-04-2021-0251
• Languages: English
• ISSNs: 0264-4401

Abstract

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.