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
    bc–opt: a branch-and-cut code for mixed integer programs (1999)
    Springer
    Mathematical programming 86 (1999), S. 335-353 
    Details
    ISSN: 1436-4646
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. A branch-and-cut mixed integer programming system, called bc–opt, is described, incorporating most of the valid inequalities that have been used or suggested for such systems, namely lifted 0-1 knapsack inequalities, 0-1 gub knapsack and integer knapsack inequalities, flowcover and continuous knapsack inequalities, path inequalities for fixed charge network flow structure and Gomory mixed integer cuts. The principal development is a set of interface routines allowing these cut routines to generate cuts for new subsets or aggregations of constraints. The system is built using the XPRESS Optimisation Subroutine Library (XOSL) which includes a cut manager that handles the tree and cut management, so that the user only essentially needs to develop the cut separation routines. Results for the MIPLIB3.0 library are presented - 37 of the instances are solved very easily, optimal or near optimal solution are produced for 18 other instances, and of the 4 remaining instances, 3 have 0, +1, -1 matrices for which bc–opt contains no special features.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050092
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Cutting planes for integer programs with general integer variables (1998)
    Springer
    Mathematical programming 81 (1998), S. 201-214 
    Details
    ISSN: 1436-4646
    Keywords: Integer programming ; Cutting planes ; Cover inequalities ; Lifting ; Gomory mixed integer cuts ; Cut-and-branch
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We investigate the use of cutting planes for integer programs with general integer variables. We show how cutting planes arising from knapsack inequalities can be generated and lifted as in the case of 0–1 variables. We also explore the use of Gomory's mixed-integer cuts. We address both theoretical and computational issues and show how to embed these cutting planes in a branch-and-bound framework. We compare results obtained by using our cut generation routines in two existing systems with a commercially available branch-and-bound code on a range of test problems arising from practical applications. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581105
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    The 0-1 Knapsack problem with a single continuous variable (1999)
    Springer
    Mathematical programming 85 (1999), S. 15-33 
    Details
    ISSN: 1436-4646
    Keywords: Key words: mixed 0-1 Knapsacks – valid inequalities – lifting – restriction
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Specifically we investigate the polyhedral structure of the knapsack problem with a single continuous variable, called the mixed 0-1 knapsack problem. First different classes of facet-defining inequalities are derived based on restriction and lifting. The order of lifting, particularly of the continuous variable, plays an important role. Secondly we show that the flow cover inequalities derived for the single node flow set, consisting of arc flows into and out of a single node with binary variable lower and upper bounds on each arc, can be obtained from valid inequalities for the mixed 0-1 knapsack problem. Thus the separation heuristic we derive for mixed knapsack sets can also be used to derive cuts for more general mixed 0-1 constraints. Initial computational results on a variety of problems are presented.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050044
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    facet.materialart.
    Unknown
    Cutting Planes in Integer and Mixed Integer Programming (1999)
    Details
    Publication Date: 2021-03-16
    Description: This survey presents cutting planes that are useful or potentially useful in solving mixed integer programs. Valid inequalities for i) general integer programs, ii) problems with local structure such as knapsack constraints, and iii) problems with 0-1 coefficient matrices, such as set packing, are examined in turn. Finally the use of valid inequalities for classes of problems with structure, such as network design, is explored.
    Keywords: ddc:000
    Language: English
    Type: reportzib , doc-type:preprint
    Format: application/postscript
    Format: application/pdf
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    OPUS
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...