Two-stage stochastic days-off scheduling of multi-skilled analysts with training options

Motivated by a cybersecurity application, this paper studies a two-stage, stochastic days-off scheduling problem with 1) many types of jobs that require specialized training, 2) many multi-skilled analysts, 3) the ability to shape analyst skill sets through training decisions, and 4) a large number of possible future demand scenarios. We provide a integer linear program … Read more

A Two-Stage Stochastic Program for Multi-shift, Multi-analyst, Workforce Optimization with Multiple On Call Options

Motivated by a cybersecurity workforce optimization problem, this paper investigates optimizing staffing and shift scheduling decisions given unknown demand and multiple on call staffing options at a 24/7 firm with three shifts per day, three analyst types, and several staffing and scheduling constraints. We model this problem as a two-stage stochastic program and solve it … Read more

Coverings and Matchings in r-Partite Hypergraphs

Ryser’s conjecture postulates that, for $r$-partite hypergraphs, $\tau \leq (r-1) \nu$ where $\tau$ is the covering number of the hypergraph and $\nu$ is the matching number. Although this conjecture has been open since the 1960s, researchers have resolved it for special cases such as for intersecting hypergraphs where $r \leq 5$. In this paper, we … Read more

An Efficient Algorithm for Computing Robust Minimum Capacity s-t Cuts

The Minimum Capacity s-t Cut Problem (Min Cut) is an intensively studied problem in combinatorial optimization. In this paper, we study Min Cut when arc capacities are uncertain but known to exist in pre-specified intervals. This framework can be used to model many real-world applications of Min Cut under data uncertainty such as in open-pit … Read more

The Maximum Flow Network Interdiction Problem: Valid Inequalities, Integrality Gaps, and Approximability

We study the Maximum Flow Network Interdiction Problem (MFNIP). We present two classes of polynomially separable valid inequalities for Cardinality MFNIP. We also prove the integrality gap of the LP relaxation of Wood’s (1993) integer program is not bounded by a constant factor, even when the LP relaxation is strengthened by our valid inequalities. Finally, … Read more

Rapidly Solving an Online Sequence of Maximum Flow Problems

We investigate how to rapidly solve an online sequence of maximum flow problems. Sequences of maximum flow problems arise in a diverse collection of settings, including stochastic network programming and real-time scheduling of jobs on a two-processor computer. In this paper, we formulate solving an online sequence of maximum flow problems as the Maximum Flow … Read more