### Characterization and Theoretical Comparison of Branch-and-Bound Algorithms for Permutation ProblemsCharacterization and Theoretical Comparison of Branch-and-Bound Algorithms for Permutation Problems

Access Restriction
Subscribed

 Author Kohler, Walter H. ♦ Steiglitz, Kenneth Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1974 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract Branch-and-bound implicit enumeration algorithms for permutation problems (discrete optimization problems where the set of feasible solutions is the permutation group $\textit{Sn})$ are characterized in terms of a sextuple (Bp S,E,D,L,U), where (1) $\textit{Bp}$ is the branching rule for permutation problems, (2) $\textit{S}$ is the next node selection rule, (3) $\textit{E}$ is the set of node elimination rules, (4) $\textit{D}$ is the node dominance function, (5) $\textit{L}$ is the node lower-bound cost function, and (6) $\textit{U}$ is an upper-bound solution cost. A general algorithm based on this characterization is presented and the dependence of the computational requirements on the choice of algorithm parameters, S, E, D, L, and $\textit{U}$ is investigated theoretically. The results verify some intuitive notions but disprove others. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1974-01-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 21 Issue Number 1 Page Count 17 Starting Page 140 Ending Page 156

#### Open content in new tab

Source: ACM Digital Library