An exact approach for the r-interdiction covering problem with fortification

作     者：Roboredo, Marcos Costa Aizemberg, Luiz Pessoa, Artur Alves 

作者机构：Univ Fed Fluminense Dept Engn Prod Rua Passo Patria 156 BR-24210240 Niteroi RJ Brazil Banco Nacl Desenvolvimento Ave Republ Chile 100 BR-20031917 Rio De Janeiro RJ Brazil 

出 版 物：《CENTRAL EUROPEAN JOURNAL OF OPERATIONS RESEARCH》 (中欧运筹学杂志)

年 卷 期：2019年第27卷第1期

页      面：111-131页

核心收录：

学科分类：02[经济学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 

主　　题：Integer programming Branch-and-cut algorithm r-Interdiction covering problem with fortification 

摘      要：In this paper we treat the r-interdiction covering problem with fortification (RICF). The environment of this problem is composed of a set of customers J and a set of facilities I. For each customer j, there is set of facilities containing the facilities that can cover the demand of j. The system efficiency is given by the sum of the total covered demand. The facilities are subject to interdictions. When a facility is interdicted, it can not cover the demand of any customer. To mitigate the negative impact of the interdictions on the system efficiency, the system planner can fortify a subset of facilities. If a facility is fortified then it can not be interdicted. The RICF consists of choosing q facilities to be fortified knowing that r not fortified facilities will be interdicted at the worst case. We propose a branch-and-cut algorithm for the problem. Our results are compared with the exact method found in the literature, being faster for the most instances, mainly the large ones.