Generating Cuts from Surrogate Constraint Analysis for Zero-Oneand Multiple Choice Programming

摘要: This paper presents a new surrogate constraint analysis that gives rise to family of strong valid inequalities called surrogate-knapsack (S-K) cuts. The analytical procedure presented provides S-K cut subject constraining the values selected coefficients, including right-hand side. Our approach is applicable both zero-one integer problems and having multiple choice (generalized upper bound) constraints. We also develop strengthening process further tightens obtained via analysis. Building on this, we polynomial-time separation successfully generates an renders given non-integer extreme point infeasible. show how sequential lifting processes can be viewed in our framework, demonstrate obtain facets are not available standard methods. provide related for generating “fast cuts”. Finally, present computational results cuts solving 0-1 programming problems. outcomes disclose capable reducing duality gap between optimal continuous feasible solutions more effectively than lifted cover inequalities, as used modern codes such CPLEX mixed solver.