Explications Contrefactuelles pour le Problème de Couverture par Ensemble, un cas d’étude Radar

Valentin l'Hermite, Yann Briheche, Christophe Labreuche, Rami Kassab, Patrick MeyerSPIRE 2026

This paper, presented at the ROADEF 2026 conference, explores how to make optimization models more "human-friendly" when they fail. Specifically, it applies the concept of Counterfactual Explanations to radar coverage planning, transforming a "computer says no" situation into a constructive negotiation between the operator and the algorithm.

TL;DR

When radar coverage requirements clash with a tight energy budget, standard optimization models simply return "infeasible." This paper proposes a mathematical framework that instead suggests the minimal adjustments—such as reducing coverage in a specific area or slightly increasing the budget—needed to make the plan work.

What Problem Does This Paper Address?

In radar operations, planning is a balancing act. You need to select a set of "dwells" (specific waveforms and durations) to cover various cells in the sky. This is mathematically modeled as a Weighted Set Cover Problem (WSCP): you want to satisfy all coverage demands at the lowest cost (time or energy) while staying within a fixed budget.

The problem arises when the requirements are impossible to meet. Traditional solvers are binary; they either give you an optimal plan or tell you the problem is infeasible. For a radar operator in the field, "infeasible" is useless. They need to know why it failed and what they can change to fix it. Currently, this involves tedious manual trial-and-error. The authors aim to automate this "what-if" analysis.

Methods

The authors extend the classical Mixed Integer Linear Program (MILP) formulation of the Set Cover Problem by introducing Counterfactual Explainability, a concept borrowed from Explainable AI (XAI).

  1. Elastic Variables: They introduce perturbation variables ($\delta$) for every major parameter of the problem:
  2. $\delta^A$: Changes to the coverage matrix (e.g., can a radar dwell reach a bit further?).
  3. $\delta^b$: Changes to the coverage demand (e.g., can we accept less density in one sector?).
  4. $\delta^c$: Changes to the cost of dwells.
  5. $\delta^B$: Changes to the total available budget.
  6. The Counterfactual Objective: Instead of just minimizing cost, the new objective function minimizes the original cost plus a "penalty" for the modifications. This ensures the suggested changes are as small and few as possible.
  7. Linearization: Because multiplying decision variables by these new perturbations creates non-linear "bilinearities," the authors use auxiliary variables and "big-M" constraints to keep the problem solvable using standard linear programming tools.
  8. Domain Constraints: They emphasize that these changes can't be random. For example, a radar dwell can only "expand" its coverage if it's physically possible (correct orientation and range), ensuring the suggestions are realistic.

Datasets

The paper does not utilize a public benchmark dataset. Instead, it is based on a Thales radar use case. The authors focus on the theoretical formulation of the model rather than providing a large-scale empirical evaluation on standardized sets.

Key Insights and Ideas

  • From Optimization to Negotiation: The core shift is moving from "finding the best solution" to "finding the closest feasible world." This turns the optimization tool into a decision-support system.
  • Actionable Insights: The model is designed to produce human-readable advice. Instead of a matrix of numbers, it can output: "Reducing coverage in Area X by 5% or increasing budget by 10% restores feasibility."
  • Physical Grounding: A major insight is that counterfactuals in optimization must respect physical laws. You can't just "tweak" a coverage bit if the radar isn't pointed in that direction. The model incorporates these operational rules into the $\delta^A$ perturbations.

Key Results

As this is a short "work-in-progress" style paper for a conference, it focuses on the mathematical formulation (Equation 4) rather than quantitative performance metrics.

The qualitative result is the demonstration of a framework that can successfully identify which parameters (coverage, cost, or budget) are the "bottlenecks" of a specific scenario. By quantifying the "minimal adjustment," the authors provide a path toward restoring feasibility that was previously a manual, intuitive process for engineers.

Limitations and Future Work

  • Computational Complexity: Adding elastic variables and big-M constraints significantly increases the search space for the MILP solver. The authors will likely need to investigate heuristics or decomposition methods for very large-scale radar grids.
  • Defining "Minimal": The "penalty" function is crucial. Future work will need to determine how to weight different types of changes—is a 5% budget increase "cheaper" than a 2% coverage drop? This likely requires user studies with actual radar operators.
  • Multi-Objective Trade-offs: The current model combines cost and penalties into one objective. Exploring a Pareto front of different counterfactual suggestions could give operators multiple "fix-it" options to choose from.

Summary updated

Abstract

International audience
BibTeX
@inproceedings{lhermite2026explications,
  author = {Valentin l'Hermite and Yann Briheche and Christophe Labreuche and Rami Kassab and Patrick Meyer},
  title = {{Explications Contrefactuelles pour le Problème de Couverture par Ensemble, un cas d’étude Radar}},
  booktitle = {SPIRE},
  year = {2026},
}
Figure