Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(4)
Branch and Bound Algorithm
Constraint Satisfaction Problem
Mixed Integer Program
Satisfiability
Subscribe
Academic
Publications
Hybrid Branching
Hybrid Branching,10.1007/9783642019296_23,Tobias Achterberg,Timo Berthold
Edit
Hybrid Branching
(
Citations: 6
)
BibTex

RIS

RefWorks
Download
Tobias Achterberg
,
Timo Berthold
Stateoftheart solvers for
Constraint Satisfaction
Problems (CSP), Mixed Integer Programs (MIP), and
satisfiability
problems (SAT) are usually based on a branchandbound algorithm. The question how to split a problem into subproblems (branching) is in the core of any branchandbound 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.
Conference:
International Conference on Integration of AI and OR Techniques in Constraint Programming  CPAIOR
, pp. 309311, 2009
DOI:
10.1007/9783642019296_23
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.
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www.informatik.unitrier.de
)
(
dx.doi.org
)
More »
Citation Context
(6)
...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 Koch
,
et 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 Januschowski
,
et al.
BranchCutandPropagate for the Maximum
...We use hybrid branching [
2
] only on integer variables...
Timo Berthold
,
et al.
A Constraint Integer Programming Approach for ResourceConstrained Pro...
...Achterberg and Berthold [
8
] propose a hybrid branching scheme for IP that incorporates conflictbased SAT and impactbased CP style search heuri stics as dynamic tiebreakers...
...– 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 Berthold
,
et 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ç Karzan
,
et al.
Informationbased branching schemes for binary linear mixed integer pr...
References
(5)
SCIP: solving constraint integer programs
(
Citations: 33
)
Tobias Achterberg
Journal:
Mathematical Programming Computation
, vol. 1, no. 1, pp. 141, 2009
Branching rules revisited
(
Citations: 65
)
Tobias Achterberg
,
Thorsten Koch
,
Alexander Martin
Journal:
Operations Research Letters  ORL
, vol. 33, no. 1, pp. 4254, 2005
LookAhead Versus LookBack for Satisfiability Problems
(
Citations: 118
)
Chu Min Li
,
Anbulagan
Conference:
Principles and Practice of Constraint Programming  CP
, pp. 341355, 1997
GRASP: A search algorithm for propositional satisfiability
(
Citations: 598
)
J. P. MarquesSilva
,
Karem A. Sakallah
Journal:
IEEE Transactions on Computers  TC
, vol. 48, no. 5, pp. 506521, 1999
Chaff: Engineering an efficient SAT solver
(
Citations: 1650
)
Matthew W. Moskewicz
,
Conor F. Madigan
,
Ying Zhao
,
Lintao Zhang
,
Sharad Malik
Conference:
Design Automation Conference  DAC
, pp. 530535, 2001
Sort by:
Citations
(6)
MIPLIB 2010
(
Citations: 1
)
Thorsten Koch
,
Tobias Achterberg
,
Erling Andersen
,
Oliver Bastert
,
Timo Berthold
,
Robert E. Bixby
,
Emilie Danna
,
Gerald Gamrath
,
Ambros M. Gleixner
,
Stefan Heinz
,
Andrea Lodi
,
Hans Mittelmann
http://academic.research.microsoft.com/io.ashx?type=5&id=48797514&selfId1=0&selfId2=0&maxNumber=12&query=
Journal:
Mathematical Programming Computation
, vol. 3, no. 2, pp. 103163, 2011
BranchCutandPropagate for the Maximum
Tim Januschowski
,
Marc E. Pfetsch
Conference:
International Conference on Integration of AI and OR Techniques in Constraint Programming  CPAIOR
, pp. 99116, 2011
A Constraint Integer Programming Approach for ResourceConstrained Project Scheduling
(
Citations: 1
)
Timo Berthold
,
Stefan Heinz
,
Marco E. Lübbecke
,
Rolf H. Möhring
,
Jens Schulz
Conference:
International Conference on Integration of AI and OR Techniques in Constraint Programming  CPAIOR
, pp. 313317, 2010
Rapid Learning for Binary Programs
Timo Berthold
,
Thibaut Feydy
,
Peter J. Stuckey
Conference:
International Conference on Integration of AI and OR Techniques in Constraint Programming  CPAIOR
, pp. 5155, 2010
Informationbased branching schemes for binary linear mixed integer problems
(
Citations: 2
)
Fatma Kılınç Karzan
,
George L. Nemhauser
,
Martin W. P. Savelsbergh
Journal:
Mathematical Programming Computation
, vol. 1, no. 4, pp. 249293, 2009