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...
| Main Authors: | , |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/148976 |
| Summary: | 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. |
|---|