We introduce a new class of distributionally robust optimization problems under decision-dependent ambiguity sets. In particular, as our ambiguity sets, we consider balls centered on a decision-dependent probability distribution. The balls are based on a class of earth mover’s distances that includes both the total variation distance and the Wasserstein metrics. We discuss the main computational challenges in solving the problems of interest and provide an overview of various settings leading to tractable formulations. Some of the arising side results, such as the mathematical programming expressions for robustified risk measures in a discrete space, are also of independent interest. Finally, we rely on state-of-the-art modeling techniques from machine scheduling and humanitarian logistics to arrive at potentially practical applications, and present a numerical study for a novel risk-averse scheduling problem with controllable processing times. Summary of Contribution: In this study, we introduce a new class of optimization problems that simultaneously address distributional and decision-dependent uncertainty. We present a unified modeling framework along with a discussion on possible ways to specify the key model components, and discuss the main computational challenges in solving the complex problems of interest. Special care has been devoted to identifying the settings and problem classes where these challenges can be mitigated. In particular, we provide model reformulation results, including mathematical programming expressions for robustified risk measures, and describe how these results can be utilized to obtain tractable formulations for specific applied problems from the fields of humanitarian logistics and machine scheduling. Toward demonstrating the value of the modeling approach and investigating the performance of the proposed mixed-integer linear programming formulations, we conduct a computational study on a novel risk-averse machine scheduling problem with controllable processing times. We derive insights regarding the decision-making impact of our modeling approach and key parameter choices.

BACKGROUND: Methylation studies are a promising complement to genetic studies of DNA sequence. However, detailed prior biological knowledge is typically lacking, so methylome-wide association studies (MWAS) will be critical to detect disease relevant sites. A cost-effective approach involves the next-generation sequencing (NGS) of single-end libraries created from samples that are enriched for methylated DNA fragments. A limitation of single-end libraries is that the fragment size distribution is not observed. This hampers several aspects of the data analysis such as the calculation of enrichment measures that are based on the number of fragments covering the CpGs. RESULTS: We developed a non-parametric method that uses isolated CpGs to estimate sample-specific fragment size distributions from the empirical sequencing data. Through simulations we show that our method is highly accurate. While the traditional (extended) read count methods resulted in severely biased coverage estimates and introduces artificial inter-individual differences, through the use of the estimated fragment size distributions we could remove these biases almost entirely. Furthermore, we found correlations of 0.999 between coverage estimates obtained using fragment size distributions that were estimated with our method versus those that were "observed" in paired-end sequencing data. CONCLUSIONS: We propose a non-parametric method for estimating fragment size distributions that is highly precise and can improve the analysis of cost-effective MWAS studies that sequence single-end libraries created from samples that are enriched for methylated DNA fragments.

Given a directed graph G=(V,A) with a non-negative weight (length) function on its arcs w:A→ℝ+ and two terminals s,t∈V, our goal is to destroy all short directed paths from s to t in G by eliminating some arcs of A. This is known as the short paths interdiction problem. We consider several versions of it, and in each case analyze two subcases: total limited interdiction, when a fixed number k of arcs can be removed, and node-wise limited interdiction, when for each node v∈V a fixed number k(v) of out-going arcs can be removed. Our results indicate that the latter subcase is always easier than the former one. In particular, we show that the short paths node-wise interdiction problem can be efficiently solved by an extension of Dijkstra’s algorithm. In contrast, the short paths total interdiction problem is known to be NP-hard. We strengthen this hardness result by deriving the following inapproximability bounds: Given k, it is NP-hard to approximate within a factor c<2 the maximum s–t distance d(s,t) obtainable by removing (at most) k arcs from G. Furthermore, given d, it is NP-hard to approximate within a factor $c<10\sqrt{5}-21\approx1.36$ the minimum number of arcs which has to be removed to guarantee d(s,t)≥d. Finally, we also show that the same inapproximability bounds hold for undirected graphs and/or node elimination.