...
Illustration of the budget-constrained max-flow problem. Given a set of starting nodes and destination nodes, the objective is to calculate the maximum amount of "flow" across the nodes, subject to capacity constraints of nodes, constraints on the capacity of the connections (edges), as well as costs associated with utilization of each connection (edge). The objective is to maximize the flow subject to the budget constraint.
This model can be composed from different components, each developed by contrbutors with different expertise and roles. The development can happen at different times (initial problem definition, service design time, run-time, and continuous improvement stages). Contributors can have different roles and expertise. Examples include:
- An optimization modeler (with expertise on modeling and mathematical aspects of optimization)
- A software developer with knowledge of data modeling and model/data templatesÂ
- A developer with expertise in creating policy models in the context of specific business domains
- An Ops team member with knowledge of applicable policies for a set of services and applications and knowledge on run-time configuration
An optimization model can therefore evolve from a mathematical concept to a computer program to a policy-driven, dynamically re-configurable application through the following stages:
An optimization modeler identifies the key concepts, comes up with a mathematical model, creates an optimization model, and tests with a small example dataset (a prototype corresponding to the model shown in the problem description above.
Then, a developer with an understanding of the API requirements, basic understanding of the model and data sources/adapters links the model to a data template (template file shown below). The developer needs a basic understanding of key variables of a model such as nodes, bandwidths, capacities in this example. While most adapters will be available from OSDF library, additional adapters/libraries can be developed and can be contributed back to the ODSF library.
A service designer, with basic understanding of key model concepts (key variables of a model such as nodes, bandwidths, capacities in this example) can create policy models (or use/extend existing constraint policy models from the OSDF library). In this example, this introduces a new constraint reflecting the maximum amount of flow that can go through a single network link, in order to reduce service disruption risks.
On top of this, an Ops person can enable or configure an applicable run-time operational constraint policy. In this example, this introduces a more stringent budget constraint (from all allowed budget to only 80% of the budget).
Thus, a new service can be created by extending existing optimization models, policies, and adapters, and using them as building blocks/ingredients.
Section |
---|
|
Minizinc Model Panel |
---|
title | MiniZinc model for the example application (budget constrained network flow optimization model). This model can be composed from different components, each independently contributed by contrbutors with different expertise and roles, as described above |
---|
|
|
Section |
---|
|
Minizinc Model Panel |
---|
title | Data file used in the example application. The file format is dzn (Minizinc data format) and the file uses the widely used jinja2 templating for Python, with support for OOF to objects such as "input" (the input API request), SDC (a dummy object that provides network capacities of nodes, as well as cost per unit network utilization), and AAI (another dummy object that provides bandwith for links among different nodes). This data template is rendered into a data file (dzn format), which, together with the model file defines a complete optimization problem. |
---|
| int: N; % input nodes int: M; % output nodes int: maxbw; float: budget;
set of int: inNodes = 1..N;
set of int: outNodes = 1..M;
array[inNodes] of int: inCap; array[outNodes] of int: outCap;
array[inNodes, outNodes] of int: bw; array[inNodes, outNodes] of float: cost; array[inNodes, outNodes] of var 0..maxbw: x;
constraint forall (i in inNodes) (sum (j in outNodes) (x[i,j]) <= inCap[i]);
constraint forall (j in outNodes) (sum (i in inNodes) (x[i,j]) <= outCap[j]);
constraint forall (i in inNodes, j in outNodes) (x[i,j] <= bw[i,j]);
constraint sum (i in inNodes, j in outNodes) (x[i,j] * cost[i,j]) <= budget;
% another "stringent" service-specific policy constraint sum (i in inNodes, j in outNodes) (x[i,j] * cost[i,j]) <= 0.8 * budget;
var flow = sum (i in inNodes, j in outNodes) (x[i,j]);
constraint forall (i in inNodes, j in outNodes) (x[i,j] <= 0.2 * flow);
solve maximize sum (i in inNodes, j in outNodes) (x[i,j]); |
Minizinc Data Template Panel |
---|
title | Data file used in the for the example application. The file format is dzn (Minizinc data format) and the file uses the widely used jinja2 templating for Python, with support for OOF to objects such as "input" (the input API request), SDC (a dummy object that provides network capacities of nodes, as well as cost per unit network utilization), and AAI (another dummy object that provides bandwith for links among different nodes). This data template is rendered into a data file (dzn format), which, together with the model file defines a complete optimization problem. |
---|
| % Relevant calls to APIs
{% inNodes, outNodes, budget = input.get("inNodes", "outNodes", "budget") %}
{% inCap, outCap = SDC.getCapacities(inNodes, outNodes) %};
{% bw = AAI.getBandwidthMatrix(inNodes, outNodes) %};
{% cost = SDC.getNetworkCostMatrix(inNodes, outNodes) %};
N = {{ len(inNodes) }};
M = {{ len(outNodes) }};
maxbw = {{ max(max(bw)) }};
budget = {{ budget }};
inCap = {{ inCap }};
outCap = {{ outCap }};
bw = {{ mzn.toMatrix(bw) }}; % writes it out as minizinc matrix
cost = {{ mzn.toMatrix(cost) }}; |
Minizinc Data File Panel |
---|
title | Rendered Minizinc Data File (from Template) |
---|
| N = 5;
M = 4;
maxbw = 20;
budget = 50;
inCap = [10, 5, 0, 4, 20];
outCap = [10, 0, 5, 4];
bw = [| 10, 5, 0, 0
| 2, 4, 10, 0
| 4, 4, 10, 0
| 2, 0, 0, 5
| 0, 0, 0, 1 |];
cost = [| 1, 1, 10, 20
| 90, 90, 90, 90
| 2, 1, 1, 1
| 2, 10, 10, 1
| 9, 9, 9, 99.9 |]; |
|
...