1141. The Maximum k-Vertex Cover Problem: Polyhedral Structure, Valid Inequalities, and Computational Enhancements
Invited abstract in session TA-17: Modeling and competitive analysis in routing and covering problems, stream Combinatorial Optimization.
Tuesday, 8:30-10:00Room: Esther Simpson 2.08
Authors (first author is the speaker)
| 1. | Shengjie Chen
|
| Academy of Mathematics and Systems Science, Chinese Academy of Sciences | |
| 2. | Yu-Hong Dai
|
| ICMSEC, AMSS,Chinese Academy of Sciences |
Abstract
The maximum k-vertex cover (Max k-VC) problem is a fundamental combinatorial optimization problem that seeks to select at most k vertices in an edge-weighted undirected graph G to maximize the total weight of covered edges. In this paper, we study the polytope associated with an integer programming (IP) formulation of the Max k-VC problem. Some insightful polyhedral properties of the polytope are established. In particular, we demonstrate that certain facet-defining inequalities for the polytope can be derived from those for the projected and low-dimensional polytopes obtained by restricting G to its subgraphs in the associated IP formulation. Exploiting this structural property, we introduce three families of strong valid inequalities based on different subgraph structures, including odd cycles, cliques, and (generalized) stars. We further characterize the necessary and sufficient conditions for these inequalities to be facet-defining and investigate the corresponding separation problems. Finally, we integrate the proposed valid inequalities as cutting planes into the branch-and-bound framework of the IP solver CPLEX. Extensive computational experiments demonstrate the effectiveness of these inequalities in improving solution quality and efficiency, providing both theoretical insights and practical enhancements for solving the Max k-VC problem.
Keywords
- Combinatorial Optimization
- Polyhedral Combinatorics
- Graphs and Networks
Status: accepted
Back to the list of papers