A bi-level model and solution methods for partial interdiction problem on capacitated hierarchical facilities

Asefe Forghani, Farzad Dehghanian, Majid Salari, Yousef Ghiami

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

Due to the importance of gaining high levels of customer satisfaction in today's competitive world, making appropriate decisions in the face of malicious attacks is valued highly by many organizations. In this paper, to predict and handle the destructive effects of an intentional attack on capacitated nested hierarchical facilities, a bi-level partial interdiction problem is proposed. In this problem, there is an interdictor who can attack facilities partially in different levels. Subsequently, the system defender could respond to the customers’ demand in two different ways, namely through the remaining system facilities and the outsourcing option. The goal of the defender is to minimize the satisfaction cost of all customers’ demand under the interdictor's attacking scenario. This problem can be modeled as a bi-level programming model in which an interdictor and the system defender play the role of the leader and the follower, respectively. Due to the inherent complexity of the bi-level programming models, we develop a heuristic approach, namely “FDS”, to obtain near optimal solutions within a reasonable running time. In each iteration of the FDS, an interdiction scenario is produced heuristically and, thereupon CPLEX solver is called to solve the lower level of the model. To evaluate the effectiveness of the proposed model, a comparison between the cost of customers’ demand satisfaction in both absence and presence of the bi-level model is drawn. Computational results show that for those instances in which the optimal solutions are available, the proposed model can, on average, achieve a saving of 7.94%.
Original languageEnglish
Article number104831
JournalComputers and Operations Research
Publication statusAccepted/In press - 2020

Fingerprint

Partial
Bilevel Programming
Customers
Attack
Programming Model
Optimal Solution
Scenarios
Customer Satisfaction
Outsourcing
Costs
Model
Computational Results
Customer satisfaction
Decision Making
Heuristics
Minimise
Iteration
Predict
Evaluate
Decision making

Keywords

  • Partial interdiction problem
  • Capacitated nested hierarchical facilities
  • Bi-level programming
  • Heuristics

Cite this

@article{8de366ca93da4eaf9e106cb292d69a52,
title = "A bi-level model and solution methods for partial interdiction problem on capacitated hierarchical facilities",
abstract = "Due to the importance of gaining high levels of customer satisfaction in today's competitive world, making appropriate decisions in the face of malicious attacks is valued highly by many organizations. In this paper, to predict and handle the destructive effects of an intentional attack on capacitated nested hierarchical facilities, a bi-level partial interdiction problem is proposed. In this problem, there is an interdictor who can attack facilities partially in different levels. Subsequently, the system defender could respond to the customers’ demand in two different ways, namely through the remaining system facilities and the outsourcing option. The goal of the defender is to minimize the satisfaction cost of all customers’ demand under the interdictor's attacking scenario. This problem can be modeled as a bi-level programming model in which an interdictor and the system defender play the role of the leader and the follower, respectively. Due to the inherent complexity of the bi-level programming models, we develop a heuristic approach, namely “FDS”, to obtain near optimal solutions within a reasonable running time. In each iteration of the FDS, an interdiction scenario is produced heuristically and, thereupon CPLEX solver is called to solve the lower level of the model. To evaluate the effectiveness of the proposed model, a comparison between the cost of customers’ demand satisfaction in both absence and presence of the bi-level model is drawn. Computational results show that for those instances in which the optimal solutions are available, the proposed model can, on average, achieve a saving of 7.94{\%}.",
keywords = "Partial interdiction problem, Capacitated nested hierarchical facilities, Bi-level programming, Heuristics",
author = "Asefe Forghani and Farzad Dehghanian and Majid Salari and Yousef Ghiami",
year = "2020",
language = "English",
journal = "Computers and Operations Research",
issn = "0305-0548",
publisher = "Elsevier Limited",

}

A bi-level model and solution methods for partial interdiction problem on capacitated hierarchical facilities. / Forghani, Asefe; Dehghanian, Farzad; Salari, Majid; Ghiami, Yousef.

In: Computers and Operations Research, 2020.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

T1 - A bi-level model and solution methods for partial interdiction problem on capacitated hierarchical facilities

AU - Forghani, Asefe

AU - Dehghanian, Farzad

AU - Salari, Majid

AU - Ghiami, Yousef

PY - 2020

Y1 - 2020

N2 - Due to the importance of gaining high levels of customer satisfaction in today's competitive world, making appropriate decisions in the face of malicious attacks is valued highly by many organizations. In this paper, to predict and handle the destructive effects of an intentional attack on capacitated nested hierarchical facilities, a bi-level partial interdiction problem is proposed. In this problem, there is an interdictor who can attack facilities partially in different levels. Subsequently, the system defender could respond to the customers’ demand in two different ways, namely through the remaining system facilities and the outsourcing option. The goal of the defender is to minimize the satisfaction cost of all customers’ demand under the interdictor's attacking scenario. This problem can be modeled as a bi-level programming model in which an interdictor and the system defender play the role of the leader and the follower, respectively. Due to the inherent complexity of the bi-level programming models, we develop a heuristic approach, namely “FDS”, to obtain near optimal solutions within a reasonable running time. In each iteration of the FDS, an interdiction scenario is produced heuristically and, thereupon CPLEX solver is called to solve the lower level of the model. To evaluate the effectiveness of the proposed model, a comparison between the cost of customers’ demand satisfaction in both absence and presence of the bi-level model is drawn. Computational results show that for those instances in which the optimal solutions are available, the proposed model can, on average, achieve a saving of 7.94%.

AB - Due to the importance of gaining high levels of customer satisfaction in today's competitive world, making appropriate decisions in the face of malicious attacks is valued highly by many organizations. In this paper, to predict and handle the destructive effects of an intentional attack on capacitated nested hierarchical facilities, a bi-level partial interdiction problem is proposed. In this problem, there is an interdictor who can attack facilities partially in different levels. Subsequently, the system defender could respond to the customers’ demand in two different ways, namely through the remaining system facilities and the outsourcing option. The goal of the defender is to minimize the satisfaction cost of all customers’ demand under the interdictor's attacking scenario. This problem can be modeled as a bi-level programming model in which an interdictor and the system defender play the role of the leader and the follower, respectively. Due to the inherent complexity of the bi-level programming models, we develop a heuristic approach, namely “FDS”, to obtain near optimal solutions within a reasonable running time. In each iteration of the FDS, an interdiction scenario is produced heuristically and, thereupon CPLEX solver is called to solve the lower level of the model. To evaluate the effectiveness of the proposed model, a comparison between the cost of customers’ demand satisfaction in both absence and presence of the bi-level model is drawn. Computational results show that for those instances in which the optimal solutions are available, the proposed model can, on average, achieve a saving of 7.94%.

KW - Partial interdiction problem

KW - Capacitated nested hierarchical facilities

KW - Bi-level programming

KW - Heuristics

M3 - Article

JO - Computers and Operations Research

JF - Computers and Operations Research

SN - 0305-0548

M1 - 104831

ER -