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
    A restricted Lagrangean approach to the traveling salesman problem (1981)
    Springer
    Mathematical programming 21 (1981), S. 19-46 
    Details
    ISSN: 1436-4646
    Keywords: Traveling Salesman Problem ; Assignment Problem ; Branch and Bound ; Lagrangean Relaxation ; Hamiltonian Circuits ; Arc Premiums/Penalties
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01584228
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Facets of the knapsack polytope (1975)
    Springer
    Mathematical programming 8 (1975), S. 146-164 
    Details
    ISSN: 1436-4646
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580440
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Integer programming and convex analysis: Intersection cuts from outer polars (1972)
    Springer
    Mathematical programming 2 (1972), S. 330-382 
    Details
    ISSN: 1436-4646
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01584553
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    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
    Keywords: Cutting planes ; projection ; mixed 0–1 programming ; disjunctive programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581273
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    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
    Keywords: Set covering ; facets ; polyhedral combinatorics ; integer programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582278
    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 precedence-constrained asymmetric traveling salesman polytope (1995)
    Springer
    Mathematical programming 68 (1995), S. 241-265 
    Details
    ISSN: 1436-4646
    Keywords: Asymmetric traveling salesman problem ; Precedence constraints ; Facets ; Generalized TSP
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585767
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    Sequential convexification in reverse convex and disjunctive programming (1989)
    Springer
    Mathematical programming 44 (1989), S. 337-350 
    Details
    ISSN: 1436-4646
    Keywords: Disjunctive programming ; reverse convex programming ; facial disjunctive sets ; convex hull generation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01587096
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    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
    Keywords: Set covering ; facet lifting ; polyhedral combinatorics
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01589093
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    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
    Keywords: Traveling salesman ; facet lifting ; polyhedral combinatorics
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581274
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 10
    Electronic Resource
    Electronic Resource
    Job Shop Scheduling With Deadlines (1998)
    Springer
    Journal of combinatorial optimization 1 (1998), S. 329-353 
    Details
    ISSN: 1573-2886
    Keywords: scheduling ; deadlines ; shifting bottleneck
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract In this paper we deal with a variant of the Job ShopScheduling Problem. We consider the addition of release dates anddeadlines to be met by all jobs. The objective is makespanminimization if there are no tardy jobs, and tardiness minimizationotherwise. The problem is approached by using a Shifting Bottleneckstrategy. The presence of deadlines motivates an iterative use of aparticular one machine problem which is solved optimally. Theoverall procedure is heuristic and exhibits a good trade-off betweencomputing time and solution quality.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1009750409895
    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...