Bibliothek

X
feed icon rss

Ihre E-Mail wurde erfolgreich gesendet. Bitte prüfen Sie Ihren Maileingang.

Leider ist ein Fehler beim E-Mail-Versand aufgetreten. Bitte versuchen Sie es erneut.

Vorgang fortführen?

Exportieren
  • 1
    Digitale Medien
    Digitale Medien
    A lift-and-project cutting plane algorithm for mixed 0–1 programs (1993)
    Springer
    Mathematical programming 58 (1993), S. 295-324 
    Details
    ISSN: 1436-4646
    Schlagwort(e): Cutting planes ; projection ; mixed 0–1 programming ; disjunctive programming
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract We propose a cutting plane algorithm for mixed 0–1 programs based on a family of polyhedra which strengthen the usual LP relaxation. We show how to generate a facet of a polyhedron in this family which is most violated by the current fractional point. This cut is found through the solution of a linear program that has about twice the size of the usual LP relaxation. A lifting step is used to reduce the size of the LP's needed to generate the cuts. An additional strengthening step suggested by Balas and Jeroslow is then applied. We report our computational experience with a preliminary version of the algorithm. This approach is related to the work of Balas on disjunctive programming, the matrix cone relaxations of Lovász and Schrijver and the hierarchy of relaxations of Sherali and Adams.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01581273
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 2
    Digitale Medien
    Digitale Medien
    On the set covering polytope: II. Lifting the facets with coefficients in {0, 1, 2} (1989)
    Springer
    Mathematical programming 45 (1989), S. 1-20 
    Details
    ISSN: 1436-4646
    Schlagwort(e): Set covering ; facet lifting ; polyhedral combinatorics
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract In an earlier paper (Mathematical Programming 43 (1989) 57–69) we characterized the class of facets of the set covering polytope defined by inequalities with coefficients equal to 0, 1 or 2. In this paper we connect that characterization to the theory of facet lifting. In particular, we introduce a family of lower dimensional polytopes and associated inequalities having only three nonzero coefficients, whose lifting yields all the valid inequalities in the above class, with the lifting coefficients given by closed form expressions.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01589093
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 3
    Digitale Medien
    Digitale Medien
    Optimized Crossover-Based Genetic Algorithms for the Maximum Cardinality and Maximum Weight Clique Problems (1998)
    Springer
    Journal of heuristics 4 (1998), S. 107-122 
    Details
    ISSN: 1572-9397
    Schlagwort(e): maximum clique ; genetic algorithms ; optimized crossover
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract In Balas and Niehaus (1996), we have developed a heuristic for generating large cliques in an arbitrary graph, by repeatedly taking two cliques and finding a maximum clique in the subgraph induced by the union of their vertex sets, an operation executable in polynomial time through bipartite matching in the complement of the subgraph. Aggarwal, Orlin and Tai (1997) recognized that the latter operation can be embedded into the framework of a genetic algorithm as an optimized crossover operation. Inspired by their approach, we examine variations of each element of the genetic algorithm—selection, population replacement and mutation—and develop a steady-state genetic algorithm that performs better than its competitors on most problems.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1023/A:1009646528813
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 4
    Digitale Medien
    Digitale Medien
    Integer programming and convex analysis: Intersection cuts from outer polars (1972)
    Springer
    Mathematical programming 2 (1972), S. 330-382 
    Details
    ISSN: 1436-4646
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract Recently a new, geometrically motivated approach was proposed [1] for integer programming, based on generating intersection cuts from some convex setS whose interior contains the linear programming optimum $$\bar x$$ but no feasible integer point. Larger sets tend to produce stronger cuts, and in this paper convex analysis is used to construct sets as large as possible within the above requirements. Information is generated from all problem constraints within a unit cubeK containing $$\bar x$$ The key concept is that of outer polars, viewed as maximal convex extensions of the ballB circumscribingK, relative to the problem constraints. The outer polarF * of the feasible setF overB is shown to be a convex set whose boundary contains all feasible vertices ofK, and whose interior contains no feasible integer point. The existence of a dual correspondence betweenF andF *, and the fact that polarity is inclusion-reversing, leads to a dualization of operations onF. As one possible procedure based on this approach, we construct a generalized intersection cut, that can be strengthened whenever some vertex ofF is cut off. This makes it possible to fruitfully combine intersection cuts with implicit enumeration or branch-and-bound. While valid for arbitrary integer programs, the theory developed here is relevant primarily to (pure or mixed-integer) 0–1 problems. Other topics discussed include: generalized polars, intersection cuts from related problems, connections with asymptotic theory.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01584553
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 5
    Digitale Medien
    Digitale Medien
    On the set covering polytope: I. All the facets with coefficients in {0, 1, 2} (1989)
    Springer
    Mathematical programming 43 (1989), S. 57-69 
    Details
    ISSN: 1436-4646
    Schlagwort(e): Set covering ; facets ; polyhedral combinatorics ; integer programming
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract While the set packing polytope, through its connection with vertex packing, has lent itself to fruitful investigations, little is known about the set covering polytope. We characterize the class of valid inequalities for the set covering polytope with coefficients equal to 0, 1 or 2, and give necessary and sufficient conditions for such an inequality to be minimal and to be facet defining. We show that all inequalities in the above class are contained in the elementary closure of the constraint set, and that 2 is the largest value ofk such that all valid inequalities for the set covering polytope with integer coefficients no greater thank are contained in the elementary closure. We point out a connection between minimal inequalities in the class investigated and certain circulant submatrices of the coefficient matrix. Finally, we discuss conditions for an inequality to cut off a fractional solution to the linear programming relaxation of the set covering problem and to improve the lower bound given by a feasible solution to the dual of the linear programming relaxation.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01582278
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 6
    Digitale Medien
    Digitale Medien
    A restricted Lagrangean approach to the traveling salesman problem (1981)
    Springer
    Mathematical programming 21 (1981), S. 19-46 
    Details
    ISSN: 1436-4646
    Schlagwort(e): Traveling Salesman Problem ; Assignment Problem ; Branch and Bound ; Lagrangean Relaxation ; Hamiltonian Circuits ; Arc Premiums/Penalties
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract We describe an algorithm for the asymmetric traveling salesman problem (TSP) using a new, restricted Lagrangean relaxation based on the assignment problem (AP). The Lagrange multipliers are constrained so as to guarantee the continued optimality of the initial AP solution, thus eliminating the need for repeatedly solving AP in the process of computing multipliers. We give several polynomially bounded procedures for generating valid inequalities and taking them into the Lagrangean function with a positive multiplier without violating the constraints, so as to strengthen the current lower bound. Upper bounds are generated by a fast tour-building heuristic. When the bound-strengthening techniques are exhausted without matching the upper with the lower bound, we branch by using two different rules, according to the situation: the usual subtour breaking disjunction, and a new disjunction based on conditional bounds. We discuss computational experience on 120 randomly generated asymmetric TSP's with up to 325 cities, the maximum time used for any single problem being 82 seconds. This is a considerable improvement upon earlier methods. Though the algorithm discussed here is for the asymmetric TSP, the approach can be adapted to the symmetric TSP by using the 2-matching problem instead of AP.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01584228
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 7
    Digitale Medien
    Digitale Medien
    Sequential convexification in reverse convex and disjunctive programming (1989)
    Springer
    Mathematical programming 44 (1989), S. 337-350 
    Details
    ISSN: 1436-4646
    Schlagwort(e): Disjunctive programming ; reverse convex programming ; facial disjunctive sets ; convex hull generation
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract This paper is about a property of certain combinatorial structures, called sequential convexifiability, shown by Balas (1974, 1979) to hold for facial disjunctive programs. Sequential convexifiability means that the convex hull of a nonconvex set defined by a collection of constraints can be generated by imposing the constraints one by one, sequentially, and generating each time the convex hull of the resulting set. Here we extend the class of problems considered to disjunctive programs with infinitely many terms, also known as reverse convex programs, and give necessary and sufficient conditions for the solution sets of such problems to be sequentially convexifiable. We point out important classes of problems in addition to facial disjunctive programs (for instance, reverse convex programs with equations only) for which the conditions are always satisfied. Finally, we give examples of disjunctive programs for which the conditions are violated, and so the procedure breaks down.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01587096
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 8
    Digitale Medien
    Digitale Medien
    A lifting procedure for the asymmetric traveling salesman polytope and a large new class of facets (1993)
    Springer
    Mathematical programming 58 (1993), S. 325-352 
    Details
    ISSN: 1436-4646
    Schlagwort(e): Traveling salesman ; facet lifting ; polyhedral combinatorics
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract Given any family ℱ of valid inequalities for the asymmetric traveling salesman polytopeP(G) defined on the complete digraphG, we show that all members of ℱ are facet defining if the primitive members of ℱ (usually a small subclass) are. Based on this result we then introduce a general procedure for identifying new classes of facet inducing inequalities forP(G) by lifting inequalities that are facet inducing forP(G′), whereG′ is some induced subgraph ofG. Unlike traditional lifting, where the lifted coefficients are calculated one by one and their value depends on the lifting sequence, our lifting procedure replaces nodes ofG′ with cliques ofG and uses closed form expressions for calculating the coefficients of the new arcs, which are sequence-independent. We also introduce a new class of facet inducing inequalities, the class of SD (source-destination) inequalities, which subsumes as special cases most known families of facet defining inequalities.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01581274
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 9
    Digitale Medien
    Digitale Medien
    The precedence-constrained asymmetric traveling salesman polytope (1995)
    Springer
    Mathematical programming 68 (1995), S. 241-265 
    Details
    ISSN: 1436-4646
    Schlagwort(e): Asymmetric traveling salesman problem ; Precedence constraints ; Facets ; Generalized TSP
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract Many applications of the traveling salesman problem require the introduction of additional constraints. One of the most frequently occurring classes of such constraints are those requiring that certain cities be visited before others (precedence constraints). In this paper we study the Precedence-Constrained Asymmetric Traveling Salesman (PCATS) polytope, i.e. the convex hull of incidence vectors of tours in a precedence-constrained directed graph. We derive several families of valid inequalities, and give polynomial time separation algorithms for important subfamilies. We then establish the dimension of the PCATS polytope and show that, under reasonable assumptions, the two main classes of inequalities derived are facet inducing.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01585767
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 10
    Digitale Medien
    Digitale Medien
    Facets of the knapsack polytope (1975)
    Springer
    Mathematical programming 8 (1975), S. 146-164 
    Details
    ISSN: 1436-4646
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract A necessary and sufficient condition is given for an inequality with coefficients 0 or 1 to define a facet of the knapsack polytope, i.e., of the convex hull of 0–1 points satisfying a given linear inequality. A sufficient condition is also established for a larger class of inequalities (with coefficients not restricted to 0 and 1) to define a facet for the same polytope, and a procedure is given for generating all facets in the above two classes. The procedure can be viewed as a way of generating cutting planes for 0–1 programs.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01580440
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
Schließen ⊗
Diese Webseite nutzt Cookies und das Analyse-Tool Matomo. Weitere Informationen finden Sie hier...