A Row Generation Scheme for Finding a Multi-Commodity Minimum Disconnecting Set

The multi-commodity minimum disconnecting set in a given network is of considerable interest in military operations. The present known methods of finding the multi-commodity minimum disconnecting set consist of implicit enumeration techniques or techniques which involve the solution of several specially structured linear integer programs known as set-covering problems. In this paper we present an efficient method of finding the multi-commodity minimum disconnecting set by solving a single set-covering problem. Extensions and computational experience are also discussed.

• 저널Management Science · 23(6) · 652–659
• 토픽Military Defense Systems Analysis · Aerospace Engineering
• DOI10.1287/mnsc.23.6.652
• 저자Y.P. Aneja, R. R. Vemuganti