A New Relaxation for Tree-Based Problems and Minimum Power-Cost Spanning Trees

Luzie Marianczuk, Ernst Althaus, Stefan Irnich, Marc E. PfetschSEA 2025 · DOI

TL;DR

This paper introduces a novel dynamic programming framework, "ng-arbs," to derive tighter lower bounds for tree-based optimization problems, particularly the Minimum Power-Cost Spanning Tree (MPCST). By generalizing existing "q-route" relaxations to "q-arbs" and then strengthening them with "ng-route" ideas, the authors achieve significantly better bounds than traditional LP relaxations, leading to more efficient exact algorithms.

What Problem Does This Paper Address?

Many NP-hard combinatorial optimization problems, like the Traveling Salesperson Problem (TSP) or Minimum Spanning Tree (MST), become significantly harder when side constraints are added. A common approach to tackle these problems is using branch-and-bound algorithms, which rely heavily on strong lower bounds to prune the search space effectively. However, for constrained versions of problems like MST, traditional linear programming (LP) relaxations often yield weak bounds, limiting the scalability of exact algorithms. This paper addresses this by developing a new, more powerful relaxation technique for tree-based problems, aiming to provide tighter lower bounds and thus improve the performance of exact solvers.

Methods

The core contribution is the development of a generalized "ng-arb" relaxation for arborescences, which are directed trees. This approach builds upon existing work on "q-routes" for vehicle routing problems (VRPs) and extends them to tree structures. The authors introduce the concept of "ng-arbs," which are arborescences that satisfy certain "ng-feasibility" conditions. These conditions are derived from a notion of "memory" associated with paths, preventing certain cycles and ensuring tighter bounds.

The paper then formalizes a dynamic programming (DP) framework for computing these ng-arb relaxations. This DP leverages equivalence classes of arborescences to avoid redundant computations. The authors define specific equivalence relations and attributes tailored for tree optimization problems, including the Minimum Power-Cost Spanning Tree (MPCST). For the MPCST, they propose a novel incremental recursive formulation that allows for the application of their DP approach.

Datasets

The authors evaluated their approach on randomly generated graph instances. These instances consist of vertices sampled uniformly on a 10000x10000 grid, with arc costs computed as Euclidean distances raised to the power of 4. This setup is in line with instances used in prior work on MPCST. The paper does not introduce new benchmark datasets.

Key Insights and Ideas

  • Generalizing VRP relaxations to trees: The paper successfully adapts the powerful "q-route" relaxation concept from VRPs to tree structures, creating "q-arbs" and then "ng-arbs." This demonstrates a fruitful cross-pollination of ideas between different problem domains.
  • "Memory" for tighter bounds: The "ng-feasibility" condition, which incorporates a notion of memory for paths, is key to achieving stronger relaxations. This memory prevents certain types of cycles that would otherwise weaken the bounds.
  • Dynamic programming with equivalence classes: The proposed DP framework effectively manages the complexity of arborescences by grouping them into equivalence classes. This is crucial for making the computation tractable.
  • MPCST as a prime application: The Minimum Power-Cost Spanning Tree problem, known for its challenging nature and lack of simple optimal substructure, serves as a strong test case. The authors show their method provides better bounds than existing LP-based approaches for MPCST.

Key Results

The paper demonstrates empirically that the ng-arb relaxation provides significantly tighter lower bounds for the Minimum Power-Cost Spanning Tree (MPCST) problem compared to traditional LP-based bounds. While specific numerical improvements are presented in Table 1 (e.g., "Harb" values are consistently higher than "µLP" values, indicating better bounds), the key takeaway is that the ng-arb bounds are often superior. The authors also note that their approach leads to a more efficient dynamic programming formulation by reducing the number of states to consider.

Limitations and Future Work

The authors acknowledge that their current implementation does not employ dominance rules to eliminate redundant intermediate solutions, which could further reduce the size of the dynamic programming table. They suggest that improving the dynamic programming by incorporating such techniques, as well as exploring additional relaxation-strengthening methods like adaptive neighborhood extension and Lagrangian penalties, could lead to even better bounds. The paper also mentions that the code for implementation is made available, encouraging further research and application of their framework.

Summary updated

BibTeX
@inproceedings{marianczuk2025new,
  author = {Luzie Marianczuk and Ernst Althaus and Stefan Irnich and Marc E. Pfetsch},
  title = {{A New Relaxation for Tree-Based Problems and Minimum Power-Cost Spanning Trees}},
  booktitle = {SEA},
  year = {2025},
  doi = {10.4230/lipics.sea.2025.24},
}
Figure