On cutting planes for cardinality-constrained linear programs

• 成果类型: Article
• 署名作者: Kim, Jinhak; Tawarmalani, Mohit; Richard, Jean-Philippe P.
• 署名单位: University of South Alabama; Purdue University System; Purdue University; State University System of Florida; University of Florida
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-018-1306-0
• 发表日期: 2019
• 页码: 417-448
• 关键词: 0-1 knapsack-problems; lift-and-project; algorithm; selection; cuts; inequalities; FAMILY

摘要

We derive cutting planes for cardinality-constrained linear programs. These inequalities can be used to separate any basic feasible solution of an LP relaxation of the problem, assuming that this solution violates the cardinality requirement. To derive them, we first relax the given simplex tableau into a disjunctive set, expressed in the space of nonbasic variables. We establish that coefficients of valid inequalities for the closed convex hull of this set obey ratios that can be computed directly from the simplex tableau. We show that a transportation problem can be used to separate these inequalities. We then give a constructive procedure to generate violated facet-defining inequalities for the closed convex hull of the disjunctive set using a variant of Prim's algorithm.