On maximum ratio clique relaxations
Abstract
This article introduces and studies two clique relaxation models with fractional objectives: the maximum ratio ‐plex problem and the maximum ratio ‐defective clique problem. The decision version of each problem is shown to be strongly ‐complete; we also discuss some related computational complexity issues. The base optimization models are single‐ratio fractional 0‐1 problems. We describe two general types of solution methods: the first one is based on mixed‐integer linear programs (MILPs) obtained by linearizing the original nonlinear 0‐1 models; the other one exploits parametric methods (namely, a binary search and Newton's method) that solve MILPs in an iterative manner. For the proposed MILPs, we derive valid inequalities that are shown to substantially improve the performance of an off‐the‐shelf MILP solver. Finally, the considered solution approaches are compared via extensive numerical experiments using a set of artificially generated and real‐life network instances.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Apr 15, 2022
- Source ID
- 10.1002/net.22097
Entities
People
- Oleg A. Prokopyev
- Petar Momčilović
- Sergiy Butenko
- Yehor Blokhin
Organizations
- Air Force Office of Scientific Research
- CRDF Global
- National Science Foundation of Sri Lanka
- University of Pittsburgh