# Regional Coverage CELF Submodular Solver

This solver is a runnable reproduced solver for `regional_coverage`. It is `READY` as a faithful CELF/CEF reproduction adapted to the benchmark's fixed candidate coverage model, with explicit compute-envelope, schedule, repair, and fixed-set bound evidence. It is also `READY_QUALITY_FAIR` for the stronger claim of faithful benchmark-adapted reproduction under a meaningful quality-seeking fixed-candidate optimization envelope: the promoted `main_solver` `quality_probe_stride150_full` profile uses the strongest fixed candidate grid, schedule-aware CELF/CEF, bounded local improvement, and deterministic parallel throughput while staying within its runtime gate.

It follows the CELF and CEF method family described by Leskovec, Krause, Guestrin, Faloutsos, VanBriesen, and Glance in "Cost-effective Outbreak Detection in Networks", adapted to the benchmark's public strip-observation case and solution contract.

## Citation

```bibtex
@inproceedings{leskovec2007cost,
  title={Cost-effective outbreak detection in networks},
  author={Leskovec, Jure and Krause, Andreas and Guestrin, Carlos and Faloutsos, Christos and VanBriesen, Jeanne and Glance, Natalie},
  booktitle={Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
  pages={420--429},
  year={2007},
  doi={10.1145/1281192.1281239}
}

@article{nemhauser1978analysis,
  title={An analysis of approximations for maximizing submodular set functions---I},
  author={Nemhauser, George L. and Wolsey, Laurence A. and Fisher, Marshall L.},
  journal={Mathematical Programming},
  volume={14},
  number={1},
  pages={265--294},
  year={1978},
  doi={10.1007/BF01588971}
}

@article{khuller1999budgeted,
  title={The budgeted maximum coverage problem},
  author={Khuller, Samir and Moss, Anna and Naor, Joseph},
  journal={Information Processing Letters},
  volume={70},
  number={1},
  pages={39--45},
  year={1999},
  doi={10.1016/S0020-0190(99)00031-9}
}
```

The solver is standalone. It reads benchmark case files and writes a benchmark solution JSON, but it does not import or execute benchmark, experiment, runtime, or other solver internals.

## Method Summary

The paper models outbreak detection as monotone submodular reward maximization
over selected sensors or information sources:

- each element is a candidate node to select
- each scenario receives reward once it is detected by at least one selected
  element
- greedy selection adds the element with highest marginal reward
- CELF avoids most naive greedy recomputations by lazily refreshing stale
  marginal gains only when an element reaches the priority-queue head
- CEF handles nonuniform costs by running both unit-cost greedy and
  benefit-per-cost greedy, then returning the higher-reward solution

This reproduction keeps that shape and adapts it to `regional_coverage`:

- element: one fixed timed `strip_observation` candidate
- scenario/item: one public coverage-grid sample index
- reward: unique weighted sample coverage over fixed candidate sample sets
- unit-cost policy: marginal weighted coverage
- cost-benefit policy: marginal weighted coverage divided by configured cost
- final CEF policy: higher objective value among unit-cost and cost-benefit
  lazy greedy outputs
- online evidence: Section 3.2 upper bound over the same fixed candidate set
  after CELF selection

## Benchmark Adaptation

The benchmark differs from the paper in several important ways:

- The paper selects abstract sensors on a graph; the benchmark requires timed
  satellite actions with roll, duration, slew, power, duty, and horizon rules.
- The paper's reward can model detection likelihood, detection time, or
  population affected; this solver uses the benchmark-facing unique weighted
  coverage of public grid samples.
- The paper's budget is an abstract selection budget; this solver maps it to
  `max_actions_total` unless an explicit solver selection budget is configured.
- Nonuniform cost is optional. Supported cost modes are action count, imaging
  time, estimated imaging energy, and a simple roll transition burden.
- Candidate geometry is solver-local and approximate. It uses public TLEs,
  Brahe SGP4 propagation, roll-only WGS84 ray hits, and coverage-grid samples.
  Official region geometry, validity, and scoring remain benchmark-owned.
- Schedule feasibility is not part of the paper's pure set-selection model, so
  this solver uses a schedule-aware CELF acceptance check as a benchmark
  adaptation and reports any post-selection repair separately.
- The online bound is computed only for the finite benchmark-adapted candidate
  universe generated by the solver. It does not certify optimality over
  arbitrary continuous schedules or verifier-side geometry.

The schedule-aware selection stage rejects candidates that would make the
current selected fixed-candidate sequence violate action caps, public strip
shape rules, same-satellite half-open interval overlap, benchmark-style
bang-coast-bang slew plus settling, or conservative battery/duty risk. The
repair stage remains as a deterministic safety net and removes any remaining
conflicting candidates by lowest estimated unique coverage loss, then higher
energy burden, duration, start offset, and candidate id.

## Solver Contract

```bash
./setup.sh
./solve.sh <case_dir> [config_dir] [solution_dir]
```

`setup.sh` verifies that the project environment can import `yaml`.

`solve.sh` writes:

- `solution.json`: primary benchmark solution, with a top-level `actions` array
  of `strip_observation` actions
- `status.json`: case parsing, candidate generation, coverage mapping, CELF,
  repair, reproduction, output policy, and timing summaries
- `candidate_debug.json`: root-level sample of generated candidates and their
  mapped sample coverage
- `debug/*`: detailed debug artifacts described below

## Configuration

The solver reads optional configuration from `<config_dir>/config.yaml`.

See [config.example.yaml](./config.example.yaml) for a commented example.

Candidate-generation knobs:

- `time_stride_s`: start-time stride over the public action grid
- `roll_step_deg`: default symmetric roll-grid spacing
- `max_candidates_total`: deterministic candidate cap; `null` disables it
- `cap_strategy`: `balanced_stride` evenly samples the stable full candidate
  grid, while `first_n` keeps the legacy prefix behavior for debugging
- `duration_values_s`: optional explicit strip durations
- `roll_values_deg`: optional explicit roll values
- `debug_candidate_limit`: number of candidates copied to `candidate_debug.json`

Coverage-mapping knobs:

- `method`: `indexed` builds a sparse solver-local grid over public coverage
  samples; `simple` scans all samples and is kept for debugging/equivalence
  tests
- `spatial_bin_deg`: longitude/latitude bin size used by the indexed mapper
- `worker_count`: serial integer worker count or `auto` for experiment-owned
  heavy policies
- `chunk_size`: deterministic contiguous candidate chunk size for parallel
  mapping

Selection knobs:

- `run_unit_cost`: run the CELF unit-cost greedy variant
- `run_cost_benefit`: run the CELF benefit-per-cost greedy variant
- `cost_mode`: `action_count`, `imaging_time`, `estimated_energy`, or
  `transition_burden`
- `budget`: optional explicit selection budget; `null` uses benchmark
  `max_actions_total`
- `min_marginal_gain`: stop threshold for accepting candidates
- `schedule_aware`: accept only candidates that keep the current fixed
  candidate schedule solver-local feasible
- `local_improvement`: enable the bounded fixed-candidate insertion/swap pass
  after CELF and before deterministic repair
- `local_improvement_max_passes`: maximum accepted local-improvement moves
- `local_improvement_max_candidate_checks`: maximum positive fixed candidates
  considered per local-improvement pass
- `local_improvement_worker_count`: serial integer worker count or `auto` for
  deterministic parallel move evaluation
- `local_improvement_chunk_size`: deterministic candidate chunk size for
  local-improvement move evaluation
- `compute_online_bounds`: compute Leskovec Section 3.2 fixed-set upper-bound
  evidence for each enabled CELF variant
- `max_bound_order_debug`: maximum bound-ordering rows retained in debug
  summaries
- `write_iteration_trace`: write `debug/celf_iterations.jsonl`
- `max_iteration_debug`: maximum recompute/accept/reject rows to keep per
  CELF variant

The promoted public configuration is `quality_probe_stride150_full`: a 518400-candidate fixed grid with 150-second start spacing, schedule-aware CELF/CEF, bounded local improvement, and deterministic parallel coverage/local-improvement throughput. Users may still tune `config.yaml` for local experiments, but the public profile and reported evidence use this single strongest configuration.

## Debug Artifacts

The solver writes:

- `debug/candidate_summary.json`: candidate counts, active caps, per-satellite,
  per-roll, and per-duration histograms
- `debug/coverage_runtime_summary.json`: coverage mapping execution model,
  spatial-index size, sample-check counters, and prefilter reduction ratio
- `debug/celf_summary.json`: algorithm metadata, selected ids, objective value,
  covered sample count, true marginal recomputations, estimated naive
  recomputation bound, lazy savings, stale pops, schedule infeasibility skips,
  fixed-set online bound, and CEF comparison result
- `debug/celf_iterations.jsonl`: bounded trace of recompute, accept,
  nonpositive-reject, and infeasible-skip events when enabled
- `debug/selected_candidates.json`: candidates selected before schedule repair
- `debug/feasibility_summary.json`: before/after validity flags and issue
  counts for solver-local schedule checks
- `debug/repair_log.json`: deterministic removal reasons and estimated unique
  coverage loss
- `debug/repair_objective_summary.json`: pre-repair CELF objective,
  post-repair solver-local objective, and repair loss
- `debug/repaired_candidates.json`: candidates remaining after repair
- `debug/reproduction_summary.json`: paper-faithful elements,
  paper-to-benchmark adaptations, known fidelity limits, and selection audit

Useful checks:

- If `estimated_lazy_recomputations_saved` is zero on a tiny unit test, the
  lazy queue is not demonstrating CELF behavior.
- If `zero_coverage_count` equals `candidate_count`, inspect solver-local
  candidate geometry, roll values, candidate cap balance, and coverage-grid
  placement.
- If repair removes many actions, inspect `repair_log.json` and the CELF
  `infeasible_skip_counts`; the bottleneck is likely a gap between solver-local
  schedule-aware acceptance and the remaining repair safety net.

## Running It

Direct setup:

```bash
./solvers/regional_coverage/celf_submodular/setup.sh
```

Direct solve on a public smoke case:

```bash
./solvers/regional_coverage/celf_submodular/solve.sh \
  benchmarks/regional_coverage/dataset/cases/test/case_0001
```

Direct solve with a config directory:

```bash
./solvers/regional_coverage/celf_submodular/solve.sh \
  benchmarks/regional_coverage/dataset/cases/test/case_0001 \
  /path/to/config_dir \
  /tmp/regional_coverage_celf_solution
```

Official quality-ready profile:

```bash
uv run python experiments/main_solver/run.py \
  --benchmark regional_coverage \
  --solver regional_coverage_celf_submodular \
  --policy quality_probe_stride150_full
```

Aggregate experiment results:

```bash
uv run python experiments/main_solver/aggregate.py
```

## Sanity Baseline

The paper's theoretical baselines apply to fixed monotone submodular selection,
not directly to verifier-scored satellite schedules. Treat them as algorithmic
sanity checks:

- unit-cost greedy should match naive greedy on small fixed-candidate tests
- CELF should use no more marginal recomputations than naive greedy, and should
  save recomputations on cases with stale-but-still-dominant queue heads
- cost-benefit greedy can differ from unit-cost greedy when configured costs
  differ
- the final CEF result should be the higher-reward solution among the enabled
  unit-cost and cost-benefit variants
- the Section 3.2 online bound should be no smaller than the selected fixed-set
  reward and should report the residual-budget marginal-per-cost ordering used
  to form the bound

For benchmark runs, official verification is the validity gate and verifier
metrics are the scoring evidence. The fixed-set online bound is an algorithmic
certificate for the generated candidate universe; it does not replace verifier
metrics.

## Verified Evidence

The single promoted public profile is `quality_probe_stride150_full`. Latest official quality evidence on `test/case_0001` shows:

- 518400 fixed candidates on a 150-second start grid
- 998 nonzero solver-local candidates
- 64 selected and repaired actions
- 7 bounded local-improvement swaps
- repair objective loss ratio `0.0`
- verifier coverage ratio `0.905533`
- verifier weighted coverage ratio `0.897791`
- solver time about `73.8` seconds, below the `420` second runtime gate
- coverage mapping `parallel_fork` with 16 workers and 127 chunks
- local improvement `parallel_fork` with 16 workers and 472 chunks

The quality-ready claim remains scoped to the fixed candidate set and experiment-owned verification on `test/case_0001`; it does not certify continuous-schedule optimality or all regional-coverage cases.

## Known Limitations

- This is a reproduction of the CELF/CEF method family with fixed-set online
  bound evidence, not a reproduction of every experiment table from the paper.
- The online optimality bound is scoped to the generated fixed candidate set
  and solver-local coverage objective. It must not be read as a bound on the
  continuous satellite scheduling problem or official verifier score.
- Candidate coverage uses deterministic solver-local Brahe SGP4 propagation and
  WGS84 ray intersections from public TLE fields, not benchmark verifier
  internals.
- Schedule-aware CELF acceptance is a benchmark adaptation layered onto the
  paper method. It improves verifier-valid output quality but does not imply
  continuous-schedule optimality.
- Bounded local improvement is another benchmark adaptation after CELF. It uses
  only fixed candidates and solver-local schedule checks, and reports accepted
  moves separately from CELF lazy recomputation statistics.
- Post-selection repair can still remove CELF-selected candidates, although the
  current schedule-aware quality probes on `case_0001` have repair loss ratio
  `0.0`.
- Battery and duty checks are conservative solver-local approximations; the
  official verifier remains the source of truth.
- The public profile intentionally keeps one strongest fixed-candidate configuration. Local users can tune `config.yaml`, but alternative smaller profiles are not reported as quality evidence.

## Evidence Type

The official `main_solver` `quality_probe_stride150_full` profile passes with `status: verified`, `valid: true`, and no verifier violations on the promoted case. This solver is therefore registered in `experiments/main_solver` with `evidence_type: reproduced_solver`.
