Article ID Journal Published Year Pages File Type
4651758 Electronic Notes in Discrete Mathematics 2013 8 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics