Composition of Near-Planar Infrastructure Network Instances with Certified Skewness Bounds

Computational studies of optimization problems on infrastructure networks may require more suitable instances than are available. We propose a method to obtain additional instances by extracting and joining connected parts of existing networks, reusing their topology and parameters. Many infrastructure networks are near-planar, so added connections should preserve this property. We measure near-planarity by skewness, … Read more

Fourth-order Marginal Moment Model: Reformulations and Applications

This paper investigates the bounds on the expectation of combinatorial optimization given moment information for each individual random variable. A popular approach to solving this problem, known as the marginal moment model (MMM), is to reformulate it as a semidefinite program (SDP). In this paper, we investigate the structure of MMM with up to fourth-order … Read more