No description, website, or topics provided.
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
instances
results
solver
.gitignore
LICENSE
README.md

README.md

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

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.