@misc{Gamrath, type = {Master Thesis}, author = {Gamrath, Gerald}, title = {Generic Branch-Cut-and-Price}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-57543}, pages = {208}, abstract = {In this thesis, we present the theoretical background, implementational details and computational results concerning the generic branch-cut-and-price solver GCG.}, language = {en} } @article{KochAchterbergAndersenetal.2011, author = {Koch, Thorsten and Achterberg, Tobias and Andersen, Erling and Bastert, Oliver and Berthold, Timo and Bixby, Robert E. and Danna, Emilie and Gamrath, Gerald and Gleixner, Ambros and Heinz, Stefan and Lodi, Andrea and Mittelmann, Hans and Ralphs, Ted and Salvagnin, Domenico and Steffy, Daniel and Wolter, Kati}, title = {MIPLIB 2010}, series = {Mathematical Programming Computation}, volume = {3}, journal = {Mathematical Programming Computation}, number = {2}, doi = {10.1007/s12532-011-0025-9}, pages = {103 -- 163}, year = {2011}, language = {en} } @article{Gamrath2013, author = {Gamrath, Gerald}, title = {Improving strong branching by propagation}, series = {Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems}, volume = {7874}, journal = {Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems}, editor = {Gomes, Carla and Sellmann, Meinolf}, publisher = {Springer Berlin Heidelberg}, doi = {10.1007/978-3-642-38171-3_25}, pages = {347 -- 354}, year = {2013}, abstract = {Strong branching is an important component of most variable selection rules in branch-and-bound based mixed-integer linear programming solvers. It predicts the dual bounds of potential child nodes by solving auxiliary LPs and thereby helps to keep the branch-and-bound tree small. In this paper, we describe how these dual bound predictions can be improved by including domain propagation into strong branching. Computational experiments on standard MIP instances indicate that this is beneficial in three aspects: It helps to reduce the average number of LP iterations per strong branching call, the number of branch-and-bound nodes, and the overall solving time.}, language = {en} } @misc{GamrathKochMartinetal., author = {Gamrath, Gerald and Koch, Thorsten and Martin, Alexander and Miltenberger, Matthias and Weninger, Dieter}, title = {Progress in Presolving for Mixed Integer Programming}, issn = {1438-0064}, doi = {10.1007/s12532-015-0083-5}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42530}, abstract = {Presolving attempts to eliminate redundant information from the problem formulation and simultaneously tries to strengthen the formulation. It can be very effective and is often essential for solving instances. Especially for mixed integer programming problems, fast and effective presolving algorithms are very important. In this paper, we report on three new presolving techniques. The first method searches for singleton continuous columns and tries to fix the corresponding variables. Then we present a presolving technique which exploits a partial order of the variables to induce fixings. Finally, we show an approach based on connected components in graphs. Our computational results confirm the profitable use of the algorithms in practice.}, language = {en} } @misc{Gamrath, author = {Gamrath, Gerald}, title = {Improving strong branching by domain propagation}, issn = {1438-0064}, doi = {10.1007/s13675-014-0021-8}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42546}, abstract = {One of the essential components of a branch-and-bound based mixed-integer linear programming (MIP) solver is the branching rule. Strong branching is a method used by many state-of-the-art branching rules to select the variable to branch on. It precomputes the dual bounds of potential child nodes by solving auxiliary linear programs (LPs) and thereby helps to take good branching decisions that lead to a small search tree. In this paper, we describe how these dual bound predictions can be improved by including domain propagation into strong branching. Domain propagation is a technique usually used at every node of the branch-and-bound tree to tighten the local domains of variables. Computational experiments on standard MIP instances indicate that our improved strong branching method significantly improves the quality of the predictions and causes almost no additional effort. For a full strong branching rule, we are able to obtain substantial reductions of the branch-and-bound tree size as well as the solving time. Moreover, also the state-of-the-art hybrid branching rule can be improved this way. This paper extends previous work by the author published in the proceedings of the CPAIOR 2013.}, language = {en} } @article{Gamrath, author = {Gamrath, Gerald}, title = {Improving strong branching by domain propagation}, series = {EURO Journal on Computational Optimization}, volume = {2}, journal = {EURO Journal on Computational Optimization}, number = {3}, publisher = {Springer}, address = {Berlin Heidelberg}, doi = {10.1007/s13675-014-0021-8}, pages = {99 -- 122}, abstract = {One of the essential components of a branch-and-bound based mixed-integer linear programming (MIP) solver is the branching rule. Strong branching is a method used by many state-of-the-art branching rules to select the variable to branch on. It precomputes the dual bounds of potential child nodes by solving auxiliary linear programs (LPs) and thereby helps to take good branching decisions that lead to a small search tree. In this paper, we describe how these dual bound predictions can be improved by including domain propagation into strong branching. Domain propagation is a technique MIP solvers usually apply at every node of the branch-and-bound tree to tighten the local domains of variables. Computational experiments on standard MIP instances indicate that our improved strong branching method significantly improves the quality of the predictions and causes almost no additional effort. For a full strong branching rule, we are able to obtain substantial reductions of the branch-and-bound tree size as well as the solving time. Moreover, the state-of-the-art hybrid branching rule can be improved this way as well. This paper extends previous work by the author published in the proceedings of the CPAIOR 2013.}, language = {en} } @misc{GamrathKochRehfeldtetal., author = {Gamrath, Gerald and Koch, Thorsten and Rehfeldt, Daniel and Shinano, Yuji}, title = {SCIP-Jack - A massively parallel STP solver}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-52293}, abstract = {In this article we describe the impact from embedding a 15 year old model for solving the Steiner tree problem in graphs in a state-of-the-art MIP-Framework, making the result run in a massively parallel environment and extending the model to solve as many variants as possible. We end up with a high-perfomance solver that is capable of solving previously unsolved instances and, in contrast to its predecessor, is freely available for academic research.}, language = {en} } @inproceedings{GamrathMelchioriBertholdetal., author = {Gamrath, Gerald and Melchiori, Anna and Berthold, Timo and Gleixner, Ambros and Salvagnin, Domenico}, title = {Branching on Multi-aggregated Variables}, series = {Integration of AI and OR Techniques in Constraint Programming. CPAIOR 2015}, volume = {9075}, booktitle = {Integration of AI and OR Techniques in Constraint Programming. CPAIOR 2015}, doi = {10.1007/978-3-319-18008-3_10}, pages = {141 -- 156}, abstract = {In mixed-integer programming, the branching rule is a key component to a fast convergence of the branch-and-bound algorithm. The most common strategy is to branch on simple disjunctions that split the domain of a single integer variable into two disjoint intervals. Multi-aggregation is a presolving step that replaces variables by an affine linear sum of other variables, thereby reducing the problem size. While this simplification typically improves the performance of MIP solvers, it also restricts the degree of freedom in variable-based branching rules. We present a novel branching scheme that tries to overcome the above drawback by considering general disjunctions defined by multi-aggregated variables in addition to the standard disjunctions based on single variables. This natural idea results in a hybrid between variable- and constraint-based branching rules. Our implementation within the constraint integer programming framework SCIP incorporates this into a full strong branching rule and reduces the number of branch-and-bound nodes on a general test set of publicly available benchmark instances. For a specific class of problems, we show that the solving time decreases significantly.}, language = {en} } @incollection{GamrathBertholdHeinzetal., author = {Gamrath, Gerald and Berthold, Timo and Heinz, Stefan and Winkler, Michael}, title = {Structure-Based Primal Heuristics for Mixed Integer Programming}, series = {Optimization in the Real World}, volume = {13}, booktitle = {Optimization in the Real World}, publisher = {Springer Japan}, isbn = {978-4-431-55419-6}, doi = {10.1007/978-4-431-55420-2_3}, pages = {37 -- 53}, abstract = {Primal heuristics play an important role in the solving of mixed integer programs (MIPs). They help to reach optimality faster and provide good feasible solutions early in the solving process. In this paper, we present two new primal heuristics which take into account global structures available within MIP solvers to construct feasible solutions at the beginning of the solving process. These heuristics follow a large neighborhood search (LNS) approach and use global structures to define a neighborhood that is with high probability significantly easier to process while (hopefully) still containing good feasible solutions. The definition of the neighborhood is done by iteratively fixing variables and propagating these fixings. Thereby, fixings are determined based on the predicted impact they have on the subsequent domain propagation. The neighborhood is solved as a sub-MIP and solutions are transferred back to the original problem. Our computational experiments on standard MIP test sets show that the proposed heuristics find solutions for about every third instance and therewith help to improve the average solving time.}, language = {en} } @misc{GamrathMelchioriBertholdetal., author = {Gamrath, Gerald and Melchiori, Anna and Berthold, Timo and Gleixner, Ambros and Salvagnin, Domenico}, title = {Branching on multi-aggregated variables}, issn = {1438-0064}, doi = {10.1007/978-3-319-18008-3_10}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-53829}, abstract = {In mixed-integer programming, the branching rule is a key component to a fast convergence of the branch-and-bound algorithm. The most common strategy is to branch on simple disjunctions that split the domain of a single integer variable into two disjoint intervals. Multi-aggregation is a presolving step that replaces variables by an affine linear sum of other variables, thereby reducing the problem size. While this simplification typically improves the performance of MIP solvers, it also restricts the degree of freedom in variable-based branching rules. We present a novel branching scheme that tries to overcome the above drawback by considering general disjunctions defined by multi-aggregated variables in addition to the standard disjunctions based on single variables. This natural idea results in a hybrid between variable- and constraint-based branching rules. Our implementation within the constraint integer programming framework SCIP incorporates this into a full strong branching rule and reduces the number of branch-and-bound nodes on a general test set of publicly available benchmark instances. For a specific class of problems, we show that the solving time decreases significantly.}, language = {en} }