Abstract In this paper, we introduce, study and analyze several classes of compact formulations for the symmetric Hamiltonian ‐median problem (HMP). Given a positive integer and a weighted complete undirected graph with weights on the edges, the HMP on is to find a minimum weight set of elementary cycles partitioning the vertices of . The advantage of developing compact formulations is that they can be readily used in combination with off‐the‐shelf optimization software, unlike other types of formulations possibly involving the use of exponentially sized sets of variables or constraints. The main part of the paper focuses on compact formulations for eliminating solutions with less than cycles. Such formulations are less well known and studied than formulations which prevent solutions with more than cycles. The proposed formulations are based on a common motivation, that is, the formulations contain variables that assign labels to nodes, and prevent less than cycles by stating that different depots must have different labels and that nodes in the same cycle must have the same label. We introduce and study aggregated formulations (which consider integer variables that represent the label of the node) and disaggregated formulations (which consider binary variables that assign each node to a given label). The aggregated models are new. The disaggregated formulations are not, although in all of them new enhancements have been included to make them more competitive with the aggregated models. The two main conclusions of this study are: (i) in the context of compact formulations, it is worth looking at the models with integer node variables, which have a smaller size. Despite their weaker LP relaxation bounds, the fewer variables and constraints lead to faster integer resolution, especially when solving instances with more than 50 nodes; (ii) the best of our compact models exhibit a performance that, overall, is comparable to that of the best methods known for the HMP (including branch‐and‐cut algorithms), solving to optimality instances with up to 226 nodes within 1 h. This corroborates our message that the knowledge of the inequalities for preventing less than cycles is much less well understood.

Abstract In this article, we study the multi‐depot family traveling salesman problem (MDFTSP) and two clustered variants, the soft‐clustered MDFTSP (SC‐MDFTSP) and the hard‐clustered MDFTSP. We emphasize the relevance of this study by relating the problems with warehouse activities supported by scattered storage systems and by pointing out that clustered variants of routing problems have been scarcely addressed in the literature. For these three problems, we present several mixed integer linear programming formulations and develop appropriate branch‐&‐cut based algorithms which are tested with a newly generated data set including instances with up to 200 nodes and 40 depots. The results from the computational experiments allow us to identify the main differences between the three problems concerning modeling approaches as well as solution methods and put in evidence that these problems are challenging problems, in particular the SC‐MDFTSP.

Abstract We study the relation between the linear programming relaxation of two classes of models for the Steiner tree problem with hop constraints. One class is characterized by having hop‐indexed arc variables. Although such models have proved to have a very strong linear programming bound, they are not easy to use because of the huge number of variables. This has motivated some studies with models involving fewer variables that use, instead of the hop‐indexed arc variables, hop‐indexed node variables. In this article, we contextualize the linear programming relaxation of these node‐based models in terms of the linear programming relaxation of known arc‐based models. We show that the linear programming relaxation of a general node‐based model is implied by the linear programming relaxation of a straightforward arc‐based model.

Special issue on network analytics

This special issue of Networks is dedicated to the 8th International Network Optimization Conference INOC 2017, held at the Faculty of Sciences, University of Lisbon, Portugal, on February 26–28, 2017 and was organized in collaboration with the Center for Mathematics, Fundamental Applications and Operations Research (CMAFcIO). The aim of this conference was to provide researchers from different areas of Operations Research, with the opportunity to present and discuss their results and research on the field of Network Optimization, in an inspiring and bridge building environment where fruitful ideas may flow freely. INOC conferences are organized biannually by the European Network Optimization Group (ENOG), a working group of EURO. The event alternates with the INFORMS Telecommunications Network Optimization Conference. INOC 2017 is the 8th edition of this event and the second to take place in Portugal. Previous editions were held in Warsaw (Poland), organized by Michał Pióro in 2015, Tenerife (Spain), organized by Juan-José Salazar-Gonzalez in 2013, Hamburg (Germany), organized by Stefan Voß in 2011, Pisa (Italy), organized by Maria Grazia Scutellà in 2009, Spa (Belgium), organized by Bernard Fortz in 2007, Lisbon (Portugal), organized by Luis Gouveia in 2005, and Evry-Paris (France), organized by Walid Ben-Ameur in 2003. As before, the event attracted great interest from the network optimization community, with a substantial number of participants from several countries. The high scientific level conference program included four plenary talks given by internationally recognized invited experts: Prof. Alexander Martin, Prof. Alexander Schrijver, Prof. Rolf Möhring, and Prof. William Cook. The program included 90 presentations divided into 26 technical sessions, based on 38 papers and 52 extended abstracts selected from 112 submissions (54 papers and 58 extended abstracts). Thirty-seven papers are available in Electronic Notes in Discrete Mathematics (Volume 64, 2018). The INOC 2017 conference was chaired by Luís Gouveia and Pedro Moura, Faculty of Sciences, University of Lisbon, Portugal. At the conclusion of INOC 2017, 12 extended papers were submitted for publication in this journal; of these, seven were accepted and appear in this special issue. The final contents of the issue are as presented next. Agra et al. 2 consider a stochastic single item production-inventory-routing problem with a single producer, multiple clients, and multiple vehicles. Demands are considered uncertain and are allowed to be backlogged incurring a penalty cost. A recourse model is presented where the production and routing decisions are taken before the scenario is known, and the quantities to deliver to the clients and the inventory levels are adjustable to the scenario. Valid inequalities are introduced to enhance the model. As the problem is very complex, following the sample average approximation (SAA) method, several small size samples are generated. Two main approaches, a static and an adjustable version, are tested. Different heuristic algorithms based on the mathematical model are tested within each approach. Computational tests based on randomly generated instances are conducted to test the different approaches. The results show that the new adjustable SAA heuristic performs better than the static one for hard instances. Büsing and Comis 3 study a version of the Weighted Matching problem, the multi-Budgeted Matching problem (mBM) with k independent edge cost functions. For each cost function, a budget constraint requires the accumulated cost not to exceed a corresponding budget. The authors show that the mBM is strongly NP-hard on paths with uniform edge weights and budgets by a reduction from 3-SAT. A dynamic program for series-parallel graphs with pseudo-polynomial run time for a fixed number of budget constraints is proposed. This algorithm is presented for solving the mBM on trees using a graph transformation. These results motivated the authors to show how dynamic programming on tree decompositions leads to a pseudo-polynomial algorithm for the mBM with fixed k on the much more general class of graphs with bounded tree width. Fischetti and Pisinger 4 address the optimization of cable connections between turbines in an offshore wind park. Since turbines are becoming still more customized, it is important to be able to evaluate the impact of new technologies with a flexible optimization tool. Following previous studies, in the present paper, the authors address new features that have been recently proposed by experts from Vattenfall BA Wind (a global leader in energy production). The authors show how some new features can effectively be modeled and solved using a mixed-integer linear programming paradigm. Computational results on the performance of the new models on a set of real-world instances provided by Vattenfall are given and discussed. Gugat et al. 1 propose a decomposition-based method for solving mixed-integer nonlinear optimization problems with “black-box” nonlinearities. The method alternatingly solves a mixed-integer linear master problem and a separation problem for iteratively refining the mixed-integer linear relaxation of the nonlinear equalities. Under some assumptions, the authors prove that the algorithm finitely terminates with a global optimal solution of the mixed-integer nonlinear problem. Applicability of the proposed approach was shown for three applications from optimal control with integer variables, from the field of pressurized flows in pipes with elastic walls, and from steady-state gas transport. For the latter, promising numerical results of the method are obtained from real-world instances that particularly show the effectiveness of the method for problems defined on networks. Raith et al. 7 consider multi-objective shortest path problems in which the edge lengths are uncertain. Different concepts for finding so-called robust efficient solutions for multi-objective robust optimization exist. This paper considers and studies multi-scenario efficiency, flimsily and highly robust efficiency, and point-based and set-based minmax robust efficiency. Although an important class of algorithms for multi-objective (deterministic) shortest path problems are labeling algorithms, the authors analyze why it is, for many of the considered concepts, not straightforward to use labeling algorithms to find robust efficient solutions. Two approaches to extend a generic multi-objective label correcting algorithm for such cases are presented and tested numerically. Sagnol et al. 6 introduce the concept of the cone K of flow matrices. The authors show that several hard flow (or path) optimization problems that cannot be solved by using the standard arc-representation of a flow, reduce to a linear optimization problem over the cone K. The authors prove that the membership problem associated to K is NP-complete and provide two convergent approximation hierarchies, one of them based on a completely positive representation of K. This approach is illustrated by computing bounds for the quadratic shortest path problem, as well as a maximum flow problem with pairwise arc-capacities. Silva et al. 5 develop and evaluate an alternative routing scheme for the Robust Network Loading problem with demand uncertainty. The scheme, denoted by named k-adaptive, is based on the fact that the decision-maker chooses k second-stage solutions and then commits to one of them only after realization of the uncertainty. This routing scheme, with its corresponding k-partition of the uncertainty set, is dynamically defined under an iterative method to sequentially improve the solution. Results from the k-adaptive scheme are compared with the ones obtained through other routing schemes. The effectiveness of the method is verified by using several realistic networks from SNDlib. We thank the authors for submitting these high-quality papers and the referees for their excellent reviews. On behalf of the Organizing Committee of INOC 2017, we also thank all the people who helped to organize this conference. The support of the University of Lisbon, CMAFcIO (Center for Mathematics, Fundamental Applications and Operations Research), from Portugal and EURO (Association of European Operational Research Societies) has contributed significantly to the success of the event. Luis Gouveia and Pedro Moura Guest Editors

There are many ways of modeling the Asymmetric Traveling Salesman Problem (ATSP) and the related Precedence Constrained ATSP (PCATSP). In this paper we present new formulations for the two problems that result from combining precedence variable based formulations with network flow based formulations. The motivation for this work is a property of the so‐called GDDL inequalities (Gouveia and Pesneau, Networks 48, 77–89, 2006), the “disjoint sub‐paths” property, that is explored to create formulations that combine two (or more) disjoint path network flow based formulations. Several sets of projected inequalities, in the space of the arc and precedence variables, and in the spirit of many inequalities presented in Gouveia and Pesneau (Networks 48, 77–89, 2006), are obtained by projecting these network flow based formulations. Computational results are given for the PCATSP and the ATSP to evaluate the quality of the new inequalities. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 71(4), 451–465 2018

Multi‐depot routing problems arise in distribution logistics where a set of vehicles based at several depots are used to serve a number of clients. Most variants of this problem have the basic requirement that the route of each vehicle starts and ends at the same depot. This article describes new inequalities, namely multi‐cut constraints (MCC), which enforce this requirement in mathematical programming formulations of multi‐depot routing problems. The MCCs are exponential in size, and are equivalent to a compact three‐index formulation for the problem in terms of the associated linear programming relaxations. The article describes how a generalization of the MCCs can be obtained, in a similar manner, by using a stronger version of the three‐index formulation. The connection between the compact and the exponential formulations implies a separation procedure based on max‐flow/min‐cut computations, which has reduced complexity in comparison with a previously known set of constraints described for the same purpose. The new inequalities are used in a branch‐and‐cut algorithm. Computational results are presented for instances with up to 300 clients and 60 depots. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 70(3), 246–261 2017

In this article, we study the k-edge-connected L-hop-constrained network design problem. Given a weighted graph , a set D of pairs of nodes, two integers and , the problem consists in finding a minimum weight subgraph of G containing at least k edge-disjoint paths of length at most L between every pair . We consider the problem in the case where L = 2, 3 and . We first discuss integer programming formulations introduced in the literature. Then, we introduce new integer programming formulations for the problem that are based on the transformation of the initial undirected graph into directed layered graphs. We present a theoretical comparison of these formulations in terms of LP-bound. Finally, these formulations are tested using CPLEX and compared in a computational study for k = 3, 4, 5. © 2015 Wiley Periodicals, Inc. NETWORKS, 67(2), 148–169 2016

The Hamiltonian p‐median problem consists of determining p disjoint cycles of minimum total cost covering all vertices of a graph. We present several new and existing models for this problem, provide a hierarchy with respect to the quality of the lower bounds yielded by their linear programming relaxations, and compare their computational performance on a set of benchmark instances. We conclude that three of the models are superior from a computational point of view, two of which are introduced in this article. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 63(4), 350–363 2014

Given a graph with nonnegative edge weights and node pairs Q, we study the problem of constructing a minimum weight set of edges so that the induced subgraph contains at least K edge-disjoint paths containing at most L edges between each pair in Q. Using the layered representation introduced by Gouveia [Gouveia, L. 1998. Using variable redefinition for computing lower bounds for minimum spanning and Steiner trees with hop constraints. INFORMS J. Comput. 10(2) 180–188], we present a formulation for the problem valid for any K, L ≥ 1. We use a Benders decomposition method to efficiently handle the large number of variables and constraints. We show that our Benders cuts contain constraints used in previous studies to formulate the problem for L = 2, 3, 4, as well as new inequalities when L ≥ 5. Whereas some recent works on Benders decomposition study the impact of the normalization constraint in the dual subproblem, we focus here on when to generate the Benders cuts. We present a thorough computational study of various branch-and-cut algorithms on a large set of instances including the real-based instances from SNDlib. Our best branch-and-cut algorithm combined with an efficient heuristic is able to solve the instances significantly faster than CPLEX 12 on the extended formulation.

Abstract This article analyzes inequalities derived by projecting out the flow variables of a single‐commodity flow model for a vehicle routing problem. These inequalities are called reverse multistar (RMS) inequalities and are related to the MS inequalities analyzed and used in other articles. Although the MS RMS inequalities are irrelevant for some vehicle routing problems, in others they are fundamental. The article presents a vehicle routing problem in which the RMS are of interest. It is called the vehicle routing problem with lower and upper bound capacities (LU‐VRP). It concerns a vehicle routing problem with one depot and a homogeneous fleet of vehicles. All the customers have a unit demand, and there are upper and lower bounds on the demand covered by each vehicle. New families of inequalities are derived by strengthening the RMS inequalities. Computational experiments show that the new inequalities are useful when solving LU‐VRP instances. The experiments are based on variations of symmetric and asymmetric VRP library (VRPLIB) instances with up to 100 customers. The constraint on a minimum number of customers served in each route is implicit in the unit‐demand capacitated vehicle routing problem with a fixed number of vehicles. Therefore, the article also evaluates the impact of using the lower bound inequalities developed in the context of this variant. It is still unknown whether the new inequalities can help solve it or not. Our theoretical analysis suggests that one of the families of developed inequalities is not implied by other standard inequalities. This prompts us to pursue studies in the search for other families of lower bound based inequalities for this variant. © 2012 Wiley Periodicals, Inc. NETWORKS, 2013

Abstract The k ‐Degree constrained Minimum Spanning Tree Problem (k ‐DMSTP) consists in finding a minimal cost spanning tree satisfying the condition that every node has a degree no greater than a fixed value k. Here we consider an extension where besides the edge costs, a concave cost function is associated to the degree of each node. Several integer linear programming formulations based on reformulation techniques are presented and their linear programming relaxations are compared. A GRASP heuristic to obtain feasible solutions for the problem together with a Path Relinking strategy is also described. We include computational results using instances with up to 200 nodes that give an empirical assessment of the linear programming bounds of the different models as well as the ability of using these models to solve the problems by using an Integer Linear Programming package. The results also show that the proposed GRASP heuristic appears to perform rather well for this type of problems. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012

Abstract In this article, we consider the notion of “reload costs” in network design. Reload costs occur naturally in many different settings including telecommunication networks using diverse technologies. However, reload costs have not been studied extensively in the literature. Given that reload costs occur naturally in many settings, we are motivated by the desire to develop “good” models for network design problems involving reload costs. In this article, and as a first step in this direction, we propose and discuss the reload cost spanning tree problem (RCSTP). We show that the RCSTP is NP‐complete. We discuss several ways of modeling network design problems with reload costs. These involve models that expand the original graph significantly—to a directed line graph and a colored graph—to model reload costs. We show that the different modeling approaches lead to models with the same linear programming bound. We then discuss several variations of reload cost spanning tree and network design problems, and discuss both their complexity and models for these variations. To assess the effectiveness of the proposed models to solve RCSTP instances, we present results taken from instances with up to 50 nodes, 300 edges, and nine technologies for several variations of the problem. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011

info:eu-repo/semantics/published

Abstract The Minimum Arborescence problem (MAP) consists of finding a minimum cost arborescence in a directed graph. This problem is NP‐Hard and is a generalization of two well‐known problems: the Minimum Spanning Arborescence Problem (MSAP) and the Directed Node Weighted Steiner Tree Problem (DNWSTP). We start the model presentation in this paper by describing four models for the MSAP (including two new ones, using so called “connectivity” constraints which forbid disconnected components) and we then describe the changes induced on the polyhedral structure of the problem by the removal of the spanning property. Only two (the two new ones) of the four models for the MSAP remain valid when the spanning property is removed. We also describe a multicommodity flow reformulation for the MAP that differs from well‐known multicommodity flow reformulations in the sense that the flow conservation constraints at source and destination are replaced by inequalities. We show that the linear programming relaxation of this formulation is equivalent to the linear programming relaxation of the best of the two previous valid formulations and we also propose two Lagrangean relaxations based on the multicommodity flow reformulation. From the upper bound perspective, we describe a constructive heuristic as well as a local search procedure involving the concept of key path developed earlier for the Steiner Tree Problem. Numerical experiments taken from instances with up to 400 nodes are used to evaluate the proposed methods. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008

Abstract This report surveys the papers presented at the International Network Optimization Conference (INOC2005), held in Lisbon, Portugal, March 2005. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 48(1), 1–6 2006

Abstract In this article we study the use of formulations with precedence relation variables for the Precedence Constrained Asymmetric Travelling Salesman (PCATS) problem. Contrary to previous articles, the emphasis of this article is on formulations involving exponential sized sets of inequalities and on the development of a cutting plane method together with polynomial routines for separating the new inequalities. Our computational results, taken from a set of benchmark instances, show that our methods improve significantly on most of the best previously known lower bound values. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 48(2), 77–89 2006

Abstract This report highlights some recent contributions to network optimization based on papers presented at the first International Network Optimization Conference (INOC'2003) held in Evry‐Paris, France. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(1), 27–30 2004

Abstract In a previous article, using underlying graph theoretical properties, Gouveia and Magnanti (2003) described several network flow‐based formulations for diameter‐constrained tree problems. Their computational results showed that, even with several enhancements, models for situations when the tree diameter D is odd proved to be more difficult to solve than those when D is even. In this article we provide an alternative modeling approach for the situation when D is odd. The approach views the diameter‐constrained minimum spanning tree as being composed of a variant of a directed spanning tree (from an artificial root node) together with two constrained paths, a shortest and a longest path, from the root node to any node in the tree. We also show how to view the feasible set of the linear programming relaxation of the new formulation as the intersection of two integer polyhedra, a so‐called triangle‐tree polyhedron and a constrained path polyhedron. This characterization improves upon a model of Gouveia and Magnanti (2003) whose linear programming relaxation feasible set is the intersection of three rather than two integer polyhedra. The linear programming gaps for the tightened model are very small, typically less than 0.5%, and are usually one third to one tenth of the gaps of the best previous model described in Gouveia and Magnanti (2003). Moreover, using the new model, we have been able to solve large Euclidean problem instances that are not solvable by the previous approaches. © 2004 Wiley Periodicals, Inc.

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 the two network layers. This paper addresses the design of MPLS over WDM networks, where some of the WDM nodes may not have packet switching capabilities. Given the WDM network topology and the offered traffic matrix, which includes the location of the edge LSRs (label switched routers), we jointly determine the location of the core LSRs (i.e. the core WDM nodes that also need to include packet switching capabilities) and the lightpath routes (which are terminated on the LSRs) that minimize the total network cost. We consider constraints both at the optical and packet layers: an MPLS hop constraint on the maximum number of LSRs traversed by each LSP (label switched path), which guarantees a given packet level QoS, and a WDM path constraint on the maximum length of lightpaths, which accommodates the optical transmission impairments. A novel integer linear programming (ILP) formulation based on an hop-indexed approach, which we call the HOP model, is proposed. A two-phase heuristic, derived from a decomposition of the HOP model in two simpler ILP models that are solved sequentially, is also developed. The computational results show that the heuristic is efficient and produces good quality solutions, as assessed by the lower bounds computed from the HOP model. In some cases, the optimal solution is obtained with the branch-and-bound method.

Abstract We formulate and computationally test several models for the Diameter‐Constrained Minimum Spanning and Steiner Tree Problems, which seek a least‐cost spanning or Steiner tree subject to a (diameter) bound imposed on the number of edges in the tree between any node pair. A traditional multicommodity flow model with a commodity for every pair of nodes was unable to solve a 20‐node and 100‐edge spanning tree problem after 1 week of computation. In contrast, the new models were able to optimality solve this problem in less than 1 second and larger problem instances with up to 100 nodes and 1000 edges. The largest model contains more than 250,000 integer variables and more than 125,000 constraints. The new models simultaneously find a directed tree with a central node or a central edge that serve as a source for the commodities in a multicommodity flow model with hop constraints. Our results demonstrate the power of using single‐sourcing combined with other reformulation techniques: directing the model and using hop‐indexed formulations. Enhancements improve the models when the diameter bound is odd (these situations are more difficult to solve). The linear programming relaxation of the best formulations discussed in this paper always give an optimal integer solution for two special, polynomially solvable cases of the problem. © 2003 Wiley Periodicals, Inc.

Abstract The Capacitated Minimum Spanning Tree Problem seeks a least‐cost spanning tree subject to a bound imposed on the number of nodes in each subtree pending from a given root node. Araque et al. (Technical Report SOR‐90‐12, Princeton University, 1990) introduced several classes of facet‐defining inequalities for the undirected version of the problem, most of which have straightforward analogs to the directed version and are also facet‐defining in that case (see Zhang, Master's thesis, 1993). The multistar constraints are one such class. Gouveia [Telecommun Syst 1 (1993), 51–56] showed that a directed flow formulation gives a polynomial representation of the class of directed multistar constraints. This equivalence shows how to obtain a polynomial‐time separation algorithm for this class of inequalities. In this paper, we show that the previous equivalence result implies that we can also separate in polynomial time the exponential‐sized class of undirected multistar constraints. We also show that “using a directed model” plays a key role in obtaining a polynomial‐time separation algorithm for this class of inequalities, that is, using a directed flow model seems to be crucial for obtaining a polynomial‐time separation algorithm for the class of undirected multistar constraints. © 2002 Wiley Periodicals, Inc.

The Capacitated Minimum Spanning Tree Problem (CMSTP) is to find a minimum spanning tree subject to an additional constraint stating that the number of nodes in each subtree pending from a given root node is not greater than a given number Q. Gouveia and Martins (1996) proposed a hop-indexed flow model for the CMSTP. This formulation is a generalization of a well-known single-commodity flow model proposed by Gavish (1983). The linear programming (LP) bound of the new formulation has produced the best bounds for a set of tests (tests with the root in the corner of the grid of nodes) which have been characterized as hard by most of the available lower-bounding schemes. The deficiency of the new formulation is the range of variation of the extra hop index which leads to storage problems when instances with 80 nodes are tried. We propose several levels of aggregation of the original formulation, yielding a hierarchy of hop-indexed LP models with fewer variables than the original model and which are weaker than the LP relaxation of the original formulation but still stronger than the LP relaxation of the single-commodity flow model. This hierarchy suggests an iterative method for computing lower bounds for the CMSTP. It iteratively transforms a given model into a more disaggregated model with a tighter relaxation. Reduction tests performed in a given iteration can be used to eliminate variables from the models arising in later iterations. Computational results assessing the efficiency of the iterative method are reported. The results are taken from a set of benchmark instances with 41 and 81 nodes and two new instances with 121 nodes. © 2000 John Wiley & Sons, Inc.

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 a root node and any other node. Hop constraints model quality of service constraints. The Lagrangean dual value associated with one Lagrangean relaxation derived from the MCF formulation dominates the corresponding LP value. However, the lower bounds given after a reasonable number of iterations of the associated subgradient optimization procedure are, for several cases, still far from the theoretical best limit. Martin's variable redefinition technique is used to obtain a generalization of the MCF formulation whose LP bound is equal to the previously mentioned Lagrangean dual bound. We use a set of instances with up to 100 nodes, 50 basic nodes, and 350 edges for comparing an LP approach based on solving the LP relaxation of the new model with the equivalent Lagrangean scheme derived from MCF.