A Procedure for Computing the <i>K</i> Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem

TLDR

Finding K best solutions to discrete optimization problems typically requires O(K n c(n)) computation, and the proposed procedure generalizes existing methods such as Murty’s for assignment and Yen’s for shortest path. The authors aim to provide a general procedure for computing the K best solutions to discrete optimization problems and to reduce storage requirements by a factor of n compared to existing algorithms. The procedure computes successive best solutions by extending the optimal solution space and employs a storage‑saving technique that cuts memory usage by a factor of n relative to Murty’s and Yen’s algorithms. The method achieves O(K n³) time for computing the K shortest loopless paths in an n‑node network with positive and negative arcs, improving Yen’s algorithm by a factor of n.

Abstract

A general procedure is presented for computing the best, 2nd best,…, Kth best solutions to a given discrete optimization problem. If the number of computational steps required to find an optimal solution to a problem with n(0, 1) variables is c(n), then the amount of computation required to obtain the if best solutions is O(K nc (n)). The procedure specializes to published procedures of Murty and of Yen for the assignment problem and the shortest path problem, respectively. A method is presented for reducing the required amount of storage by a factor of n, compared with the algorithms of Murty and of Yen. It is shown how the K shortest (loopless) paths in an n-node network with positive and negative arcs can be computed with an amount of computation which is O(Kn 3 ). This represents an improvement by a factor of n, compared with Yen's algorithm.