Abstract We consider the simultaneous propagation of two contagions over a social network. We assume a threshold model for the propagation of the two contagions and use the formal framework of discrete dynamical systems. In particular, we study an optimization problem where the goal is to minimize the total number of new infections subject to a budget constraint on the total number of available vaccinations for the contagions. While this problem has been considered in the literature for a single contagion, our work considers the simultaneous propagation of two contagions. This optimization problem is NPhard. We present two main solution approaches for the problem, namely an integer linear programming (ILP) formulation to obtain optimal solutions and a heuristic based on a generalization of the set cover problem. We carry out a comprehensive experimental evaluation of our solution approaches using many realworld networks. The experimental results show that our heuristic algorithm produces solutions that are close to the optimal solution and runs several orders of magnitude faster than the ILPbased approach for obtaining optimal solutions. We also carry out sensitivity studies of our heuristic algorithm.
more »
« less
A Bounded Formulation for The School Bus Scheduling Problem
This paper proposes a new formulation for the school bus scheduling problem (SBSP), which optimizes school start times and bus operation times to minimize transportation cost. The goal is to minimize the number of buses to serve all bus routes such that each route arrives in a time window before school starts. We show that introducing contextspecific features, common in many school districts, can lead to a new timeindexed integer linear programming (ILP) formulation. Based on a strengthened version of the linear relaxation of the ILP, we develop a dependent randomized rounding algorithm that yields nearoptimal solutions for largescale problem instances. The efficient formulation and solution approach enable quick generation of multiple solutions to facilitate strategic planning, which we demonstrate with data from two public school districts in the United States. We also generalize our methodologies to solve a robust version of the SBSP.
more »
« less
 Award ID(s):
 1727744
 NSFPAR ID:
 10378746
 Date Published:
 Journal Name:
 Transportation Science
 Volume:
 56
 Issue:
 5
 ISSN:
 00411655
 Page Range / eLocation ID:
 1148 to 1164
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


Emerging interdatacenter applications involving data transferred, processed, and analyzed at multiple data centers, such as virtual machine migrations, realtime data backup, remote desktop, and virtual data centers, can be modeled as virtual network requests that share computing and spectrum resources of a common substrate physical interdatacenter network. Recent advances make flexible optical networks an ideal candidate for meeting the dynamic and heterogeneous connection demands between datacenters. In this paper, we address the static (offline) version of the virtual network embedding problem in flexible optical networks equipped with sliceable bandwidth variable transponders (SBVTs). The objective is to minimize the total number of required SBVTs in the network. An Integer Linear Programming (ILP) formulation is presented, lower bounds are derived, and four heuristics are proposed and compared. Simulation results are presented to show the effectiveness of the proposed approaches.more » « less

Given a weighted graph G(V, E) and t ≥ 1, a subgraph H is a t–spanner of G if the lengths of shortest paths in G are preserved in H up to a multiplicative factor of t. The subsetwise spanner problem aims to preserve distances in G for only a subset of the vertices. We generalize the minimumcost subsetwise spanner problem to one where vertices appear on multiple levels, which we call the multilevel graph spanner (MLGS) problem, and describe two simple heuristics. Applications of this problem include road/network building and multilevel graph visualization, especially where vertices may require different grades of service. We formulate a 0–1 integer linear program (ILP) of size O(EV 2) for the more general minimum pairwise spanner problem, which resolves an open question by Sigurd and Zachariasen on whether this problem admits a useful polynomialsize ILP. We extend this ILP formulation to the MLGS problem, and evaluate the heuristic and ILP performance on random graphs of up to 100 vertices and 500 edges.more » « less

The rising availability of heterogeneous networked devices highlights new opportunities for distributed artificial intelligence. This work proposes an Integer Linear Programming (ILP) optimization scheme to assign layers of a neural network in a distributed setting with heterogeneous devices representing edge, hub, and cloud in order to minimize the overall inference latency. The ILP formulation captures the tradeoff between avoiding communication cost when executing consecutive layers on the same device versus the latency benefit due to weight preloading when an idle device is waiting to receive the results of an earlier layer across the network. In our experiments we show the layer assignment and inference latency of a neural network can significantly vary depending on the types of devices in the network and their communications bandwidths.more » « less

This work addresses inverse linear optimization, where the goal is to infer the unknown cost vector of a linear program. Specifically, we consider the datadriven setting in which the available data are noisy observations of optimal solutions that correspond to different instances of the linear program. We introduce a new formulation of the problem that, compared with other existing methods, allows the recovery of a less restrictive and generally more appropriate admissible set of cost estimates. It can be shown that this inverse optimization problem yields a finite number of solutions, and we develop an exact twophase algorithm to determine all such solutions. Moreover, we propose an efficient decomposition algorithm to solve large instances of the problem. The algorithm extends naturally to an online learning environment where it can be used to provide quick updates of the cost estimate as new data become available over time. For the online setting, we further develop an effective adaptive sampling strategy that guides the selection of the next samples. The efficacy of the proposed methods is demonstrated in computational experiments involving two applications: customer preference learning and cost estimation for production planning. The results show significant reductions in computation and sampling efforts. Summary of Contribution: Using optimization to facilitate decision making is at the core of operations research. This work addresses the inverse problem (i.e., inverse optimization), which aims to infer unknown optimization models from decision data. It is, conceptually and computationally, a challenging problem. Here, we propose a new formulation of the datadriven inverse linear optimization problem and develop an efficient decomposition algorithm that can solve problem instances up to a scale that has not been addressed previously. The computational performance is further improved by an online adaptive sampling strategy that substantially reduces the number of required data points.more » « less