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
    Capacitated facility location: Separation algorithms and computational experience (1998)
    Springer
    Mathematical programming 81 (1998), S. 149-175 
    Details
    ISSN: 1436-4646
    Keywords: Cutting planes ; Facets ; Location problems
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We consider the polyhedral approach to solving the capacitated facility location problem. The valid inequalities considered are the knapsack cover, flow cover, effective capacity, single depot, and combinatorial inequalities. The flow cover, effective capacity and single depot inequalities form subfamilies of the general family of submodular inequalities. The separation problem based on the family of submodular inequalities is NP-hard in general. For the well known subclass of flow cover inequalities, however, we show that if the client set is fixed, and if all capacities are equal, then the separation problem can be solved in polynomial time. For the flow cover inequalities based on an arbitrary client set and general capacities, and for the effective capacity and single depot inequalities we develop separation heuristics. An important part of these heuristics is based on the result that two specific conditions are necessary for the effective cover inequalities to be facet defining. The way these results are stated indicates precisely how structures that violate the two conditions can be modified to produce stronger inequalities. The family of combinatorial inequalities was originally developed for the uncapacitated facility location problem, but is also valid for the capacitated problem. No computational experience using the combinatorial inequalities has been reported so far. Here we suggest how partial output from the heuristic identifying violated submodular inequalities can be used as input to a heuristic identifying violated combinatorial inequalities. We report on computational results from solving 60 medium size 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/BF01581103
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Reformulation of capacitated facility location problems:How redundant information can help (1998)
    Springer
    Annals of operations research 82 (1998), S. 289-308 
    Details
    ISSN: 1572-9338
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract When solving hard combinatorial optimization problems by branch-and-bound, obtaininga good lower bound (considering a minimization problem) from the linear relaxation iscrucial for the performance of the algorithm. On the other hand, we want to avoid an initialformulation that is too large. This requires careful modeling of the problem. One way ofobtaining a good linear formulation is by applying a cutting plane algorithm where strongcutting planes are added if they violate the current fractional solution. By “strong” cuttingplanes, we mean linear inequalities that define high-dimensional faces of the convex hull offeasible solutions. For some classes of inequalities, effective algorithms for identifyingviolated inequalities belonging to these classes have been implemented as standard featuresin commercial branch-and-bound packages. Such classes are for instance the knapsack coverinequalities and the flow cover inequalities that were originally developed for the knapsackproblem and the single-node flow problem. These problems form relaxations of severalcapacitated combinatorial optimization problems such as various capacitated facility locationproblems. If, however, we consider traditional models for location problems, then theknapsack and single-node flow relaxations are not explicitly stated in the models, andunless we modify the models, the mentioned classes of inequalities will not be generated“automatically” by the systems. The extra variables and constraints that we need to add tothe traditional models in order to make the various relaxations explicit are redundant, notonly to the integer formulation but also to the linear relaxation. Computational experimentsdo, however, indicate that the inequalities that are generated based on the relaxations arevery effective and that the gain from the stronger linear relaxation far outweighs the drawbackof expanding the traditional models.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1018966804496
    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, 8thinternational IPCO conference Utrecht, ¬The¬ Netherlands, June 13-15, 2001, proceedings; 2081 (2001)
    Berlin u.a. :Springer,
    Details
    Title: Integer programming and combinatorial optimization, 8thinternational IPCO conference Utrecht, ¬The¬ Netherlands, June 13-15, 2001, proceedings; 2081
    Contributer: Aardal, Karen , Gerards, Bert
    Publisher: Berlin u.a. :Springer,
    Year of publication: 2001
    Pages: 421 S.
    Series Statement: Lecture notes in computer science 2081
    Type of Medium: Book
    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
    Models and Solution Techniques for Frequency Assignment Problems (2001)
    Details
    Publication Date: 2014-11-11
    Description: {\begin{rawhtml} 〈a href="http://dx.doi.org/10.1007/s10479-007-0178-0"〉 Revised Version unter http://dx.doi.org/10.1007/s10479-007-0178-0〈/a〉 \end{rawhtml}} Wireless communication is used in many different situations such as mobile telephony, radio and TV broadcasting, satellite communication, and military operations. In each of these situations a frequency assignment problem arises with application specific characteristics. Researchers have developed different modelling ideas for each of the features of the problem, such as the handling of interference among radio signals, the availability of frequencies, and the optimization criterion. This survey gives an overview of the models and methods that the literature provides on the topic. We present a broad description of the practical settings in which frequency assignment is applied. We also present a classification of the different models and formulations described in the literature, such that the common features of the models are emphasized. The solution methods are divided in two parts. Optimization and lower bounding techniques on the one hand, and heuristic search techniques on the other hand. The literature is classified according to the used methods. Again, we emphasize the common features, used in the different papers. The quality of the solution methods is compared, whenever possible, on publicly available benchmark instances.
    Keywords: ddc:000
    Language: English
    Type: reportzib , doc-type:preprint
    Format: application/postscript
    Format: application/pdf
    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...