Analysis of Decomposition Algorithms with Benders Cuts for p-Median Problem |
| |
Authors: | Alexander Kolokolov Nikolay Kosarev |
| |
Institution: | (1) Omsk Branch of Sobolev Institute of Mathematics, Discrete Optimization Laboratory, Omsk, Russia;(2) Omsk State University, Omsk, Russia |
| |
Abstract: | In this paper the algorithms for solving the p-median problem based on the Benders decomposition are investigated. A family of problems hard for solving with such algorithms is constructed and then generalized to a special NP-hard case of the p-median problem. It is shown that the effectiveness of the considered algorithms depends on the choice of the optimal values of the dual variables used in Benders cuts. In particular, the depth of the cuts can be equal to one. |
| |
Keywords: | p-median problem decomposition algorithms Benders cuts |
本文献已被 SpringerLink 等数据库收录! |