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
    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
  • 2
    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
  • 3
    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
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...