preprocessing

Reduction Tests for the Prize-Collecting Steiner Problem

  • Eduardo Uchoa
    • Categories Applications - OR and Management Sciences, Integer Programming, Telecommunications Tags , ,

    The Prize-Collecting Steiner Problem (PCSP) is a generalization of the classical Steiner Problem in Graphs (SPG) where instead of terminal vertices that must be necessarily connected, one have profits associated to the vertices that must be balanced against the connection costs. This problem is gaining much attention in the last years due to its practical … Read more

    Preprocessing sparse semidefinite programs via matrix completion

  • Katsuki Fujisawa
  • Mituhiro Fukuda
  • Kazuhide Nakata
    • Categories Semi-definite Programming Tags , , , , ,

    Considering that preprocessing is an important phase in linear programming, it should be systematically more incorporated in semidefinite programming solvers. The conversion method proposed by the authors (SIAM Journal on Optimization, vol.~11, pp.~647–674, 2000, and Mathematical Programming, Series B, vol.~95, pp.~303–327, 2003) is a preprocessing of sparse semidefinite programs based on matrix completion. This article … Read more