Hybrid Branching,10.1007/978-3-642-01929-6_23,Tobias Achterberg,Timo Berthold

Hybrid Branching   (Citations: 6)
BibTex | RIS | RefWorks Download
State-of-the-art solvers for Constraint Satisfaction Problems (CSP), Mixed Integer Programs (MIP), and satisfiability problems (SAT) are usually based on a branch-and-bound algorithm. The question how to split a problem into subproblems (branching) is in the core of any branch-and-bound algorithm. Branching on individual variables is very common in CSP, MIP, and SAT. The rules, however, which variable to choose for branching, differ significantly. In this paper, we present hybrid branching, which combines selection rules from all three fields.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...If there is a tie among the top candidates, then a series of secondary criteria should be used to make the final decision [2]...

    Thorsten Kochet al. MIPLIB 2010

    • ...In the truncated first index branching variant, we branch on the first fractional variable xij for which the current LPsolution has no 1 in positions (j, j) ,..., (i − 1 ,j ). If no such variable has been found, we use the standard (strong-)branching rule of scip, see [5]...

    Tim Januschowskiet al. Branch-Cut-and-Propagate for the Maximum

    • ...We use hybrid branching [2] only on integer variables...

    Timo Bertholdet al. A Constraint Integer Programming Approach for Resource-Constrained Pro...

    • ...Achterberg and Berthold [8] propose a hybrid branching scheme for IP that incorporates conflict-based SAT and impact-based CP style search heuri stics as dynamic tie-breakers...
    • ...– each generated conflict constraint is valid for the IP search, – each global bound change can be applied at the IP root node, – each feasible solution can be added to the IP solver’s solution pool, – the branching statistics can initialize a hybrid IP branching rule [8], and – if the CP solver completely solves the problem, the IP solver can abort...

    Timo Bertholdet al. Rapid Learning for Binary Programs

    • ...Motivated, in part, by a conference presentation of our results [28], Achterberg and Berthold [4] suggest hybrid branching, a strategy that combines pseudocosts, inference values, and conflict...

    Fatma Kılınç Karzanet al. Information-based branching schemes for binary linear mixed integer pr...

Sort by: