An Efficient Algorithm for Determine the Length of the Longest Dead Path in an "LIFO" Branch-and-bound Exploration Schema
The length of the longest dead path (LLDP) is a widely used parameter in estimating the efficiency of branch-and-bound optimization algorithms that employ the LIFO exploration schema. Thanks to two original theorems, we are able to present a particularly attractive procedure for determining of the L...
| Κύριοι συγγραφείς: | , |
|---|---|
| Έκδοση: |
2023
|
| Διαθέσιμο Online: | https://hdl.handle.net/1721.1/148976 |
| _version_ | 1826206303342559232 |
|---|---|
| author | Pallottino, Stefano Toffoli, Tommaso |
| author_facet | Pallottino, Stefano Toffoli, Tommaso |
| author_sort | Pallottino, Stefano |
| collection | MIT |
| description | The length of the longest dead path (LLDP) is a widely used parameter in estimating the efficiency of branch-and-bound optimization algorithms that employ the LIFO exploration schema. Thanks to two original theorems, we are able to present a particularly attractive procedure for determining of the LLDP. In fact, this procedure requires a number of storage variables which is independent of problem size and very small; moreover, the procedure is self-contained in the sense that it can be externally attached to any LIFO branch-and-bound program without interfering with its algorithms and data structures. |
| first_indexed | 2024-09-23T13:27:19Z |
| id | mit-1721.1/148976 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T13:27:19Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1489762023-03-30T03:38:06Z An Efficient Algorithm for Determine the Length of the Longest Dead Path in an "LIFO" Branch-and-bound Exploration Schema Pallottino, Stefano Toffoli, Tommaso The length of the longest dead path (LLDP) is a widely used parameter in estimating the efficiency of branch-and-bound optimization algorithms that employ the LIFO exploration schema. Thanks to two original theorems, we are able to present a particularly attractive procedure for determining of the LLDP. In fact, this procedure requires a number of storage variables which is independent of problem size and very small; moreover, the procedure is self-contained in the sense that it can be externally attached to any LIFO branch-and-bound program without interfering with its algorithms and data structures. 2023-03-29T14:15:28Z 2023-03-29T14:15:28Z 1980-01 https://hdl.handle.net/1721.1/148976 6312150 MIT-LCS-TM-149 application/pdf |
| spellingShingle | Pallottino, Stefano Toffoli, Tommaso An Efficient Algorithm for Determine the Length of the Longest Dead Path in an "LIFO" Branch-and-bound Exploration Schema |
| title | An Efficient Algorithm for Determine the Length of the Longest Dead Path in an "LIFO" Branch-and-bound Exploration Schema |
| title_full | An Efficient Algorithm for Determine the Length of the Longest Dead Path in an "LIFO" Branch-and-bound Exploration Schema |
| title_fullStr | An Efficient Algorithm for Determine the Length of the Longest Dead Path in an "LIFO" Branch-and-bound Exploration Schema |
| title_full_unstemmed | An Efficient Algorithm for Determine the Length of the Longest Dead Path in an "LIFO" Branch-and-bound Exploration Schema |
| title_short | An Efficient Algorithm for Determine the Length of the Longest Dead Path in an "LIFO" Branch-and-bound Exploration Schema |
| title_sort | efficient algorithm for determine the length of the longest dead path in an lifo branch and bound exploration schema |
| url | https://hdl.handle.net/1721.1/148976 |
| work_keys_str_mv | AT pallottinostefano anefficientalgorithmfordeterminethelengthofthelongestdeadpathinanlifobranchandboundexplorationschema AT toffolitommaso anefficientalgorithmfordeterminethelengthofthelongestdeadpathinanlifobranchandboundexplorationschema AT pallottinostefano efficientalgorithmfordeterminethelengthofthelongestdeadpathinanlifobranchandboundexplorationschema AT toffolitommaso efficientalgorithmfordeterminethelengthofthelongestdeadpathinanlifobranchandboundexplorationschema |