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
    Facet of regular 0–1 polytopes (1975)
    Springer
    Mathematical programming 8 (1975), S. 179-206 
    Details
    ISSN: 1436-4646
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The role of 0–1 programming problems having monotone or regular feasible sets was pointed out in [6]. The solution sets of covering and of knapsack problems are examples of monotone and of regular sets respectively. Some connections are established between prime implicants of a monotone or a regular Boolean functionβ on the one hand, and facets of the convex hullH of the zeros ofβ on the other. In particular (Corollary 2) a necessary and sufficient condition is given for a constraint of a covering problem to be a facet of the corresponding integer polyhedron. For any prime implicantP ofβ, a nonempty familyF(P) of facets ofH is constructed. Proposition 17 gives easy-to-determine sharp upper bounds for the coefficients of these facets whenβ is regular. A special class of prime implicants is described for regular functions and it is shown that for anyP in this class,F(P) consists of one facet ofH, and this facet has 0–1 coefficients. Every nontrivial facet ofH with 0–1 coefficients is obtained from this class.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580442
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Computing low-capacity 0–1 knapsack polytopes (1982)
    Springer
    Mathematical methods of operations research 26 (1982), S. 243-249 
    Details
    ISSN: 1432-5217
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Zusammenfassung Es wird ein Verfahren vorgestellt, das für eine lineare UngleichungL in binären Variablen mit positiven ganzzahligen Koeffizienten alle Facetten der konvexen Hülle der Lösungen vonL bestimmt. Um diese Facetten für irgendeine UngleichungL mit rechter Seiteb zu erhalten, braucht man nur die Facetten des sogenannten Master-Knapsack-ProblemsM b zu kennen, dasO (b log b) Variablen besitzt. Fürb=1,..., 7 werden alle Facetten vonM b angegeben.
    Notes: Abstract A procedure is proposed that, given a linear inequalityL having positive integral coefficients in 0–1 variables, finds all the facets of the convex hull of the solutions ofL. This is done for allL by doing once and for all the computations for a particular sequenceM 1,M 2,... of such linear inequalities, called master knapsack problems. To find the facets for a givenL, it is enough to know the facets for the master knapsack problemM b, whereb is the free term inL (no matter how many variablesL might have). ThisM b has no more than order ofb logb variables. The procedure is based on polarity. All the facets forM 1,...,M 7 are tabulated.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01917116
    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...