Prototype Decision Optimization usage for Covid-19 decision making
During this critical period, all help is welcome. Some people can directly help with their medical skills. Others continue to produce and distribute food. We hope that Technology can help too.
A demonstration of our technology, not a ready-to-use solution (yet!)
In the IBM Decision Optimization team, we develop optimization engines, tools and platforms. We ourselves don’t develop ready-to-use final solutions, but our tools can be used to directly solve real-life problems. Our technology is already used in many day- to-day critical applications, from nationwide energy production and consumption balances, to large food supply chain design and operations. Before having to work almost 24 hours a day, many nurses in many hospitals had their schedules built with solutions embedding our technology. See here, for example, a use case for hospital transportation of patients. To create the solution which answers these complex problems, our customers use our tools and platforms to develop and deploy Decision Optimization models. which they embed in their applications.
Our technology could also be used for urgent problems directly related to the current situation. We are not unfortunately Subject Matter Experts (SMEs) who could directly use our tools to create the right Decision Optimization models for that. But we can create a demonstration to show that it could be done. It is hoped that people with the right knowledge and who are involved in the decision-making process will benefit from this.
Planning the transfers
These days, one of the critical problem for our governments is to manage the heterogeneous propagation of the virus over the territories. Not all areas are infected at the same level. While confinment of the population and prohibition of travel is reducing the propagation of the virus, the transfer of sick people between different areas can reduce the stress of hospitals in the most critical regions. In France, transfers are now generalized, using military planes (see here or here), helicopters or high speed trains, but also locally with ambulances.
The problem of finding optimal ways to relocate sick people among areas can benefit from a combination of Machine Learning (ML) and Decision Optimization (DO).
Based on the recent evolution of the number of critical reanimation cases in each area, predictive models can be trained to forecast the evolution per area on the coming days. This data, in addition to the capacity of the hospitals for each of the areas and some description of the constraints applying on the possible transfers can then be used in a decision optimization model. This schema where Machine Learning is used first to extract additional unknown information and Decision Optimization is used to prescribe the best next actions is very common.
Example notebook
You can find here an example notebook. This is a very simplistic prototype to illustrate how both technologies could collaborate, but a real solution would require a subject matter expert to ensure that the right data is used, and the right constraints and objectives are taken into account. This model formulation is very standard process in Decision Optimization projects and can take from days to months, depending on the complexity of the problem.
Import and display input data
We use data from the French government data.gouv.fr site: https://www.data.gouv.fr/fr/datasets/donnees-relatives-a-lepidemie-de-covid-19/#_ in addition to some imported data on the different French administrative “departments” (GPS coordinates of frontier and center).
Using Folium, we can easily represent this data on a map. The circles show the number of reanimation cases in each department. Red circles show above normal capacity.
Simplistic predictive model
A very simplistic predictive model is trained for illustration. We use LinearRegression from sklearn, knowing obviously that the epidemy is not linear at all. But this gives an idea of how ML would work here.
import numpy as np
from sklearn.linear_model import LinearRegressionNB_PERIODS = 3def predict_more(d, n):
X = hosp_data[d].index.tolist()
X.reverse()
X=np.array(X).reshape(-1,1)
y = hosp_data[d]['rea'].tolist()
y.reverse()
y=np.array(y).reshape(-1,1)regsr=LinearRegression()
regsr.fit(X,y)to_predict_x = [i for i in range(len(X), len(X)+n)]
to_predict_x= np.array(to_predict_x).reshape(-1,1)
predicted_y= regsr.predict(to_predict_x)
delta_y = [ int(round(max(0, predicted_y[i][0]-y[len(y)-1][0]))) for i in range(n)]
return delta_ynew_rea ={ d:predict_more(d, NB_PERIODS) for d in deps}
print (new_rea)
The outcome is a prediction of the expected number of new reanimation cases to occur in the next few days we will plan (here NB_PERIODS = 3).
Sample Decision Optimization model
Our hypothesis for the optimization model is that two different types of transfers can be done:
- long distance transfers (planes, trains) with the number of transfers limited over the whole country, several people can be transferred at a time.
- short distance transfers (ambulances) with the number of transfers limited per area, and with just one person at a time.
The parameters we use (completely invented) are:
MAX_NB_LONG_TRANSFERS_PER_PERIOD = 3
MAX_CASES_PER_LONG_TRANSFERS = 20MAX_NB_SHORT_TRANSFERS_PER_DEPARTMENT = 3LONG_DISTANCE = 200
We use our docplexAPI to model the problem:
from docplex.mp.model import Model
mdl = Model("Plan Transfers")The decision variables represent the transfer links to be used in the best (optimal) transfer plan (an integer variable for the number of persons transferred and a binary variable indicating whether the link is used or not, with a constraint linking both). Another set of auxiliary variables represents the occupancy for each department and each period.
use_link_vars = mdl.binary_var_cube(deps, deps, transfer_periods, name="use_link")
link_vars = mdl.integer_var_cube(deps, deps, transfer_periods, lb=0, ub=MAX_CASES_PER_LONG_TRANSFERS, name="link")
occupancy_vars = mdl.integer_var_matrix(deps, all_periods, lb=0, name="occupancy")Then we formulate all the constraints:
# Initial state
mdl.add_constraints(occupancy_vars[d, 0] == initial[d] for d in deps)# structural constraint between user_link and link
mdl.add_constraints(use_link_vars[d, d1, t] == (link_vars[d, d1, t] >= 1) for d in deps for d1 in deps for t in transfer_periods)# Short transfers bounds
mdl.add_constraints(link_vars[d1, d2, t] <= 1 for d1 in deps for d2 in deps if not is_long[d1][d2] for t in transfer_periods)# number of transfers from a department less than current number of cases
mdl.add_constraints(mdl.sum(link_vars[d, d1, t] for d1 in deps) <= occupancy_vars[d, t] for d in deps for t in transfer_periods)# maximum number of LONG transfers
mdl.add_constraints(mdl.sum(use_link_vars[d1, d2, t] for d1 in deps for d2 in deps if is_long[d1][d2]) <= MAX_NB_LONG_TRANSFERS_PER_PERIOD for t in transfer_periods)# maximum number of SHORT transfers
mdl.add_constraints(mdl.sum(use_link_vars[d1, d2, t] for d1 in deps if not is_long[d1][d2] for t in transfer_periods) <= MAX_NB_SHORT_TRANSFERS_PER_DEPARTMENT for d2 in deps )# conservation constraints including new cases to come
mdl.add_constraints(occupancy_vars[d, t+1] == new_rea[d][t] + occupancy_vars[d, t] + mdl.sum(link_vars[d1, d, t] for d1 in deps) - mdl.sum(link_vars[d, d1, t] for d1 in deps) for d in deps for t in transfer_periods)
And the objectives. The main objective is to reduce the total overcapacity on the areas, but we should also limit unnecessary transfers.
final_overcapacity = mdl.sum(mdl.max(0, occupancy_vars[d, NB_PERIODS] - capacity[d]) for d in deps)
mdl.add_kpi(final_overcapacity)nb_long_transfers = mdl.sum(use_link_vars[d1, d2, t] for d1 in deps for d2 in deps if is_long[d1][d2] for t in transfer_periods)
mdl.add_kpi(nb_long_transfers)nb_short_transfers = mdl.sum(use_link_vars[d1, d2, t] for d1 in deps for d2 in deps if not is_long[d1][d2] for t in transfer_periods)
mdl.add_kpi(nb_short_transfers)mdl.minimize(1000 * final_overcapacity + 10 * nb_long_transfers + nb_short_transfers)
We can then solve the problem (using the CPLEX engine) and get the prescribed decisions.
mdl.set_time_limit(20)
mdl.solve(log_output=True)Display the solution
Using the same Folium package, we can represent the proposed transfers on a map.
The long distance transfers are represented in green and the short distance ones in black.
Conclusions
I want to insist again on the fact this is not a ready-to-use solution, but a demonstration of how ML and DO technology could be used to propose mathematically optimal transfer decisions.
You can find here the complete notebook.
In practice, additional data, constraints and objectives should be taken into account. For example, we can easily imagine that the level of criticality of individual infected persons would be taken into account. Also the characteristics of hospitals in the different areas, including the neighborhood of the airport or train station, should be taken into account.
Note also my model only considered transfers within France, while some transfers already took place from France to Germany and Luxembourg.
This notebook is hence only provided as an example which can be used to discover or learn optimization. You can freely try this notebook on Watson Studio Cloud.
There are dozens of other problems related to the current situation where ML and DO could help too, e.g. to manage the stocks and the supply chain for masks and respirators.
If you are in a position to use such technology in practice for the Covid-19 situation, don’t hesitate to contact us, we are willing to help.
