AND/OR Branch-and-Bound Search for Pure 0/1 Integer Linear Programming Problems

摘要: AND/OR search spaces have recently been introduced as a unifying paradigm for advanced algorithmic schemes graphical models. The main virtue of this representation is its sensitivity to the structure model, which can translate into exponential time savings algorithms. In paper we extend Branch-and-Bound algorithm (AOBB) [1] solving pure 0/1 Integer Linear Programs [2]. Since variable selection dramatic impact on performance, introduce new dynamic able accommodate ordering heuristics. effectiveness approach demonstrated variety benchmarks integer programming, including instances from MIPLIB library, real-world combinatorial auctions and random uncapacitated warehouse location problems.