Optimization Online


Facets of the Total Matching Polytope for bipartite graphs

Luca Ferrarini(l.ferrarini3***at***campus.unimib.it)

Abstract: The Total Matching Polytope generalizes the Stable Set Polytope and the Matching Polytope. In this paper, we give the perfect formulation for Trees and we derive two new families of valid inequalities, the balanced biclique inequalities which are always facet-defining and the non-balanced lifted biclique inequalities obtained by a lifting procedure, which are facet-defining for bipartite graphs. Finally, we give a complete description for Complete Bipartite Graphs.

Keywords: Integer Programming, Combinatorial Optimization, Total Matching, Polyhedral Combinatorics

Category 1: Combinatorial Optimization

Category 2: Integer Programming (0-1 Programming )

Category 3: Integer Programming (Cutting Plane Approaches )


Download: [PDF]

Entry Submitted: 12/06/2021
Entry Accepted: 12/06/2021
Entry Last Modified: 12/06/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society