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:

\[\begin{split}\text{minimize} \qquad &\sum_{a \in A} \alpha_a \sum_{i \in {\cal L}_a} d_{ai} x_{ai}\\ \text{subject to} \qquad &\sum_{i\in {\cal L}_a} x_{ai} = 1 \hspace{1.2in} \forall a \in A\\ &x_{ai} \le s_i \hspace{1.47in} \forall a \in A, i \in {\cal L}_a\\ &\sum_{i \in L} c_i s_i \le p\\ &s_i \in \{0,1\} \hspace{1.3in} \forall i \in L\\ &0 \leq x_{ai} \leq 1 \hspace{1.23in} \forall a \in A, i \in {\cal L}_a\end{split}\]

where:

  • \(A\) is the set of all scenarios

  • \(L\) is the set of all candidate sensors

  • \({\cal L_a}\) is the set of all sensors that are capable of detecting scenario \(a\)

  • \(\alpha_a\) is the probability of occurrence for scenario \(a\)

  • \(d_{ai}\) is the impact assessment, and represents some measure of the impact that will be incurred if scenario \(a\) is first detected by sensor \(i\)

  • \(x_{ai}\) is an indicator variable that will be 1 if sensor \(i\) is installed and that sensor is the first to detect scenario \(a\) (where first is defined as the minimum possible impact, usually defined as time to detection)

  • \(s_i\) is a binary variable that will be 1 if sensor \(i\) is selected, and 0 otherwise

  • \(c_i\) is the cost of sensor \(i\)

  • \(p\) is the sensor budget

The size of the Impact formulation is determined by the number of binary variables. Although \(x_{ai}\) is a binary indicator variable, it is relaxed to be continuous between 0 and 1, and yet it always converges to a value of 0 or 1. Therefore, the number of binary variables that need to be considered by the solver is a function of the number of candidate sensors alone, and not the number of scenarios considered. This formulation has been used to place sensors in large water distribution networks [BHPU06] [USEPA12] [USEPA15] and for gas detection in petrochemical facilities [LBSW12].

To use this formulation in Chama, create an ImpactFormulation object and specify the impact assessment, \(d_{ai}\), sensor budget, \(p\), and (optionally) sensor cost, \(c_i\) and the scenario probability, \(\alpha_a\), as described below:

  • 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:

\[\begin{split}\text{maximize} \qquad &\sum_{a \in A} \alpha_a x_a \\ \text{subject to} \qquad &x_{a} \le \sum_{i \in {\cal L}_a} s_i \hspace{1.15in} \forall a \in A\\ &\sum_{i \in L} c_i s_i \le p\\ &s_i \in \{0,1\} \hspace{1.3in} \forall i \in L\\ &0 \leq x_{a} \leq 1 \hspace{1.25in} \forall a \in A\end{split}\]

where:

  • \(A\) is the set of all entities

  • \(L\) is the set of all candidate sensors

  • \({\cal L_a}\) is the set of all sensors that cover entity \(a\)

  • \(\alpha_a\) is the objective weight of entity \(a\)

  • \(x_{a}\) is an indicator variable that will be 1 if entity \(a\) is covered

  • \(s_i\) is a binary variable that will be 1 if sensor \(i\) is selected, and 0 otherwise

  • \(c_i\) is the cost of sensor \(i\)

  • \(p\) 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, \({\cal L_a}\), sensor budget, \(p\), and (optionally) sensor cost, \(c_i\) and the entity weights, \(\alpha_a\), as described below:

  • 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', 'D']
>>> 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:

\[g_{min} \le \sum_{i \in L_g} s_i \le g_{max}\]

where:

  • \(L_g\) is a subset of all candidate sensors

  • \(s_i\) is a binary variable that will be 1 if sensor \(i\) is selected, and 0 otherwise

  • \(g_{min}\) is the minimum number of sensors that must be selected from the subset \(L_g\)

  • \(g_{max}\) is the maximum number of sensors that may be selected from the subset \(L_g\)

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 \(L_g\) containing the candidate sensors within each subvolume and adding a grouping constraint over each of these subsets with \(g_{min}\) set to 1.

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 \(L_g\) for each category of sensor and then set \(g_{min}\) and \(g_{max}\) according to how many sensors you want in each category.

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.