Sensor Position Problem Example
This notebook walks through the Sensor Placement problem: choose a subset of sensor positions that covers all targets at minimum cost while respecting budget and exclusivity rules.
Problem overview
- Goal: minimize total sensor cost while covering each target at least a required number of times.
- Decisions: binary variable \(y_p\) for each position \(p\); \(y_p = 1\) if the position is activated.
- Inputs: coverage matrix (which positions see which targets), per-position costs, optional budgets, max-position caps, and mutually exclusive groups.
- Objective: \(\min \sum_p c_p \cdot y_p\).
- Key constraints:
- Coverage: \(\sum_{p \in \text{cover}(t)} y_p \ge \text{minCoverage}_t\) for each target \(t\).
- Exclusivity groups: at most one sensor per group.
- Optional: budget, max number of active positions, incompatibility pairs.
In this notebook, materialized coverage means the coverage matrix is precomputed and stored in JSON, so loading can skip geometry-based recomputation.
The sections below mirror the typical workflow: build data, formulate, solve with fast local solver, and optionally solve with Luna-hosted solvers like SCIP.
from luna_quantum.algorithms import SCIP
from luna_usecases.sensor_position_problem import (
SppCollection,
SppData,
SppFormulation,
SppInstance,
)
Create Data
SpData captures the static problem definition:
- position_ids: candidate sensor locations
- target_ids: points that must be covered
- coverage (targets × positions): Boolean matrix where coverage[t, p] is True if position p sees target t
- position_costs: cost per position
- min_coverage: per-target or scalar requirement (e.g., 1 for simple coverage)
- Optional controls: budget, max_positions, group_ids (exclusivity), fixed_on/off, must_select/forbidden, incompatibilities
Below is a toy 4×2 example (4 targets, 2 positions) to keep the coverage matrix readable.
import numpy as np
position_ids = ["p0", "p1"]
target_ids = ["t0", "t1", "t2", "t3"]
coverage = np.array(
[
[True, False], # t0 seen by p0
[True, True], # t1 seen by p0 or p1
[False, True], # t2 seen by p1
[True, False], # t3 seen by p0
]
)
data = SppData(
position_ids=position_ids,
target_ids=target_ids,
coverage=coverage,
position_costs=np.array([1.0, 1.2]),
min_coverage=1,
budget=None,
max_positions=None,
)
print(data.to_string())
print(data.model_dump())
SP Data (materialized coverage):
positions: 2
targets: 4
coverage matrix density: 62.5%
fixed on/off: 0/0
- dropped (dominated): 0
- dropped (degree-1): 0
targets removed with degree-1: 0
uncoverable targets: 0
budget: None
max_positions: None
variant groups: 0
{'name': 'sp', 'data_name': 'sp', 'position_ids': ['p0', 'p1'], 'target_ids': ['t0', 't1', 't2', 't3'], 'coverage': [[True, False], [True, True], [False, True], [True, False]], 'position_costs': [1.0, 1.2], 'min_coverage': [1, 1, 1, 1], 'budget': None, 'max_positions': None, 'incompatibilities': [], 'must_select': [], 'forbidden': [], 'fixed_on': [], 'fixed_off': [], 'uncoverable_targets': [], 'cost_weight': 1.0, 'proximity_penalty_weight': 0.0, 'lidar_positions': None, 'dropped_dominated_positions': None, 'dropped_degree1_positions': None, 'dropped_target_positions': None, 'target_positions': None, 'walls': [], 'group_ids': [None, None], 'lidar_params': [], 'position_metadata': None}
Create Formulation
SpFormulation converts data into an optimization model with:
- Variables: binary \(y_p\) for each position \(p\)
- Objective: minimize \(\sum_p c_p y_p\) (cost-weighted activation)
- Constraints:
- Coverage per target (using the baked coverage matrix)
- Optional budget and max-position limits
- Group exclusivity (at most one sensor per group)
- Incompatibility pairs (cannot select conflicting positions)
This model is solver-agnostic: you can feed it to baselines, SCIP, or other Luna solvers.
SP Formulation:
vars: 2 binaries (one per position)
targets: 4
cost weight: 1.0
budget: None
max_positions: None
fixed on/off: 0/0
groups: 0
Create Instance
SpInstance bundles SpData and SpFormulation. This keeps data (what the problem is) separate from the formulation (how we model it) and lets you reuse the same data with different formulations or parameter tweaks.
Data:SP Data (materialized coverage):
positions: 2
targets: 4
coverage matrix density: 62.5%
fixed on/off: 0/0
- dropped (dominated): 0
- dropped (degree-1): 0
targets removed with degree-1: 0
uncoverable targets: 0
budget: None
max_positions: None
variant groups: 0
Formulation:SP Formulation:
vars: 2 binaries (one per position)
targets: 4
cost weight: 1.0
budget: None
max_positions: None
fixed on/off: 0/0
groups: 0
Formulate Model
Build the optimization model from the instance. The model captures variables, constraints, and the objective and can be sent to any backend (baselines, SCIP, FlexQAOA).
Model: sp<sp>
Minimize
y_0 + 1.2 * y_1
Subject To
cover_t0: y_0 >= 1
cover_t1: y_0 + y_1 >= 1
cover_t2: y_1 >= 1
cover_t3: y_0 >= 1
Binary
y_0 y_1
Solve and Interpret
This section demonstrates two SCIP execution paths with the same interpretation flow:
- Remote SCIP: algorithms.SCIP() submits a Luna job and polls until completion.
Both follow the same pattern:
job = scip.run(model) → res = job.result() → instance.interpret(res)
Recommended workflow: run local SCIP first for quick checks, then run remote SCIP for parity with hosted execution. In both cases, keep the same pipeline:
job = scip.run(model)→res = job.result()→instance.interpret(res).
scip = SCIP()
job = scip.run(model)
scip_sol = instance.interpret(job.result())
print("--- SCIP ---")
print(scip_sol.to_string())
2026-03-26 00:16:58 INFO Running SCIP for model sp<sp>
INFO Completed SCIP optimization for model sp<sp> in 0.01s
--- SCIP ---
SP Solution:
selected positions: 2
forced on/off: 0/0
covered targets: 4
uncovered targets: 0
coverage rate: 100.0%
total cost: 2.200
objective value: 2.200
feasible: True
Remote SCIP Authentication Setup
Remote SCIP execution uses the Luna service and needs authentication.
load_dotenv()loads environment variables from a local.envfile.- The notebook reads
LUNA_API_KEYfrom that environment. - If the key is not set, it prompts securely via
getpass.
Run the next cell once before the remote SCIP cell.
import getpass
import os
from dotenv import load_dotenv
from luna_quantum.client.controllers.luna_solve import LunaSolve
# Load .env and authenticate for remote solver calls
load_dotenv()
api_key = os.getenv("LUNA_API_KEY")
if not api_key:
api_key = getpass.getpass("Enter your Luna API key: ")
LunaSolve.authenticate(api_key)
from luna_quantum import algorithms
scip = algorithms.SCIP()
job = scip.run(model)
scip_sol = instance.interpret(job.result())
print("--- SCIP ---")
print(scip_sol.to_string())
C:\Users\marku\vsc-projects\aqarios\luna-usecases\.venv\Lib\site-packages\rich\live.py:260: UserWarning: install
"ipywidgets" for Jupyter support
warnings.warn('install "ipywidgets" for Jupyter support')
2026-03-26 00:17:03 INFO Sleeping for 5.0 seconds. Waiting and checking a function in a loop.
--- SCIP ---
SP Solution:
selected positions: 2
forced on/off: 0/0
covered targets: 4
uncovered targets: 0
coverage rate: 100.0%
total cost: 2.200
objective value: 2.200
feasible: True
Working with Collections
Collections help you generate and manage multiple instances for benchmarking, batch experiments, or parameter sweeps. They keep metadata, problem descriptions, and instances together.
Generate a Collection
Use helper constructors (from_random, from_json, from_glb) to build collections with consistent metadata. Random generators let you control sizes, densities, and seeds for reproducibility.
# Generate a collection of random instances
collection = SppCollection.from_random(
n_positions=4,
n_targets=12,
density=0.3,
num_instances=3,
seed=42,
)
print(f"Collection: {collection.name}")
print(f"Description: {collection.description}")
print(f"Total instances: {len(collection.instances)}\n")
first = collection.instances[0]
print("First instance summary:")
print(first.to_string())
Collection: Random SP 12x4
Description: Random SP instances (density=0.3)
Total instances: 3
First instance summary:
Data:SP Data (materialized coverage):
positions: 4
targets: 12
coverage matrix density: 41.7%
fixed on/off: 0/0
- dropped (dominated): 0
- dropped (degree-1): 0
targets removed with degree-1: 0
uncoverable targets: 0
budget: None
max_positions: None
variant groups: 0
Formulation:SP Formulation:
vars: 4 binaries (one per position)
targets: 12
cost weight: 1.0
budget: None
max_positions: None
fixed on/off: 0/0
groups: 0
Batch Processing
Formulate every instance first to inspect size and validity before solving. This catches infeasible data or unexpectedly large models early.
# Formulate all models in the collection
models = []
for i, instance in enumerate(collection.instances):
model = instance.formulate()
models.append(model)
print(f"Instance {i}: {model.num_variables} variables")
print(f"\nFormulated {len(models)} models!")
Solving Collections
Template for solving many instances. Swap in any solver (SCIP, FlexQAOA, or the local baselines). For Luna solvers use the job pattern; for baselines call .run(data) directly.
# Example template for running a solver on each instance:
from luna_quantum import algorithms
scip = SCIP()
solutions = []
for i, inst in enumerate(collection.instances):
print(f"Solving instance {i}...")
res = scip.run(inst.formulate())
sol = inst.interpret(res.result())
solutions.append(sol)
print(f" Objective: {sol.objective_value}\n")
2026-03-26 00:17:10 INFO Running SCIP for model sp<sp>
INFO Completed SCIP optimization for model sp<sp> in 0.01s
INFO Running SCIP for model sp<sp>
INFO Completed SCIP optimization for model sp<sp> in 0.01s
INFO Running SCIP for model sp<sp>
INFO Completed SCIP optimization for model sp<sp> in 0.00s
Next Steps
- Move to
sp-advanced.ipynbfor GLB-based workflows, auto-variants, reduction, and richer visualization. - Use Local SCIP first for fast iteration and model debugging on your machine.
- Validate parity with remote solvers (for example
algorithms.SCIP()andalgorithms.FlexQAOA()) on the same instances. - Track coverage density, constraint counts, objective values, and runtime across solver modes for benchmarking.