A Benders decomposition-based reoptimization method to find the best-K fixed-charge network designs

Fixed-charge network design problem (NDP) aims to find the optimal network design under various restrictions. Except for the best network design, real-world applications need to obtain the 2nd, 3rd,…, K th optimal network designs to enrich decision-making. We call this problem network design problem which finds the best K fixed-charge network designs. For finding the k th optimal network design, k−1 constraints that can exclude the 1st, 2nd, …, k−1 th optimal network designs are extended to the design model. We use the Benders decomposition to solve K diverse NDPs sequentially. The generated Benders cuts to produce the best k−1 optimal designs can be used as warm-start cuts to find the k th optimal design. A Benders decomposition-based reoptimization method is developed to take full advantage of previous computational effort. For finding the best 50 designs, 91% of CPU running time and 92% of Benders iterations can be saved by the reoptimization technique.