Compact Models to Solve the Precedence-Constrained Minimum-Cost Arborescence Problem with Waiting Times

Abstract

The minimum-cost arborescence problem is a well-studied problem. Polynomial-time algorithms for solving it exist. Recently, a new variation of the problem called the Precedence-Constrained Minimum-Cost Arborescence Problem with Waiting Times was presented and proven to be NP-hard. In this work, we propose new polynomial-size models for the problem that are considerably smaller in size compared to those previously proposed. We experimentally evaluate and compare each new model in terms of computation time and quality of the solutions. Several improvements to the best-known upper and lower bounds of optimal solution costs emerge from the study.

Keywords

• arborescences
• precedence constraints
• mixed integer linear programming
• constraint programming