ISSN:
1572-9338
Keywords:
Branch and bound design
;
tree enumeration strategies
;
discrete nonlinear programs
;
nonlinear integer test problems
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
,
Economics
Notes:
Abstract This paper is concerned with computational experimentation leading to the design of effective branch and bound algorithms for an important class of nonlinear integer programming problems, namely linearly constrained problems, which are used to model several real-world situations. The main contribution here is a study of the effect of node and branching variable selection and storage reduction strategies on overall computational effort for this class of problems, as well as the generation of a set of adequate test problems. Several node and branching variable strategies are compared in the context of a pure breadth-first enumeration, as well as in a special breadth and depth enumeration combination approach presented herein. Also, the effect of using updated pseudocosts is briefly addressed. Computational experience is presented on a set of eighteen suitably-sized nonlinear test problems, as well as on some random linear integer programs. Some of the new rules proposed are demonstrated to be significantly superior to previously suggested strategies; interestingly, even for linear integer programming problems.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02022086
Permalink
