Compact MILP Formulations for the p-Center Problem

Zacharie Alès, Sourour ElloumiISCO 2018 · OpenReview

TL;DR

This paper introduces two novel, more compact Mixed-Integer Linear Programming (MILP) formulations for the classic p-center problem. These new formulations significantly reduce the number of variables and constraints compared to existing methods, leading to faster computation times, especially when combined with a proposed two-step resolution algorithm.

What Problem Does This Paper Address?

The p-center problem is a fundamental challenge in facility location and operations research. The goal is to select a fixed number of facility locations (p) from a larger set of potential sites (M) to serve a set of clients (N), such that the maximum distance from any client to its nearest chosen facility (the "radius") is minimized. This problem has wide-ranging applications, from telecommunications network design to emergency service placement. While exact solutions exist, solving large instances can be computationally expensive due to the complexity of existing mathematical formulations. This paper aims to improve the efficiency of solving the p-center problem by developing more compact and effective MILP formulations.

Methods

The authors propose two new MILP formulations, denoted as (CP₁) and (CP₂).

  • (CP₁) is an improvement upon a previously known formulation (P₂). It achieves compactness by identifying and removing redundant constraints, specifically those related to distances that don't significantly impact the lower bound of the optimal radius. This formulation maintains the same linear relaxation bound as (P₂) but with a reduced number of constraints.
  • (CP₂) is a further simplification that replaces a set of binary variables with a single integer variable. This significantly reduces the number of variables and constraints, making it the most compact formulation presented. However, this compactness comes at the cost of a weaker linear relaxation bound compared to (CP₁) and (P₂).

In addition to the formulations, the paper introduces a two-step resolution algorithm. This algorithm first refines the lower and upper bounds of the optimal radius by iteratively solving the linear relaxation of the chosen formulation and updating bounds based on the results. This process is enhanced by "reduction rules" that remove dominated clients and facilities. The second step then solves the problem to optimality using the improved bounds.

Datasets

The paper evaluates its proposed formulations and algorithm using instances from the OR-Library. Specifically, they use the first 40 instances from the OR-Library for their numerical experiments. No new datasets were introduced.

Key Insights and Ideas

  • Redundancy in Existing Formulations: The paper demonstrates that certain constraints in existing p-center MILP formulations are redundant and can be removed without affecting the quality of the linear relaxation bound. This is a key insight for developing more efficient models.
  • Trade-off Between Compactness and LP Quality: The formulation (CP₂) highlights a common trade-off in optimization modeling: achieving extreme compactness (fewer variables/constraints) can sometimes lead to a weaker linear relaxation, which might require more effort from the solver to reach optimality.
  • Algorithm-Formulation Synergy: The proposed two-step algorithm, when combined with the compact formulations (especially (CP₁)), shows a significant improvement in computation times. This suggests that the effectiveness of a formulation can be greatly amplified by a well-designed solution strategy.
  • Practical Efficiency Gains: The numerical results demonstrate that the new formulations, particularly (CP₁), can solve instances much faster than previous methods, making them more suitable for larger or more complex p-center problems.

Key Results

  • Formulation (CP₁) offers a significant reduction in the number of constraints compared to formulation (P₂), while maintaining the same linear relaxation bound. For instance, on some OR-Library instances, the number of constraints is reduced by a factor of up to N (where N is the number of clients).
  • Formulation (CP₂) is the most compact, with the fewest variables and constraints.
  • When using the proposed two-step resolution algorithm, (CP₁) and (CP₂) solve all 40 OR-Library instances within 1 hour.
  • The algorithm combined with (CP₁) reduces the total computation time by approximately 6 times compared to solving without the algorithm, and (CP₂) achieves a reduction of about 14 times.
  • In terms of solving time for the linear relaxation, (CP₁) is generally much faster than (P₂), and often faster than (CP₂), despite (CP₂) being more compact.

Limitations and Future Work

  • Formulation (CP₂)'s LP Bound: The paper acknowledges that formulation (CP₂) suffers from a weaker linear relaxation bound compared to (CP₁) and (P₂). This can sometimes lead to longer resolution times for the integer problem, even though the formulation itself is more compact.
  • Solver Dependence: While the paper uses CPLEX, the performance of formulations can sometimes be solver-dependent.
  • Future Work: The authors plan to focus on improving their compact formulations through polyhedral studies. This involves deeper analysis of the underlying mathematical structure to potentially derive even tighter formulations or better cutting planes.

Summary updated

Abstract

The p-center problem consists in selecting p centers among M to cover N clients, such that the maximal distance between a client and its closest selected center is minimized. For this problem we propose two new and compact integer formulations.
BibTeX
@inproceedings{ales2018compact,
  author = {Zacharie Alès and Sourour Elloumi},
  title = {{Compact MILP Formulations for the p-Center Problem}},
  booktitle = {ISCO},
  year = {2018},
  url = {https://openreview.net/forum?id=rNyoQw4o3S},
}
Figure