Projecting an Extended Formulation for Mixed-Integer Covers on Bipartite Graphs

• 成果类型: Article
• 署名作者: Conforti, Michele; Wolsey, Laurence A.; Zambelli, Giacomo
• 署名单位: University of Padua; Universite Catholique Louvain
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1100.0454
• 发表日期: 2010
• 页码: 603-623
• 关键词: polyhedra

摘要

We consider the mixed-integer version of bipartite vertex cover. This is equivalent to a mixed-integer network dual model, introduced recently, that generalizes several mixed-integer sets arising in production planning. We derive properties of inequalities that are valid for the convex hull of the mixed-integer bipartite covers by projecting an extended formulation onto the space of the original variables. This permits us to give a complete description of the facet-inducing inequalities of the double mixing set and of the continuous mixing set with flows, two mixed-integer sets that generalize several models studied in the literature.