Two branch-and-boundalgorithms are analyzed for the problem of the maximum set of pairwise incomparable vertices in a digraph with additional constraints.
Two branch-and-boundalgorithms are analyzed for the problem of the maximum set of pairwise incomparable vertices in a digraph with additional constraints.
The bilevel programming problem (BLPP) is a model of a leader-follower game in which play is sequential and cooperation is not permitted. In the first part of the paper, some basic properties of the general model are ...
详细信息
The bilevel programming problem (BLPP) is a model of a leader-follower game in which play is sequential and cooperation is not permitted. In the first part of the paper, some basic properties of the general model are developed and a conjecture relevant to solution procedures is presented. Next, two algorithms are presented for solving various versions of the game when certain convexity conditions hold. One algorithm relies upon a hybrid branch and bound scheme, and it does not guarantee global optimality. Another is based upon objective function cuts and, barring numerical stability problems with the optimize, is guaranteed to converge to an epsilon-optimal solution. Finally, performance of the two algorithms is examined using randomly generated test problems. The computational performance of the branch and bound algorithm is explored, and the cutting plane algorithm is used to determine whether or not the branch and bound algorithm is uncovering global optima.
An approximate stochastic model of branch-and-boundalgorithms with a best-first search is proposed. The average memory space required is estimated and the average number of subproblems expanded before the process ter...
详细信息
An approximate stochastic model of branch-and-boundalgorithms with a best-first search is proposed. The average memory space required is estimated and the average number of subproblems expanded before the process terminates is predicted. Both of these measures are exponentials of sublinear exponent. In addition, a comparison is made between the number of subproblems expanded in a best-first search and that expanded in a depth-first search. Depth-first search is found to have computational complexity comparable to best-first search when the lower bound function is highly accurate or highly inaccurate; otherwise, the best-fit search is usually preferable. The results derived are useful in examining the efficient evaluation of branch-and-boundalgorithms in a virtual memory environment. They also verify that approximations are very effective in lowering the total number of iterations.
This paper analyzes the applicability and relative efficiency of four pruning rules for finding k -nearest neighbors by a branch and bound algorithm. Results of experimental simulations with various clustering schemes...
详细信息
This paper analyzes the applicability and relative efficiency of four pruning rules for finding k -nearest neighbors by a branch and bound algorithm. Results of experimental simulations with various clustering schemes and data distributions are included.
We consider a production-inventory planning problem with time-varying demands, convex production costs and a warehouse capacity constraint. It is solved by use of the Lagrangian form of the maximum principle. The poss...
详细信息
We consider a production-inventory planning problem with time-varying demands, convex production costs and a warehouse capacity constraint. It is solved by use of the Lagrangian form of the maximum principle. The possible existence of strong decision and forecast horizons is demonstrated. When they exist, they permit the breaking up of the whole problem into a set of smaller problems which can be solved independently because optimal decisions up to a strong decision horizon are completely independent of demand data beyond the next forecast horizon. A forward branch and bound algorithm is developed to determine such horizons and to solve the whole problem.
A new search strategy, called depth-msearch, is proposed for branch-and-boundalgorithms, wheremis a parameter to be set by the user. In particular, depth-1 search is equivalent to the conventional depth-first search,...
详细信息
A new search strategy, called depth-msearch, is proposed for branch-and-boundalgorithms, wheremis a parameter to be set by the user. In particular, depth-1 search is equivalent to the conventional depth-first search, and depth-∞ search is equivalent to the general heuristic search (including best-bound search as a special case). It is confirmed by computational experiment that the performance of depth-msearch continuously changes from that, of depth-first search to that of heuristic search, whenmis changed from 1 to ∞. The exact upper bound on the size of the required memory space is derived and shown to be bounded byO(nm), wherenis the problem size. Some methods for controllingmduring computation are also proposed and compared, to carry out the entire computation within a given memory space bo
暂无评论