Integer Programming Methods for Solving Binary Interdiction Games

This paper studies a general class of interdiction problems in which the solution space of both the leader and follower are characterized by two discrete sets denoted the leader’s strategy set and the follower’s structure set. In this setting, the interaction between any strategy-structure pair is assumed to be binary, in the sense that the … Read more

Combinatorial Acyclicity Models for Potential-based Flows

Potential-based flows constitute a basic model to represent physical behavior in networks. Under natural assumptions, the flow in such networks must be acyclic. The goal of this paper is to exploit this property for the solution of corresponding optimization problems. To this end, we introduce several combinatorial models for acyclic flows, based on binary variables … Read more

Optimizing the Response for Arctic Mass Rescue Events

We study a model that optimizes the response to a mass rescue event in Arctic Alaska. The model contains dynamic logistics decisions for a large-scale maritime evacuation with the objectives of minimizing the impact of the event on the evacuees and the average evacuation time. Our proposed optimization model considers two interacting networks – the … Read more

Quantum Bridge Analytics II: Network Optimization and Combinatorial Chaining for Asset Exchange

Quantum Bridge Analytics relates to methods and systems for hybrid classical-quantum computing, and is devoted to developing tools for bridging classical and quantum computing to gain the benefits of their alliance in the present and enable enhanced practical application of quantum computing in the future. This is the second of a two-part tutorial that surveys … Read more

On the NP-Completeness of the Multi-Period Minimum Spanning Tree Problem

In this note, we consider the Multi-period Minimum Spanning Tree Problem (MMST), a variant of the well known Minimum Spanning Tree Problem (MST), that consists in the fol- lowing. Given a connected and undirected graph G and a finite discrete time horizon, one has to schedule the moment in time edges are added to a … Read more

Column Generation based Alternating Direction Methods for solving MINLPs

Traditional decomposition based branch-and-bound algorithms, like branch-and-price, can be very efficient if the duality gap is not too large. However, if this is not the case, the branch-and-bound tree may grow rapidly, preventing the method to find a good solution. In this paper, we present a new decompositon algorithm, called ADGO (Alternating Direction Global Optimization … Read more

Finding the Most Likely Infection Path in Networks with Limited Information

In this paper we address the problem of identifying the most likely infection pattern responsible for the spread of a disease in a network. In particular, we focus on the scenario where limited information (i.e. infection reports) is available during an ongoing outbreak. For this problem we propose a maximum likelihood model and present an … Read more

Optimal Response to Epidemics and Cyber Attacks in Networks

This paper introduces novel formulations for optimally responding to epidemics and cyber attacks in networks. In our models, at a given time period, network nodes (e.g., users or computing resources) are associated with probabilities of being infected, and each network edge is associated with some probability of propagating the infection. A decision maker would like … Read more

Complexity and Exact Solution Approaches to the Minimum Changeover Cost Arborescence Problem

We are given a digraph G = (N, A), where each arc is colored with one among k given colors. We look for a spanning arborescence T of G rooted at a given node and having minimum changeover cost. We call this the Minimum Changeover Cost Arborescence problem. To the authors’ knowledge, it is a … Read more

GRASP with path-relinking for network migration scheduling

Network migration scheduling is the problem where inter-nodal traffic from an outdated telecommunications network is to be migrated to a new network. Nodes are migrated, one at each time period, from the old to the new network. All traffic originating or terminating at given node in the old network is moved to a specific node … Read more