Browsing by Author "Donoso, Macarena"

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    A branch and cut algorithm for the hierarchical network design problem
    (ELSEVIER SCIENCE BV, 2010) Obreque, Carlos; Donoso, Macarena; Gutierrez, Gabriel; Marianov, Vladimir
    The Hierarchical Network Design Problem consists of locating a minimum cost bi-level network on a graph. The higher level sub-network is a path visiting two or more nodes. The lower level sub-network is a forest connecting the remaining nodes to the path. We optimally solve the problem using an ad hoc branch and cut procedure. Relaxed versions of a base model are solved using an optimization package and, if binary variables have fractional values or if some of the relaxed constraints are violated in the solution, cutting planes are added. Once no more cuts can be added. branch and bound is used. The method for finding valid cutting planes is presented. Finally, we use different available test instances to compare the procedure with the best known published optimal procedure, with good results. In none of the instances we needed to apply branch and bound, but only the cutting planes. (C) 2008 Elsevier B.V. All rights reserved.
  • Thumbnail Image
    Item
    Minimum cost path location for maximum traffic capture
    (PERGAMON-ELSEVIER SCIENCE LTD, 2010) Gutierrez Jarpa, Gabriel; Donoso, Macarena; Obreque, Carlos; Marianov, Vladimir
    A free path (with no preset extreme nodes) is located on a network, in such a way as to minimize the cost and maximize the traffic captured by the path. Traffic between a pair of nodes is captured if both nodes are visited by the path. Applications are the design of the route and locations of mailboxes for a local package delivery company, or the design of bus or subway lines, in which the shape of the route and the number of stops is determined by the solution of the optimization problem. The problem also applies to the design of an optical fiber network interconnecting WiFi antennas in a university campus. We propose two models and an exact solution method. Computational experience is presented for up to 300 nodes and 1772 arcs, as well as a practical case for the city of Concepcion, Chile. (C) 2009 Elsevier Ltd. All rights reserved.