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 marginal moments and reformulate them as second-order cone programs (SOCP). Additionally, we establish that this SOCP formulation is equivalent to a convex optimization problem over the convex hull of the feasible region of the original combinatorial optimization, presenting closed-form expressions for both the objective function and its derivative. These reformulations enable more efficient computation of the bounds and persistency value. In addition, we explore two types of ambiguity sets characterized by incomplete moment information. We further discuss the relationship between the aforementioned MMMs and another widely-used model, the marginal distribution model (MDM). Beyond bounding the worst-case expectations, our approaches can be modified to bound the worst-case conditional value at risk (CVaR) of the combinatorial optimization.
Building on this theoretical advancement, we explore two applications. First, we consider the project crashing problem, wherein both the means and variances of activity durations can be controlled through effort. We demonstrate that the distributionally robust project crashing problem, incorporating up to fourth-order moment information, can be reformulated as either an SOCP or a convex minimization over a simple polytope. Numerical analysis reveals that MMM with fourth moment information yields tighter bounds on expected delays and requires a significantly smaller budget than the mean-variance model for a fixed delay guarantee. Second, we apply our reformulations to solve the distributionally robust newsvendor problem with moment information, extending the well-known Scarf's model. We derive several new closed-form solutions and explore how the optimal order quantities depend on skewness and kurtosis. Numerically, we show that incorporating additional moment information can lead to better performance, especially in the high service level regime.
Article
View Fourth-order Marginal Moment Model: Reformulations and Applications