Given a graph with nonnegative edge weights and node pairs Q, we study the problem of constructing minimum weight set edges so that induced subgraph contains at least K edge-disjoint paths containing most L between each pair in Q. Using layered representation introduced by Gouveia [Gouveia, L. 1998. variable redefinition for computing lower bounds spanning Steiner trees hop constraints. INFORMS J. Comput. 10(2) 180–188], present formulation valid any K, ≥ 1. We use Benders decomposition...

Abstract We formulate and computationally test several models for the Diameter‐Constrained Minimum Spanning Steiner Tree Problems, which seek a least‐cost spanning or tree subject to (diameter) bound imposed on number of edges in between any node pair. A traditional multicommodity flow model with commodity every pair nodes was unable solve 20‐node 100‐edge problem after 1 week computation. In contrast, new were able optimality this less than second larger instances up 100 1000 edges. The...

In this paper we present a new formulation for the Capacitated Minimal Spanning Tree (CMST) problem. One advantage of is that it more compact (in number constraints) than well-known formulation. Additionally, show linear programming relaxation both formulations produces optimal solutions with same cost. We brief discussion concerning valid inequalities which are directly derived from some not dominated by sets facet-inducing (CMST). derive Lagrangian relaxation-based methods and...

We use variable redefinition (see R. Martin, 1987. Generating Alternative Mixed-Integer Programming Models Using Variable Redefinition, Operations Research 35, 820–831) to strengthen a multicommodity flow (MCF) model for minimum spanning and Steiner trees with hop constraints between root node any other node. Hop quality of service constraints. The Lagrangean dual value associated one relaxation derived from the MCF formulation dominates corresponding LP value. However, lower bounds given...

MPLS (multiprotocol label switching) over WDM (wavelength division multiplexing) networks are gaining significant attention due to the efficiency in resource utilization that can be achieved by jointly considering two network layers. This paper addresses design of networks, where some nodes may not have packet switching capabilities. Given topology and offered traffic matrix, which includes location edge LSRs (label switched routers), we determine core (i.e. also need include capabilities)...

In this paper, we present a new formulation for the Time-Dependent Traveling Salesman Problem (TDTSP). We start by reviewing well known natural formulations with some emphasis on Picard and Queyranne (1978) [22]. The main feature of is that it uses, as subproblem, an exact description n-circuit problem. Then, uses more variables based using, each node, stronger namely subproblem additional constraint corresponding node not repeated in circuit. Although model has constraints than original PQ...

This paper studies the behavior of compact formulations for solving maximum edge-weight clique (MEWC) problem in sparse graphs. The MEWC has long been discussed literature, but mostly addressing complete graphs, with or without a cardinality constraint on clique. Yet, several real-world applications are defined where missing edges due to some threshold process because they not even supposed be graph, at all. Such situations often arise cell's metabolic networks, amount metabolites shared...