A Polynomial Formulation for the Stochastic Maximum Weight Forest Problem

Let G=(V, ED?ES) be a non directed graph with set of nodes V and set of weighted edges ED?ES. The edges in ED and ES have deterministic and uncertain weights, respectively, with ED?ES=?. Let S={1, 2, ?, P} be a given set of scenarios for the uncertain weights of the edges in ES. The stochastic maximum weight forest (SMWF) problem consists in determining a forest of G, one for each scenario s?S, sharing the same deterministic edges and maximizing the sum of the deterministic weights plus the expected weight over all scenarios associated with the uncertain edges. In this work we present two formulations for this problem. The first model has an exponential number of constraints, while the second one is a new compact extended formulation based on a new theorem characterizing forests in graphs. We give a proof of the correctness of the new formulation. It generalizes existing related models from the literature for the spanning tree polytope. Preliminary results evidence that the SMWF problem can be NP-hard. © 2013 Elsevier B.V.