Affordable Access

Publisher Website

A polynomial formulation for the stochastic maximum weight forest problem

Authors
Journal
Electronic Notes in Discrete Mathematics
1571-0653
Publisher
Elsevier
Publication Date
Volume
41
Identifiers
DOI: 10.1016/j.endm.2013.05.072
Keywords
  • Compact Formulation
  • Stochastic Maximum Weight Forest Problem
Disciplines
  • Mathematics

Abstract

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.

There are no comments yet on this publication. Be the first to share your thoughts.