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
    On the 0, 1 facets of the set covering polytope (1989)
    Springer
    Mathematical programming 43 (1989), S. 45-55 
    Details
    ISSN: 1436-4646
    Keywords: Set covering ; set packing ; polytope ; facet ; odd hole
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper, we consider inequalities of the formΣ α jxj ≥ β, whereα j equals 0 or 1, andβ is a positive integer. We give necessary and sufficient conditions for such inequalities to define facets of the set covering polytope associated with a 0, 1 constraint matrixA. These conditions are in terms of critical edges and critical cutsets defined in the bipartite incidence graph ofA, and are in the spirit of the work of Balas and Zemel on the set packing problem where similar notions were defined in the intersection graph ofA. Furthermore, we give a polynomial characterization of a class of 0, 1 facets defined from chorded cycles of the bipartite incidence graph. This characterization also yields all the 0, 1 liftings of odd-hole inequalities for the simple plant location polytope.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582277
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    (0, ±1) ideal matrices (1998)
    Springer
    Mathematical programming 80 (1998), S. 265-281 
    Details
    ISSN: 1436-4646
    Keywords: Generalized set covering problem ; Perfect and ideal matrices ; Lehman's theorem ; (0, ±1) matrices
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A (0, 1) matrixA is said to be ideal if all the vertices of the polytopeQ(A) = {x ∣ Ax ⩾ 1, 0 ⩽x ⩽ 1} are integral. The issue of finding a satisfactory characterization of those matrices which are minimally non-ideal is a well known open problem. An outstanding result toward the solution of this problem, due to Alfred Lehman, is the description of crucial properties of minimally non-ideal matrices. In this paper we consider the extension of the notion of ideality to (0, ±1) matrices. By means of a standard transformation, we associate with any (0, ±1) matrixA a suitable (0, 1) matrixD(A). Then we introduce the concept of disjoint completionA + of a (0, ±1) matrixA and we show thatA is ideal if and only ifD(A +) is ideal. Moreover, we introduce a suitable concept of a minimally non-ideal (0, ±1) matrix and we prove a Lehman-type characterization of minimally non-ideal (0, ±1) matrices. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581169
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    A Lagrangian-based heuristic for large-scale set covering problems (1998)
    Springer
    Mathematical programming 81 (1998), S. 215-228 
    Details
    ISSN: 1436-4646
    Keywords: Set covering ; Crew scheduling ; Primal-dual lagrangian ; Subgradient algorithms ; 0–1 programming ; Approximate solutions ; Railways
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present a new Lagrangian-based heuristic for solving large-scale set-covering problems arising from crew-scheduling at the Italian Railways (Ferrovie dello Stato). Our heuristic obtained impressive results when compared to state-of-the-art codes on a test-bed provided by the company, which includes instances with sizes ranging from 50,000 variables and 500 constraints to 1,000,000 variables and 5000 constraints. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581106
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Facets and lifting procedures for the set covering polytope (1989)
    Springer
    Mathematical programming 45 (1989), S. 111-137 
    Details
    ISSN: 1436-4646
    Keywords: Independence systems ; set covering ; polytope ; facet
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a family of subsetsℱ of an arbitrary groundsetE, acover ofℱ is any setC ⊂E having non-empty intersection with every subset inℱ. In this paper we deal with thecovering polytope, i.e., the convex hull of the incidence vectors of all the covers ofℱ. In Section 2 we review all the known properties of the covering polytope. In Sections 3 and 4 we introduce two new classes of non-Boolean facets of such a polytope. In Sections 5 and 6 we describe some non-sequential lifting procedures. In Section 7 a generalization of the notion ofweb introduced by L.E. Trotter is presented together with the facets of the covering polytope produced by such a structure. Moreover, the strong connections between several combinatorial problems and the covering problem are pointed out and, exploiting those connections, some examples are presented of new facets for the Knapsack and Acyclic Subdigraph polytopes.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01589100
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    The equipartition polytope. I: Formulations, dimension and basic facets (1990)
    Springer
    Mathematical programming 49 (1990), S. 49-70 
    Details
    ISSN: 1436-4646
    Keywords: Equipartition polytope ; cut polytope ; Boolean quadratic programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The following basic clustering problem arises in different domains, ranging from physics, statistics and Boolean function minimization. Given a graphG = (V, E) and edge weightsc e , partition the setV into two sets of ⌈1/2|V|⌉ and ⌊1/2|V|⌋ nodes in such a way that the sum of the weights of edges not having both endnodes in the same set is maximized or minimized. Anequicut is a feasible solution of the above problem and theequicut polytope Q(G) is the convex hull of the incidence vectors of equicuts inG. In this paper we give some integer programming formulations of the equicut problem, study the dimension of the equicut polytope and describe some basic classes of facet-inducing inequalities forQ(G).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01588778
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    The equipartition polytope. II: Valid inequalities and facets (1990)
    Springer
    Mathematical programming 49 (1990), S. 71-90 
    Details
    ISSN: 1436-4646
    Keywords: Equipartition polytope ; cut polytope ; Boolean quadratic programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Theequipartition problem is defined as follows: given a graphG = (V, E) and edge weightsc e , partition the setV into two sets of ⌈1/2|V|⌉ and ⌊1/2|V|⌋ nodes in such a way that the sum of the weights of edges not having both endnodes in the same set is maximized or minimized. Anequicut is a feasible solution of the above problem and theequicut polytope Q(G) is the convex hull of the incidence vectors of equicuts inG. In this paper we describe some facet inducing inequalities of this polytope.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01588779
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    An exact algorithm for the maximum stable set problem (1994)
    Springer
    Computational optimization and applications 3 (1994), S. 243-258 
    Details
    ISSN: 1573-2894
    Keywords: Maximum stable set ; maximum clique ; branch-and-bound
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract We describe a new branch-and-bound algorithm for the exact solution of the maximum cardinality stable set problem. The bounding phase is based on a variation of the standard greedy algorithm for finding a colouring of a graph. Two different node-fixing heuristics are also described. Computational tests on random and structured graphs and very large graphs corresponding to ‘real-life’ problems show that the algorithm is competitive with the fastest algorithms known so far.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01299447
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    facet.materialart.
    Unknown
    GUB Covers and Power-Indexed Formulations for Wireless Network Design (2013)
    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
  • 9
    facet.materialart.
    Unknown
    Negative Cycle Separation in Wireless Network Design (2011)
    Details
    Publication Date: 2020-08-05
    Language: English
    Type: conferenceobject , doc-type:conferenceObject
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    OPUS
  • 10
    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...