dapcstp

A solver for the prize-collecting Steiner tree and related problems.

A Dual Ascent-Based Branch-and-Bound Framework for the Prize-Collecting Steiner Tree and Related Problems
Markus Leitner, Ivana Ljubić, Martin Luipersbeck, and Markus Sinnl
INFORMS Journal on Computing 201830:2 , 402-420

The article can be downloaded here, the benchmark instances here.

Dependencies

• Boost C++ Libraries

Usage

• Build using make.
• Example usage (solve instance file 'instance.pcstp' of type 'prize-collecting Steiner tree problem' and write the solution to file 'instance.sol'):

  ./dapcstp instance.pcstp --type pcstp -o instance.sol

• Display all available options:

  ./dapcstp -h

• Supported problem types:
  • Prize-collecting Steiner tree problem (pcstp) - default
  • Maximum-weight connected subgraph problem (mwcs)
  • Node-weighted Steiner tree problem (nwstp)
  • Steiner tree problem (stp)

License

This project is licensed under the AGPL - see the LICENSE file for details.