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

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.