Optimization¶
The chama.optimize
module contains Impact and Coverage sensor
placement optimization formulations. The formulations are written in Pyomo
[HLWW12] and solved using an open source or commercial solver such as GLPK
[Makh10], Gurobi [GUROBI], or CPLEX [CPLEX]. The open source GLPK solver is
used by default. Additional optimization formulations could be added to this
module.
Impact Formulation¶
The Impact formulation is used to determine optimal sensor placement and type that minimizes impact, where impact can be the sensor’s detection time or some other measure of damage. The Impact formulation, which is based on the p-median facility location problem, is described below:
where:
is the set of all scenarios is the set of all candidate sensors is the set of all sensors that are capable of detecting scenario is the probability of occurrence for scenario is the impact assessment, and represents some measure of the impact that will be incurred if scenario is first detected by sensor is an indicator variable that will be 1 if sensor is installed and that sensor is the first to detect scenario (where first is defined as the minimum possible impact, usually defined as time to detection) is a binary variable that will be 1 if sensor is selected, and 0 otherwise is the cost of sensor is the sensor budget
The size of the Impact formulation is determined by the number of binary
variables. Although
To use this formulation in Chama, create an
ImpactFormulation
object and
specify the impact assessment,
Impact assessment: A single value of impact (detection time or other measure of damage) for each sensor that detects a scenario. Impact is stored as a Pandas DataFrame, as described in the Impact assessment section.
Sensor budget: The number of sensors to place, or total budget for sensors. If the ‘use_sensor_cost’ flag is True, the sensor budget is a dollar amount and the optimization uses the cost of individual sensors. If the ‘use_sensor_cost’ flag is False (default), the sensor budget is a number of sensors and the optimization does not use sensor cost.
Sensor characteristics: Sensor characteristics include the cost of each sensor. Sensor characteristics are stored as a Pandas DataFrame with columns ‘Sensor’ and ‘Cost’. Cost is used in the sensor placement optimization if the ‘use_sensor_cost’ flag is set to True.
Scenario characteristics: Scenario characteristics include scenario probability and the impact for undetected scenarios. Scenario characteristics are stored as a Pandas DataFrame with columns ‘Scenario’, ‘Undetected Impact’ , and ‘Probability’. Undetected Impact is required for each scenario. When minimizing detection time, the undetected impact value can be set to a value larger than time horizon used for the study. Individual scenarios can also be given different undetected impact values. Probability is used if the ‘use_scenario_probability’ flag is set to True.
Results are stored in a dictionary with the following information:
Sensors: A list of selected sensors
Objective: The expected (mean) impact based on the selected sensors
FractionDetected: The fraction of scenarios that were detected
TotalSensorCost: Total cost of the selected sensors
Assessment: The impact value for each sensor-scenario pair. The assessment is stored as a Pandas DataFrame with columns ‘Scenario’, ‘Sensor’, and ‘Impact’ (same format as the input Impact assessment’) If the selected sensors did not detect a particular scenario, the impact is set to the Undetected Impact.
The following example demonstrates the use of the Impact Formulation.
>>> print(min_det_time)
Scenario Sensor Impact
0 S1 A 2.0
1 S2 A 3.0
2 S3 B 4.0
3 S4 C 1.0
4 S5 D 2.0
>>> print(sensor)
Sensor Cost
0 A 100.0
1 B 200.0
2 C 400.0
3 D 500.0
>>> print(scenario)
Scenario Undetected Impact Probability
0 S1 50.0 0.15
1 S2 250.0 0.50
2 S3 100.0 0.05
3 S4 75.0 0.20
4 S5 225.0 0.10
>>> impactform = chama.optimize.ImpactFormulation()
>>> results = impactform.solve(impact=min_det_time, sensor_budget=1000,
... sensor=sensor, scenario=scenario,
... use_scenario_probability=True,
... use_sensor_cost=True)
>>> print(results['Sensors'])
['A', 'C', 'D']
>>> print(results['Objective'])
7.2
>>> print(results['Assessment'])
Scenario Sensor Impact
0 S1 A 2.0
1 S2 A 3.0
2 S4 C 1.0
3 S5 D 2.0
4 S3 None 100.0
Coverage Formulation¶
The Coverage formulation is used to place sensors that maximize the coverage of a set of entities, where an entity can be a scenario, scenario-time pair, or geographic location. The Coverage formulation is described below:
where:
is the set of all entities is the set of all candidate sensors is the set of all sensors that cover entity is the objective weight of entity is an indicator variable that will be 1 if entity is covered is a binary variable that will be 1 if sensor is selected, and 0 otherwise is the cost of sensor is the sensor budget
This formulation is similar to the Impact formulation in that the number of binary variables is a function of the number of candidate sensors and not the number of entities considered.
To use this formulation in Chama, create a
CoverageFormulation
object and
specify the coverage,
Coverage: A list of entities that are covered by a single sensor. Coverage is stored as a Pandas DataFrame, as described in the Impact assessment section.
Sensor budget: The number of sensors to place, or total budget for sensors. If the ‘use_sensor_cost’ flag is True, the sensor budget is a dollar amount and the optimization uses the cost of individual sensors. If the ‘use_sensor_cost’ flag is False (default), the sensor budget is a number of sensors and the optimization does not use sensor cost.
Sensor characteristics: Sensor characteristics include the cost of each sensor. Sensor characteristics are stored as a Pandas DataFrame with columns ‘Sensor’ and ‘Cost’. Cost is used in the sensor placement optimization if the ‘use_sensor_cost’ flag is set to True.
Entity characteristics: Entity weights stored as a Pandas DataFrame with columns ‘Entity’ and ‘Weight’. Weight is used if the ‘use_entity_weight’ flag is set to True.
Results are stored in a dictionary with the following information:
Sensors: A list of selected sensors
Objective: The mean coverage based on the selected sensors
FractionDetected: The fraction of entities that are detected
TotalSensorCost: Total cost of selected sensors
EntityAssessment: A dictionary whose keys are the entity names and values are a list of sensors that detect that entity
SensorAssessment: A dictionary whose keys are the sensor names and values are the list of entities that are detected by that sensor
The following example demonstrates the use of the Coverage Formulation to solve for scenario-time coverage. The results list scenario-time pairs that were detected by the sensor placement (listed as ‘scenario-time’).
>>> print(det_times)
Scenario Sensor Detection Times
0 S1 A [2, 3, 4]
1 S2 A [3]
2 S3 B [4, 5, 6, 7]
3 S4 C [1, 3]
4 S5 B [6]
5 S5 D [2, 4, 6]
>>> print(sensor)
Sensor Cost
0 A 100.0
1 B 200.0
2 C 400.0
3 D 500.0
>>> print(scenario)
Scenario Undetected Impact Probability
0 S1 50.0 0.15
1 S2 250.0 0.50
2 S3 100.0 0.05
3 S4 75.0 0.20
4 S5 225.0 0.10
>>> scenario_time, new_scenario = chama.impact.detection_times_to_coverage(
... det_times,
... coverage_type='scenario-time',
... scenario=scenario)
>>> print(scenario_time)
Sensor Coverage
0 A [S1-2.0, S1-3.0, S1-4.0, S2-3.0]
1 B [S3-4.0, S3-5.0, S3-6.0, S3-7.0, S5-6.0]
2 C [S4-1.0, S4-3.0]
3 D [S5-2.0, S5-4.0, S5-6.0]
>>> print(new_scenario)
Scenario Undetected Impact Probability
0 S1-2.0 50.0 0.15
1 S1-3.0 50.0 0.15
2 S1-4.0 50.0 0.15
3 S2-3.0 250.0 0.50
4 S3-4.0 100.0 0.05
5 S3-5.0 100.0 0.05
6 S3-6.0 100.0 0.05
7 S3-7.0 100.0 0.05
8 S4-1.0 75.0 0.20
9 S4-3.0 75.0 0.20
10 S5-6.0 225.0 0.10
11 S5-2.0 225.0 0.10
12 S5-4.0 225.0 0.10
>>> new_scenario = new_scenario.rename(columns={'Scenario':'Entity',
... 'Probability':'Weight'})
>>> coverageform = chama.optimize.CoverageFormulation()
>>> results = coverageform.solve(coverage=scenario_time, sensor_budget=1000,
... sensor=sensor, entity=new_scenario,
... use_sensor_cost=True)
>>> print(results['Sensors'])
['A', 'B', 'C']
>>> print(results['Objective'])
11.0
>>> print(round(results['FractionDetected'],2))
0.85
Grouping Constraints¶
Constraints can be added to both the Impact and Coverage formulations to enforce or restrict the number of sensors allowed from certain sets. These grouping constraints take the following general form:
where:
is a subset of all candidate sensors is a binary variable that will be 1 if sensor is selected, and 0 otherwise is the minimum number of sensors that must be selected from the subset is the maximum number of sensors that may be selected from the subset
Grouping constraints can be used to ensure that an optimal sensor placement follows required
policies or meets practical limitations. For example, you might want to determine the optimal
sensor placement, while also ensuring that there is at least one sensor in every 10 m x 10 m
subvolume of the space. This can be formulated by defining sensor subsets
Another example where grouping constraints might be used is when you have different categories
of sensors and you want to make sure that an optimal placement has a certain number of each
category. In this case, you would define a sensor subset
While grouping constraints are very useful, it should be noted that it is possible to formulate infeasible optimization problems if these constraints are not used carefully.
The following example adds grouping constraints to the Impact formulation. This requires the user to 1) create the Pyomo model, 2) add the grouping constraints, 3) solve the model, and 4) extract the solution summary.
>>> impactform = chama.optimize.ImpactFormulation()
>>> model = impactform.create_pyomo_model(impact=min_det_time, sensor=sensor, scenario=scenario)
>>> impactform.add_grouping_constraint(['A', 'B'], min_select=1)
>>> impactform.add_grouping_constraint(['C', 'D'], min_select=1)
>>> impactform.solve_pyomo_model(sensor_budget=2)
>>> results = impactform.create_solution_summary()
>>> print(results['Sensors'])
['A', 'D']
Grouping constraints can be added to the Coverage formulation in a similar manner.