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.