ISSN:
1572-9338
Schlagwort(e):
Branch and bound design
;
tree enumeration strategies
;
discrete nonlinear programs
;
nonlinear integer test problems
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Mathematik
,
Wirtschaftswissenschaften
Notizen:
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.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/BF02022086
Permalink
