bc-opt: A branch-and-cut code for mixed integer programs. 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.par The system is built using the XPRESS Optimization 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.par Results for the MIPLIB3.0 library are presented -- 37 of the instances are solved very easily, optimal or near optimal solutions 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.
Keywords for this software
References in zbMATH (referenced in 12 articles )
Showing results 1 to 12 of 12.
- Milano, Michela; Wallace, Mark: Integrating operations research in constraint programming (2010)
- Belov, G.; Scheithauer, G.: A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting (2006)
- Fontes, Dalila B. M. M.; Hadjiconstantinou, Eleni; Christofides, Nicos: A dynamic programming approach for solving single-source uncapacitated concave minimum cost network flow problems (2006)
- Milano, Michela; Wallace, Mark: Integrating operations research in constraint programming (2006)
- Sergienko, I. V.; Shylo, V. P.: Problems of discrete optimization: challenges and main approaches to solve them (2006)
- Padberg, Manfred: Classical cuts for mixed-integer programming and branch-and-cut (2005)
- De Schutter, B.; Heemels, W. P. M. H.; Bemporad, A.: On the equivalence of linear complementarity problems (2002)
- Marchand, Hugues; Martin, Alexander; Weismantel, Robert; Wolsey, Laurence: Cutting planes in integer and mixed integer programming (2002)
- Wolsey, Laurence A.: Solving multi-item lot-sizing problems with an MIP solver using classification and reformulation (2002)
- Atamtürk, Alper: Flow pack facets of the single node fixed-charge flow polytope (2001)
- Loparic, Marko; Pochet, Yves; Wolsey, Laurence A.: The uncapacitated lot-sizing problem with sales and safety stocks (2001)
- Cordier, Cécile; Marchand, Hugues; Laundy, Richard; Wolsey, Laurence A.: (bc)-(opt): A branch-and-cut code for mixed integer programs (1999)