ERA is in the process of being migrated to Scholaris, a Canadian shared institutional repository service (https://scholaris.ca). Deposits and changes to existing ERA items and collections are frozen until migration is complete. Please contact erahelp@ualberta.ca for further assistance
- 330 views
- 297 downloads
Solving the Sequential Ordering Problem with Automatically Generated Lower Bounds
-
- Author(s) / Creator(s)
-
Technical report TR03-16. The Sequential Ordering Problem (SOP) is a version of the Asymmetric Traveling Salesman Problem (ATSP) where precedence constraints on the vertices must be observed. The SOP has many real life applications and it has proved to be a challenge as there are SOPs of order 40-50 vertices which have not yet been solved optimally with significant computational effort. We use a novel branch&bound search algorithm with lower bounds obtained from homomorphic abstractions of the original state space. Our method is asymptotically optimal. In one instance, it has proved a solution value to be optimal for an open problem while it also has matched best known solutions quickly for many unsolved problems from the TSPLIB. Our method of deriving lower bounds is general and applies to other variants of constrained ATSPs as well. | TRID-ID TR03-16
-
- Date created
- 2003
-
- Subjects / Keywords
-
- Type of Item
- Report
-
- License
- Attribution 3.0 International