Resolution Search and Dynamic Branch-and-Bound

被引：0

作者：

Saïd Hanafi

Fred Glover

机构：

[1] Université de Valenciennes et du Hainaut-Cambrésis,Unité de Recherche Opérationnelle et d'Aide à la Décision

[2] Le Mont Houy,Hearin Center for Enterprise Science, School of Business Administration

[3] University of Mississippi,undefined

来源：

Journal of Combinatorial Optimization | 2002年 / 6卷

关键词：

branch-and-bound; dynamic branch-and-bound; resolution search; mixed integer programming;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

A novel approach to pure 0-1 integer programming problems called Resolution Search has been proposed by Chvatal (Discrete Applied Mathematics, vol. 73, pp. 81–99, 1997) as an alternative to implicit enumeration, with a demonstration that the method can yield more effective branching strategies. We show that an earlier method called Dynamic Branch-and-Bound (B&B) yields the same branching strategies as Resolution Search, and other strategic alternatives in addition. Moreover, Dynamic B&B is not restricted to pure 0-1 problems, but applies to general mixed integer programs containing both general integer and continuous variables.

引用

页码：401 / 423

页数：22

共 50 条

[41] A branch-and-bound algorithm for hardware/software partitioning
Wu, JG
Thambipillai, S
PROCEEDINGS OF THE FOURTH IEEE INTERNATIONAL SYMPOSIUM ON SIGNAL PROCESSING AND INFORMATION TECHNOLOGY, 2004, : 526 - 529
[42] A Branch-and-Bound Algorithm for the Talent Scheduling Problem
Liang, Xiaocong
Zhang, Zizhen
Qin, Hu
Guo, Songshan
Lim, Andrew
MODERN ADVANCES IN APPLIED INTELLIGENCE, IEA/AIE 2014, PT I, 2014, 8481 : 208 - 217
[43] Performance of convex underestimators in a branch-and-bound framework
Guzman, Yannis A.
Hasan, M. M. Faruque
Floudas, Christodoulos A.
OPTIMIZATION LETTERS, 2016, 10 (02) : 283 - 308
[44] Performance of convex underestimators in a branch-and-bound framework
Yannis A. Guzman
M. M. Faruque Hasan
Christodoulos A. Floudas
Optimization Letters, 2016, 10 : 283 - 308
[45] Constrained branch-and-bound algorithm for image registration
金剑秋
王章野
彭群生
Journal of Zhejiang University-Science A(Applied Physics & Engineering), 2005, (S1) : 94 - 99
[46] A branch-and-bound algorithm for the coupled task problem
József Békési
Gábor Galambos
Michael N. Jung
Marcus Oswald
Gerhard Reinelt
Mathematical Methods of Operations Research, 2014, 80 : 47 - 81
[47] Dynamic and Hierarchical Load-Balancing Techniques Applied to Parallel Branch-and-Bound Methods
Herrera, Juan F. R.
Casado, Leocadio G.
Hendrix, Eligius M. T.
Paulavicius, Remigijus
Zilinskas, Julius
2013 EIGHTH INTERNATIONAL CONFERENCE ON P2P, PARALLEL, GRID, CLOUD AND INTERNET COMPUTING (3PGCIC 2013), 2013, : 497 - 502
[48] Search pruning techniques in SAT-based branch-and-bound algorithms for the binate covering problem
Manquinho, VM
Marques-Silva, JP
IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 2002, 21 (05) : 505 - 516
[49] Solving the minimum-cost satisfiability problem using SAT based branch-and-bound search
Fu, Zhaohui
Malik, Sharad
IEEE/ACM INTERNATIONAL CONFERENCE ON COMPUTER-AIDED DESIGN, DIGEST OF TECHNICAL PAPERS, ICCAD, 2006, : 106 - +
[50] A Penalty Branch-and-Bound Method for Mixed Binary Linear Complementarity Problems
De Santis, Marianna
de Vries, Sven
Schmidt, Martin
Winkel, Lukas
INFORMS JOURNAL ON COMPUTING, 2022, 34 (06) : 3117 - 3133

← 1 2 3 4 5 →