GENERATING CUTS FROM SURROGATE CONSTRAINT ANALYSIS FOR ZERO-ONE AND MULTIPLE-CHOICE PROGRAMMING

This paper presents a new surrogate constraint analysis that gives ris e to a family of strong valid inequalities called surrogate-knapsack ( S-K) cuts. The analytical procedure presented provides a strong S-K cu t subject to constraining the values of selected cut coefficients, inc luding the right-hand side. Our approach is applicable to both zero-on e integer problems and problems having multiple choice (generalized up per bound) constraints. We also develop a strengthening process that f urther tightens the S-K cut obtained via the surrogate analysis. Build ing on this, we develop a polynomial-time separation procedure that su ccessfully generates an S-K cut that renders a given non-integer extre me point infeasible. We show how sequential lifting processes can be v iewed in our framework, and demonstrate that our approach can obtain f acets that are not available to standard lifting methods. We also prov ide a related analysis for generating ''fast cuts''. Finally, we prese nt computational results of the new S-K cuts for solving 0-1 integer p rogramming problems. Our outcomes disclose that the new cuts are capab le of reducing the duality gap between optimal continuous and integer feasible solutions more effectively than standard lifted cover inequal ities, as used in modem codes such as the CPLEX mixed 0-1 integer prog ramming solver.