Browsing by Author "Triki, C."

Filter results by typing the first few letters
Now showing 1 - 3 of 3
  • Placeholder
    ArticlePublicationMetadata only
    A branch-and-cut algorithm for the Steiner tree problem with delays
    (Springer Science+Business Media, 2012-12) Leggieri, V.; Haouari, Mohamed; Triki, C.; Industrial Engineering; HAOUARI, Mohamed
    In this paper, we investigate the Steiner tree problem with delays, which is a generalized version of the Steiner tree problem applied to multicast routing. For this challenging combinatorial optimization problem, we present an enhanced directed cut-based MIP formulation and an exact solution method based on a branch-and-cut approach. Our computational study reveals that the proposed approach can optimally solve hard dense instances.
  • Placeholder
    Conference ObjectPublicationMetadata only
    An exact algorithm for the Steiner tree problem with delays
    (Elsevier, 2010-08-01) Leggieri, V.; Haouari, Mohamed; Triki, C.; Industrial Engineering; HAOUARI, Mohamed
    The Steiner Tree Problem with Delays (STPD) is a variant of the well-known Steiner Tree Problem in which the delay on each path between a source node and a terminal node is limited by a given maximum value. We propose a Branch-and-Cut algorithm for solving this problem using a formulation based on lifted Miller-Tucker-Zemlin subtour elimination constraints. The effectiveness of the proposed algorithm is assessed through computational experiments carried out on dense benchmark instances.
  • Placeholder
    ArticlePublicationMetadata only
    The Steiner tree problem with delays: a compact formulation and reduction procedures
    (Elsevier, 2014-02-19) Leggieri, V.; Haouari, Mohamed; Triki, C.; Industrial Engineering; HAOUARI, Mohamed
    This paper investigates the Steiner Tree Problem with Delays (STPD), a variation of the classical Steiner Tree problem that arises in multicast routing. We propose an exact solution approach that is based on a polynomial-size formulation for this challenging NP-hard problem. The LP relaxation of this formulation is enhanced through the derivation of new lifted Miller Tucker Zemlin subtour elimination constraints. Furthermore, we present several preprocessing techniques for both reducing the problem size and tightening the LP relaxation. Finally, we report the results of extensive computational experiments on instances with up to 1000 nodes. These results attest to the efficacy of the combination of the enhanced formulation and reduction techniques.