Laboratoire d’Analyse et d’Architecture des Systèmes
The maximum weight forest problem (MWFP) in a graph is solved by the famous greedy algorithm due to Edmonds (1971) where every edge has a known weight. In particular, the system of constraints on the set of edges is TDI (totally dual integral), since the set of independent edges, i.e., acyclic subsets of edges, is a matroïd. We extend this approach to the case of two-stage stochastic maximum weight forest problem. The set of edges is composed of first stage edges with known weights and second stage edges where the weights are random variables with discrete distribution. In this case, we transform the stochastic problem into a deterministic equivalent problem. In this talk, we prove TDIness for the two stage maximum weight forest problem in the case of two scenarios. We provide a counter example to prove that the problem is not TDI for more than two scenarios.