ON THE COMPUTATIONAL EFFICIENCY OF BRANCH-AND-BOUND ALGORITHMS
スポンサーリンク
概要
- 論文の詳細を見る
The behavior of the number of partial problems T(A) which are decomposed in a branch-and-bound algorithm A (T(A) may be taken as a measure for the computational efficiency of A) is investigated in a fairly general setting. The first result is that the mean number T^~(n) of T(A) when A is applied to problems of size n grows at least as fast as exponentially with n, under relatively mild conditions, if A uses only the lower bound test as most of the conventional branch-and-bound algorithms do. Then it is pointed out that a possible way to avoid this exponential growth is to use the dominance test together with the lower bound test. The dominance test is also interesting from the view point of unifying a wide variety of algorithms as branch-and-bound. These points are exemplified by the well known Dijkstra algorithm for the shortest path problem and the Johnson algorithm for the two-machine flow-shop scheduling problem, for which T^~(n)<le>n-1 holds by virtue of the dominance test.
- 社団法人日本オペレーションズ・リサーチ学会の論文
著者
-
Ibaraki Toshihide
Department Of Applied Mathematics And Physics Faculty Of Engineering Kyoto University
-
IBARAKI TOSHIHIDE
Department of Applied Mathematics and Physics, Faculty of Engineering, Kyoto University
関連論文
- 6B2 AN ITERATED LOCAL SEARCH ALGORITHM FOR THE MULTI-RESOURCE GENERALIZED ASSIGNMENT PROBLEM WITH FLEXIBLE ASSIGNMENT COST(Technical session 6B: General model for scheduling and assignment problem)
- A Simple Proof of a Minimum Cut Algorithm and Its Applications
- A Randomness Based Analysis on the Data Size Needed for Removing Deceptive Patterns
- 4A1 A LOCAL SEARCH ALGORITHM FOR ROUTING AND SCHEDULING PROBLEMS WITH TIME WINDOW AND TRAVELING TIME CONSTRAINTS(Technical session 4A : Vehicle routing)
- A Note on Approximating the Survivable Network Design Problem in Hypergraphs(Special Issue on Selected Papers from LA Symposium)
- An LP-Based Local Search to the One Dimensional Cutting Stock Problem Using a Given Number of Cutting Patterns
- Construction of Classifiers by Iterative Compositions of Features with Partial Knowledge(Discrete Mathematics and Its Applications)
- ALGORITHMS FOR QUADRATIC FRACTIONAL PROGRAMMING PROBLEMS
- A Fast Algorithm for Cactus Representations of Minimum Cuts
- Solving the Single-Vehicle Scheduling Problems for All Home Locations under Depth-First Routing on a Tree (Special Section on Discrete Mathematics and Its Applications)
- VEHICLE SCHEDULING ON A TREE TO MINIMIZE MAXIMUM LATENESS
- 1A1 Scheduling of Corrugated Paper Production(Technical session 1A: Combinatorial optimization)
- A PRIMAL CUTTING PLANE ALGORITHM FOR INTEGER FRACTIONAL PROGRAMMING PROBLEMS
- AN ASSIGNMENT PROBLEM ON A NETWORK
- MINIMUM DELAY SEMIJOIN SCHEDULES FOR LOCAL AREA DISTRIBUTED DATABASE SYSTEMS(Mathematical Theories on Computing Schemes and Their Applications)
- Approximability of the Minimum Maximal Matching Problem in Planar Graphs(Graphs and Networks)
- An Approximation of the Minimum Vertex Cover in a Graph
- Minimum Self-Dual Decompositions of Positive Dual-Minor Boolean Functions
- ON THE COMPUTATIONAL EFFICIENCY OF BRANCH-AND-BOUND ALGORITHMS
- PARTIALLY DEFINED BOOLEAN FUNCTIONS WITH APPLICATIONS TO DATA ANALYSIS : A SURVEY