Investigating Mixed‐Integer Programming Approaches for the p‐α‐Closest‐Center Problem

In this work, we introduce and study the ‐‐closest‐center problem (CCP), which is a generalization of the ‐second‐center problem, a recently emerged variant of the classical (discrete) p ‐center problem. In the CCP, we are given a discrete set of customers, a discrete set of potential facility locations, distances between each customer and potential facility location as well as two integers and . The goal is to open facilities at of the potential facility locations, such that the maximum ‐distance between each customer and the open facilities is minimized. The ‐distance of a customer is defined as the sum of distances from the customer to its closest open facilities. If is set to one, the CCP is the p ‐center problem, and for being two, the ‐second‐center problem is obtained, for which the only existing algorithm in literature is a variable neighborhood search (VNS). We first prove relationships between the optimal objective function values for different variants of the p ‐center problem to set the CCP in context with existing problems. We then present four mixed‐integer programming (MIP) formulations for the CCP and strengthen them by adding valid and optimality‐preserving inequalities. We also conduct a polyhedral study to prove relationships between the linear programming relaxations of our MIP formulations. Moreover, we present iterative procedures for lifting some valid inequalities to improve initial lower bounds on the optimal objective function value of the CCP and characterize the best lower bounds obtainable by this iterative lifting approach. Based on our theoretical findings, we develop a branch‐and‐cut algorithm (B&C) to solve the CCP exactly. We improve its performance by a starting and a primal heuristic, variable fixings and separating inequalities. In our computational study, we investigate the effect of the various ingredients of our B&C on benchmark instances from related literature. Our B&C is able to prove optimality for 17 of the 40 instances from the work on the VNS heuristic.