TY - JOUR

T1 - Planning a Defense That Minimizes a Resource Deficit in the Worst-Case Scenario of Supply Network Destruction

AU - Beresnev, V. L.

AU - Melnikov, A. A.

N1 - Funding Information: The authors were supported by the Russian Science Foundation (project no. 17–11–01021). Publisher Copyright: © 2020, Pleiades Publishing, Ltd. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2020/8/1

Y1 - 2020/8/1

N2 - We consider same model of planning the defense of edges of a supply network. Thevertices of the network represent the consumers and the providers of a resource, while the edgesallow us to transmit the resource without delays and capacity constraints. The Defender commitsa bounded budget to protect some of the edges, aiming to minimize the damage that is causedby the destruction of the unprotected edges. To measure the damage, we apply the value of thetotal resource deficit caused by the worst-case scenario of partial network destruction. TheDefender’s problem falls into the family of “Defender–Attacker” problems that are formalized asthe minimax mixed-integer programming problems. To find an optimal Defender’s solution, wesuggest some two cut generation schemes based on a reformulation of the problem asa mixed-integer problem with exponentially many constraints.

AB - We consider same model of planning the defense of edges of a supply network. Thevertices of the network represent the consumers and the providers of a resource, while the edgesallow us to transmit the resource without delays and capacity constraints. The Defender commitsa bounded budget to protect some of the edges, aiming to minimize the damage that is causedby the destruction of the unprotected edges. To measure the damage, we apply the value of thetotal resource deficit caused by the worst-case scenario of partial network destruction. TheDefender’s problem falls into the family of “Defender–Attacker” problems that are formalized asthe minimax mixed-integer programming problems. To find an optimal Defender’s solution, wesuggest some two cut generation schemes based on a reformulation of the problem asa mixed-integer problem with exponentially many constraints.

KW - cut generation

KW - total deficit

KW - “Defender–Attacker” problem

UR - http://www.scopus.com/inward/record.url?scp=85094637726&partnerID=8YFLogxK

U2 - 10.1134/S1990478920030023

DO - 10.1134/S1990478920030023

M3 - Article

AN - SCOPUS:85094637726

VL - 14

SP - 416

EP - 429

JO - Journal of Applied and Industrial Mathematics

JF - Journal of Applied and Industrial Mathematics

SN - 1990-4789

IS - 3

ER -