Convex Optimization for Binary Tree-Based Transport Networks

Raoul Sallé de Chou, Mohamed Ali Srir, Laurent Najman, Nicolas Passat, Hugues Talbot, Irene E. Vignon-Clementel

Abstract

Generating realistic synthetic vascular networks is a critical step in developing medical "numerical twins" for non-invasive blood flow simulation. Traditional methods, such as Constrained Constructive Optimization (CCO), rely on local, volume-based heuristics that are often computationally expensive and mathematically unstable. This paper introduces a novel framework that shifts from local volume minimization to a global, convex energy-based optimization. By leveraging Murray’s Law, the proposed method achieves a significant reduction in total vascular volume and computational time while ensuring mathematical robustness.

Introduction

The creation of digital models of blood vessel trees is essential for diagnosing cardiovascular diseases and planning surgical interventions. The standard approach, Constrained Constructive Optimization (CCO), builds these trees incrementally by adding branches one by one. However, CCO faces two primary challenges: sub-optimality and mathematical instability. Because CCO optimizes branch positions locally, it often fails to reach a globally efficient network configuration. Furthermore, the traditional volume-based cost functions are frequently "ill-posed," requiring complex, iterative solvers that do not guarantee a true minimum.

To address these issues, this research proposes a mathematically robust, global optimization framework that replaces local heuristics with a convex energy function. This approach not only improves the efficiency of the resulting networks but also streamlines the computational process.

Methodology

The core innovation of this work lies in the transition from volume-based costs to an energy-based cost function derived from Murray’s Law. Murray’s Law posits that the cube of a vessel's radius is proportional to its flow rate, providing a biological basis for efficient transport.

The Energy Function

The authors define the network's cost as the sum of viscous work (the energy required to push fluid through the vessels) and metabolic cost (the energy required to maintain the blood volume). By substituting flow-radius relationships into this equation, the authors demonstrate that the cost function becomes convex with respect to the coordinates of the branching points. In the field of optimization, convexity is highly desirable because it ensures that any local minimum found by an algorithm is also the global minimum, eliminating the need for the "hacks" required by previous non-linear solvers.

Two-Step Optimization

The framework utilizes a two-step process:

  1. Incremental Growth: A local optimization is applied as the tree is built branch-by-branch.
  2. Global Refinement: Once the tree connectivity is established, a Global Optimization Algorithm adjusts all bifurcation points simultaneously. This "global shake" ensures the network reaches the absolute lowest energy state for its specific topology.

Experimental Setup

The researchers benchmarked the new energy-based method against the classical volume-based CCO using synthetic datasets. They generated 10 distinct trees for four different sizes: 100, 200, 300, and 400 terminal nodes. All simulations were conducted within a standardized 2D circular perfusion territory to maintain consistency across comparisons.

Key Results and Discussion

The shift to a convex energy-based framework yielded significant improvements across several metrics:

  • Computational Efficiency: The energy-based method proved to be significantly faster, reducing computational time by an average of 31.7% to 36.3% compared to traditional volume-based CCO. This is largely due to the well-posed nature of the convex problem.
  • Volume Reduction: Surprisingly, focusing on energy minimization resulted in more volume-efficient trees than those specifically designed to minimize volume. The new method produced trees with approximately 36% less total volume than traditional CCO.
  • Impact of Global Refinement: The global optimization step proved highly effective, further reducing the total vascular volume by an average of 7.7% to 7.9% for larger networks (200+ nodes).
  • Morphological Realism: Despite the mathematical changes, the resulting synthetic trees maintained realistic biological characteristics, including appropriate asymmetry and complex branching depths of up to 46 bifurcation levels.

Conclusion

This research demonstrates that a global, convex optimization framework based on energy minimization is superior to traditional local volume-based heuristics for generating synthetic vascular networks. The method is faster, more robust, and produces more efficient transport structures.

Future work will focus on extending these 2D simulations into 3D organ-specific geometries and validating the synthetic models against real-world medical imaging data. Additionally, the authors suggest exploring topology optimization—adjusting the connectivity of the tree itself—to further enhance the realism and efficiency of these numerical twins.

Summary updated

Abstract

Optimizing transport networks is a well-known class of problems that have been extensively studied, with application in many domains. Here we are interested in a generalization of the Steiner problem, which entails finding a graph minimizing a cost function associated with connecting a given set of points. In this paper, we concentrate on a specific formulation of this problem which is applied to the generation of synthetic vascular trees. More precisely, we focus on the Constrained Constructive Optimization (CCO) tree algorithm, which constructs a vascular network iteratively, optimizing a blood transport energy efficiency. We show that the classical incremental construction method often leads to sub-optimal results, and that a better global solution can be reached.
BibTeX
@inproceedings{chou2024convex,
  author = {Raoul Sallé de Chou and Mohamed Ali Srir and Laurent Najman and Nicolas Passat and Hugues Talbot and Irene E. Vignon-Clementel},
  title = {{Convex Optimization for Binary Tree-Based Transport Networks}},
  booktitle = {DGMM},
  year = {2024},
  doi = {10.1007/978-3-031-57793-2\_17},
}
Figure