Title: A two-phase method based on the branch and bound algorithm for solving the bi-objective set covering problem

Authors: Imane Hamidi; Djamal Chaabane

Addresses: AMCD-RO Laboratory, Faculty of Mathematics, Department of Operations Research, DGRSDT, USTHB, B.P. 32, El-Alia, Bab Ezzouar, Algiers, 16111, Algeria ' AMCD-RO Laboratory, Faculty of Mathematics, Department of Operations Research, DGRSDT, USTHB, B.P. 32, El-Alia, Bab Ezzouar, Algiers, 16111, Algeria

Abstract: Multicriteria set covering problem (SCP) is classified in the category of NP-hard combinatorial optimisation problems. In this paper, we propose a new exact approach to solve the bi-objective set covering problem (BOSCP); where branch and bound (B&B) technique is the pivot of the procedure skeleton, in both phases. We focus, particularly, on the second phase where a new branching architecture and a new priority order of branching variables are introduced. A rich set of experiments containing a numerical illustration and some MCDM-benchmark BOSCP instances are used to validate our developed method. Some comparisons to an existing two-phase method have been done using the MCDM-benchmark BOSCP instances.

Keywords: multi-objective integer linear programming; MOILP; combinatorial problem; set covering problem; branch and bound; B&B; two-phase method.

DOI: 10.1504/IJMCDM.2023.134923

International Journal of Multicriteria Decision Making, 2023 Vol.9 No.4, pp.281 - 321

Accepted: 29 Nov 2022
Published online: 21 Nov 2023 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article