Library

X
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
  • 1
    Electronic Resource
    Electronic Resource
    A branch-and-cut algorithm for capacitated network design problems (1999)
    Springer
    Mathematical programming 86 (1999), S. 17-39 
    Details
    ISSN: 1436-4646
    Keywords: Key words: mixed-integer programming – branch-and-cut – computing
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. We present a branch-and-cut algorithm to solve capacitated network design problems. Given a capacitated network and point-to-point traffic demands, the objective is to install more capacity on the edges of the network and route traffic simultaneously, so that the overall cost is minimized. We study a mixed-integer programming formulation of the problem and identify some new facet defining inequalities. These inequalities, together with other known combinatorial and mixed-integer rounding inequalities, are used as cutting planes. To choose the branching variable, we use a new rule called “knapsack branching”. We also report on our computational experience using real-life data.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050077
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Minimum cost capacity installation for multicommodity network flows (1998)
    Springer
    Mathematical programming 81 (1998), S. 177-199 
    Details
    ISSN: 1436-4646
    Keywords: Network design ; Integer programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Consider a directed graphG = (V,A), and a set of traffic demands to be shipped between pairs of nodes inV. Capacity has to be installed on the edges of this graph (in integer multiples of a base unit) so that traffic can be routed. In this paper we consider the problem of minimum cost installation of capacity on the arcs to ensure that the required demands can be shipped simultaneously between node pairs. We study two different approaches for solving problems of this type. The first one is based on the idea of metric inequalities (see Onaga and Kakusho, On feasibility conditions of multicommodity flows in networks, IEEE Transactions on Circuit Theory, CT-18 (4) (1971) 425–429.), and uses a formulation with only |A| variables. The second uses an aggregated multicommodity flow formulation and has |V||A| variables. We first describe two classes of strong valid inequalities and use them to obtain a complete polyhedral description of the associated polyhedron for the complete graph on three nodes. Next we explain our solution methods for both of the approaches in detail and present computational results. Our computational experience shows that the two formulations are comparable and yield effective algorithms for solving real-life problems. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581104
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Book
    Book
    Integer programming and combinatorial optimization /; 6655 (2011)
    Heidelberg [u.a.] :Springer,
    Details
    Title: Integer programming and combinatorial optimization /; 6655
    Contributer: Günlük, Oktay , Woeginger, Gerhard J. , IPCO 〈15, 2011, New York, NY〉
    Publisher: Heidelberg [u.a.] :Springer,
    Year of publication: 2011
    Pages: XIII, 432 S. : , graph. Darst. ; , 235 mm x 155 mm
    Series Statement: Lecture notes in computer science 6655
    ISBN: 3-642-20806-1 , 978-3-642-20806-5 , 978-3-642-20807-2
    Type of Medium: Book
    Language: English
    URL: http://deposit.d-nb.de/cgi-bin/dokserv?id=3708421&prov=M&dok_var=1&dok_ext=htm
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    ZIB Catalog
    Zuse Institute Berlin get availability status
  • 4
    facet.materialart.
    Unknown
    A note on the MIR closure and basic relaxations of polyhedra (2011)
    Details
    Publication Date: 2020-08-05
    Language: English
    Type: article , doc-type:article
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    OPUS
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...