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 polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles (1981)
    Springer
    Mathematical programming 20 (1981), S. 225-232 
    Details
    ISSN: 1436-4646
    Keywords: Combinatorial Optimization ; Vertex Packings ; Graph Theory ; Polynomial Algorithm
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The vertex packing problem for a given graph is to find a maximum number of vertices no two of which are joined by an edge. The weighted version of this problem is to find a vertex packingP such that the sum of the individual vertex weights is maximum. LetG be the family of graphs whose longest odd cycle is of length not greater than 2K + 1, whereK is any non-negative integer independent of the number (denoted byn) of vertices in the graph. We present an O(n 2K+1) algorithm for the maximum weighted vertex packing problem for graphs inG ≥ 1. A by-product of this algorithm is an algorithm for piecing together maximum weighted packings on blocks to find maximum weighted packings on graphs that contain more than one block. We also give an O(n 2K+3) algorithm for testing membership inG
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01589347
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Lifted flow cover inequalities for mixed 0-1 integer programs (1999)
    Springer
    Mathematical programming 85 (1999), S. 439-467 
    Details
    ISSN: 1436-4646
    Keywords: Mathematics Subject Classification (1991): 90C11
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. We investigate strong inequalities for mixed 0-1 integer programs derived from flow cover inequalities. Flow cover inequalities are usually not facet defining and need to be lifted to obtain stronger inequalities. However, because of the sequential nature of the standard lifting techniques and the complexity of the optimization problems that have to be solved to obtain lifting coefficients, lifting of flow cover inequalities is computationally very demanding. We present a computationally efficient way to lift flow cover inequalities based on sequence independent lifting techniques and give computational results that show the effectiveness of our lifting procedures.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050067
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Simplex pivots on the set packing polytope (1985)
    Springer
    Mathematical programming 33 (1985), S. 123-138 
    Details
    ISSN: 1436-4646
    Keywords: Set Packing ; Integer Programming ; Linear Programming ; Simplex Method
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper considers the set packing problem max{wx: Ax ⩽ b, x ⩾ 0 and integral}, whereA is anm × n 0–1 matrix,w is a 1 ×n weight vector of real numbers andb is anm × 1 vector of ones. In equality form, its linear programming relaxation is max{wx: (x, y) ∈P(A)} whereP(A) = {(x, y):Ax +I m y =b, x⩾0,y⩾0}. Letx 1 be any feasible solution to the set packing problem that is not optimal and lety 1 =b − Ax 1; then (x 1,y 1) is an integral extreme point ofP(A). We show that there exists a sequence of simplex pivots from (x 1,y 1) to (x*,y*), wherex* is an optimal solution to the set packing problem andy* =b − Ax*, that satisfies the following properties. Each pivot column has positive reduced weight and each pivot element equals plus one. The number of pivots equals the number of components ofx* that are nonbasic in (x 1,y 1).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582240
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    The mixed vertex packing problem (2000)
    Springer
    Mathematical programming 89 (2000), S. 35-53 
    Details
    ISSN: 1436-4646
    Keywords: Mathematics Subject Classification (1991): 90C10, 90C11, 90C57
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. We study a generalization of the vertex packing problem having both binary and bounded continuous variables, called the mixed vertex packing problem (MVPP). The well-known vertex packing model arises as a subproblem or relaxation of many 0-1 integer problems, whereas the mixed vertex packing model arises as a natural counterpart of vertex packing in the context of mixed 0-1 integer programming. We describe strong valid inequalities for the convex hull of solutions to the MVPP and separation algorithms for these inequalities. We give a summary of computational results with a branch-and-cut algorithm for solving the MVPP and using it to solve general mixed-integer problems.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070000154.
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Min-cut clustering (1993)
    Springer
    Mathematical programming 62 (1993), S. 133-151 
    Details
    ISSN: 1436-4646
    Keywords: Clustering ; decomposition ; column generation ; subproblem optimization ; valid inequality ; compiler design
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We describe a decomposition framework and a column generation scheme for solving a min-cut clustering problem. The subproblem to generate additional columns is itself an NP-hard mixed integer programming problem. We discuss strong valid inequalities for the subproblem and describe some efficient solution strategies. Computational results on compiler construction problems are reported.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585164
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    Book reviews (1973)
    Springer
    Mathematical programming 4 (1973), S. 113-118 
    Details
    ISSN: 1436-4646
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01584651
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    A recursive procedure to generate all cuts for 0–1 mixed integer programs (1990)
    Springer
    Mathematical programming 46 (1990), S. 379-390 
    Details
    ISSN: 1436-4646
    Keywords: Cutting planes ; valid inequalities ; disjunctive inequalities ; superadditive functions ; 0–1 mixed integer programs
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We study several ways of obtaining valid inequalities for mixed integer programs. We show how inequalities obtained from a disjunctive argument can be represented by superadditive functions and we show how the superadditive inequalities relate to Gomory's mixed integer cuts. We also show how all valid inequalities for mixed 0–1 programs can be generated recursively from a simple subclass of the disjunctive inequalities.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585752
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    The fleet assignment problem: Solving a large-scale integer program (1995)
    Springer
    Mathematical programming 70 (1995), S. 211-232 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Mixed-integer programming ; Large-scale optimization ; Airline fleet assignment
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a flight schedule and set of aircraft, the fleet assignment problem is to determine which type of aircraft should fly each flight segment. This paper describes a basic daily, domestic fleet assignment problem and then presents chronologically the steps taken to solve it efficiently. Our model of the fleet assignment problem is a large multi-commodity flow problem with side constraints defined on a time-expanded network. These problems are often severely degenerate, which leads to poor performance of standard linear programming techniques. Also, the large number of integer variables can make finding optimal integer solutions difficult and time-consuming. The methods used to attack this problem include an interior-point algorithm, dual steepest edge simplex, cost perturbation, model aggregation, branching on set-partitioning constraints and prioritizing the order of branching. The computational results show that the algorithm finds solutions with a maximum optimality gap of 0.02% and is more than two orders of magnitude faster than using default options of a standard LP-based branch-and-bound code.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585938
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    Sequence Independent Lifting in Mixed Integer Programming (2000)
    Springer
    Journal of combinatorial optimization 4 (2000), S. 109-129 
    Details
    ISSN: 1573-2886
    Keywords: integer programming ; lifting
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We investigate lifting, i.e., the process of taking a valid inequality for a polyhedron and extending it to a valid inequality in a higher dimensional space. Lifting is usually applied sequentially, that is, variables in a set are lifted one after the other. This may be computationally unattractive since it involves the solution of an optimization problem to compute a lifting coefficient for each variable. To relieve this computational burden, we study sequence independent lifting, which only involves the solution of one optimization problem. We show that if a certain lifting function is superadditive, then the lifting coefficients are independent of the lifting sequence. We introduce the idea of valid superadditive lifting functions to obtain good aproximations to maximum lifting. We apply these results to strengthen Balas' lifting theorem for cover inequalities and to produce lifted flow cover inequalities for a single node flow problem.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1009841107478
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 10
    Electronic Resource
    Electronic Resource
    Solving binary cutting stock problems by column generation and branch-and-bound (1994)
    Springer
    Computational optimization and applications 3 (1994), S. 111-130 
    Details
    ISSN: 1573-2894
    Keywords: column generation ; cutting stock problem ; branch-and-bound
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract We present an algorithm for the binary cutting stock problem that employs both column generation and branch-and-bound to obtain optimal integer solutions. We formulate a branching rule that can be incorporated into the subproblem to allow column generation at any node in the branch-and-bound tree. Implementation details and computational experience are discussed.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01300970
    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...