Set Covering and Involutory Bases

Some new properties associated with the special class of integer programs known as weighted set covering problems are derived. While it is well known that an optimal integer solution to the set covering problem is a basic feasible solution to the corresponding linear program, we show that there exists an optimal basis which is involutory (i.e., B = B −1 ). This property and others are used to develop a new algorithm which uses strong cutting planes. The cutting planes are strong in the sense that they exclude both integer and noninteger solutions. Computational experience is presented.

• 저널Management Science · 18(3) · 194–206
• 토픽Vehicle Routing Optimization Methods · Industrial and Manufacturing Engineering
• DOI10.1287/mnsc.18.3.194
• 저자Mandell Bellmore, H. Donald Ratliff