Branch and peg algorithms for the simple plant location problem Export

@article{citeulike:3498837, abstract = {The simple plant location problem is a well-studied problem in combinatorial optimization. It is one of deciding where to locate a set of plants so that a set of clients can be supplied by them at the minimum cost. This problem often appears as a subproblem in other combinatorial problems. Several branch and bound techniques have been developed to solve these problems. In this paper we present two techniques that enhance the performance of branch and bound algorithms. The new algorithms thus obtained are called branch and peg algorithms, where pegging refers to fixing values of variables at each subproblem in the branch and bound tree, and is distinct from variable fixing during the branching process. We present exhaustive computational experiments which show that the new algorithms generate less than 60\% of the number of subproblems generated by branch and bound algorithms, and in certain cases require less than 10\% of the execution times required by branch and bound algorithms.}, address = {Oxford, UK, UK}, author = {Goldengorin, Boris and Ghosh, Diptesh and Sierksma, Gerard}, citeulike-article-id = {3498837}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=762130.762132}, citeulike-linkout-1 = {http://dx.doi.org/10.1016/S0305-0548(02)00049-7}, doi = {10.1016/S0305-0548(02)00049-7}, issn = {0305-0548}, journal = {Comput. Oper. Res.}, keywords = {article, masters, pegging, resourceallocation}, number = {7}, pages = {967--981}, posted-at = {2008-11-09 20:58:50}, priority = {0}, publisher = {Elsevier Science Ltd.}, title = {Branch and peg algorithms for the simple plant location problem}, url = {http://dx.doi.org/10.1016/S0305-0548(02)00049-7}, volume = {30}, year = {2003} }

TY - JOUR ID - citeulike:3498837 L3 - citeulike-article-id:3498837 N2 - The simple plant location problem is a well-studied problem in combinatorial optimization. It is one of deciding where to locate a set of plants so that a set of clients can be supplied by them at the minimum cost. This problem often appears as a subproblem in other combinatorial problems. Several branch and bound techniques have been developed to solve these problems. In this paper we present two techniques that enhance the performance of branch and bound algorithms. The new algorithms thus obtained are called branch and peg algorithms, where pegging refers to fixing values of variables at each subproblem in the branch and bound tree, and is distinct from variable fixing during the branching process. We present exhaustive computational experiments which show that the new algorithms generate less than 60% of the number of subproblems generated by branch and bound algorithms, and in certain cases require less than 10% of the execution times required by branch and bound algorithms. IS - 7 JF - Comput. Oper. Res. SN - 0305-0548 AD - Oxford, UK, UK EP - 981 TI - Branch and peg algorithms for the simple plant location problem PB - Elsevier Science Ltd. VL - 30 SP - 967 KW - article KW - masters KW - pegging KW - resourceallocation AU - Goldengorin, Boris AU - Ghosh, Diptesh AU - Sierksma, Gerard PY - 2003/// UR - http://dx.doi.org/10.1016/S0305-0548(02)00049-7 ER -