# Tour¶

This tour serves as a reference point for developing models using the Flowty Optimisation Solver.

## Build Model¶

As a small example let's solve a mincost integer single commodity flow problem. Additionally, we enforce a time limit on the commodity paths.

```
from typing import List, Tuple
import flowty
# data
C: List[int] = [2, 2, 3, 1, 3, 1]
E: List[Tuple[int, int]] = [(0, 1), (0, 2), (1, 2), (2, 1), (1, 3), (2, 3)]
U: List[float] = [3, 6, 2, 2, 3, 4]
b: float = 6
T: List[int] = [1, 7, 6, 5, 3, 2]
q: int = 10
# create model
model = flowty.Model()
# create a maximum transit time constraint constraint
time = "E", T, "G", 0, q, "timeId"
# create a resource constrained graph
graph = model.addGraph(edges=E, edgeCosts=C, resources=[time])
# add a subproblem using the graph with source and target vertices. Enforce integer flows
s = model.addSubproblem(graph=graph, source=0, target=3, obj=0, lb=1, ub=b, domain="I")
# add a penalty variable for uncovered flow
penalty = sum(C) + 1
y = model.addVariable(obj=penalty, lb=0, ub=b, domain="C")
# add demand constraint
model += y + s >= b
# add edge capacity constraints
for e, u in zip(s.graph.edges, U):
model += e <= u
# solve the model
status = model.solve()
if status:
# get the best solution
solution = model.getSolution()
if solution:
# get the solution cost
obj = solution.cost
```

### Naming¶

Optionally name your model for future reference.

```
model = flowty.model("MyModelName")
```

## Get Solution¶

Solutions consists of variables and paths.

```
# get the best solution, returns None if no solution
best = model.getSolution()
```

### Multiple Solutions¶

```
# get number of solutions
num = model.getNumSolutions()
# get the n'th solution, n = 0 is the best solution
n = 1
nSolution = model.getSolution(n)
# get all solutions
solutions = model.getSolutions()
```

### Get Paths¶

```
# get paths in the solution
paths = solution.paths
# loop the paths and extract info
for path in paths:
# solution value
x = path.x
# the subproblem the path belongs to
subproblem = path.subproblem
# get the edges on the path
edges = path.edges
for edge in edges:
edgeId = edge.id
# edge source and target
source = edge.source
target = edge.target
```

### Get Variables¶

```
# get non-zero variables in the solution
variables = solution.variables
# loop the variables and extract info
for var in variables:
# underlying variable
variable = var.variable
# solution value
x = var.x
```

## Graphs and Resources¶

Resources constrains paths in graphs.

### Consumption and Bounds Types¶

Resources are defined as tuples like

```
resource: Tuple[
flowty.Resource.ConsumptionType | str,
List[int],
flowty.Resource.BoundsType | str,
int | List[int],
int | List[int],
]
# The resource components
consumptionType: flowty.Resource.ConsumptionType | str
consumptionValues: List[int]
boundsType: flowty.Resource.BoundsType | str
lowerBounds: int | List[int]
upperBounds: int | List[int]
```

Consumption types, i.e, the resources accumulation, are on edges or vertices. Resource lower and upper bounds are checked in edges and vertices or at a global level if the lower bound is 0 and upper bound is identical for all vertices.

```
# consumption types
edgeConsumption = flowty.Resource.ConsumptionType.Edge
edgeConsumption = "E"
vertexConsumption = flowty.Resource.ConsumptionType.Vertex
vertexConsumption = "V"
# bound types
edgeBounds = flowty.Resource.BoundsType.Edge
edgeBounds = "E"
vertexBounds = flowty.Resource.BoundsType.Vertex
vertexBounds = "V"
globalBounds = flowty.Resource.BoundsType.Global
globalBounds = "G"
```

Consumption and bounds are lists of integer values with lengths corresponding to their type, i.e., edge consumptions are number of edges long. Global bounds a are defined with a single upper bound scalar.

### Create Resources¶

Resources are created like

```
# time window resource
T: List[int] = [1, 3, 4, 2] # length |E|
A: List[int] = [0, 1, 1] # length |V|
B: List[int] = [0, 4, 5] # length |V|
time = "E", T, "V", A, B
# capacity resource (always a lower bound of 0)
D: List[int] = [2, 2, 3] # length |V|
b: int = 4
capacity = "V", D, "G", a, b, "capacityId"
# mutually exclusive sets, bits for vertices as set id (first and second bit)
S: List[int] = [1, 1, 2] # length |V|
U: List[int] = [1, 1, 2] # length |V|
mutuallyExclusiveSet = "V", S, "V", [], U, "mutuallyExclusiveSetId"
```

### Path Sense¶

Defines if the paths should be simple. Used to specify that paths must be simple and can be used for cyclic graphs to enforce paths without loops.

```
# path sense types
anyPath = flowty.Graph.PathSense.NoneType
anyPath = "N"
simplePath = flowty.Graph.PathSense.Simple
simplePath = "S"
```

### Add Graphs¶

Graphs a defined with set of edges given as tuples of vertices. The vertices are indexed from 0 and forth running. Watch out for gaps in the vertex indices as the max vertex index decides the total number of vertices in the graph and may result in excessive memory usage for storing the graph. By default the path sense is set to `flowty.Graph.PathSense.NoneType`

.

```
# graph with no resource constraints
C: List[float] = [1, 3, 2, 5] # length |E|
F: List[float] = [1, 3, 2] # length |V|
E: List[Tuple[int, int]] = [(0, 1), (0, 2), (2, 1), (2, 1)]
noResourceGraph = model.addGraph(edges=E, edgeCosts=C, vertexCosts=F)
# graphs with resource constraints
oneResourceGraph = model.addGraph(edges=E, edgeCosts=C, vertexCosts=F, resources=[time])
twoResourceGraph = model.addGraph(edges=E, edgeCosts=C, vertexCosts=F, resources=[time, capacity])
# get graphs
graphs = model.graphs
# get graph properties
graphId = graph.id
edgeCosts = graph.edgeCosts
vertexCosts = graph.vertexCosts
vertices = graph.vertices
edges = graph.edges
resources = graph.resources
```

To specify path sense, add graphs like

```
# graphs with path sense
graph = model.addGraph(edges=E, edgeCosts=C, resources=[time], pathSense="S")
```

#### Add NG sets¶

Define NG sets as list of list of vertices. Top level list must have dimension equal to number of vertices.

```
# vertices 1, 2, and 3 are each others neighbours
NG = [[1,2,3] if i in [1,2,3] else [] for i in range(n)]
graph = model.addGraph(edges=E, edgeCosts=C, resources=[time, capacity], pathSense="S", neighbourhoods=NG)
```

## Subproblems¶

Subproblems defines paths properties in a graph.

### Resources Rules Type¶

Rules define how resources are updated and feasibility is checked when propagated along the path.

```
# rule types
capacityRule = flowty.Rule.Type.Capacity
capacityRule = "C"
windowRule = flowty.Rule.Type.Window
windowRule = "W"
mutuallyExclusiveSetsRule = flowty.Rule.Type.MutuallyExclusiveSets
mutuallyExclusiveSetsRule = "MES"
```

The `capacityRule`

represents an accumulation of resource where feasibility is checked against a global upper bound, e.g., like the capacity constraint in the vehicle routing problem.

The `windowRule`

is time-window lie rule, where resource is accumulated and waiting is allowed at no cost and feasibility is checked against individual time windows at a vertex or on an edge.

The `mutuallyExclusiveSetsRule`

allows the user to define sets of vertices or edges that are mutually exclusive, i.e., a path is not allowed to visit two vertices in different sets. Exclusive sets are defined using bitsets as consumption and bounds types.

### Resource Update and Feasibility Rules¶

If only capacity and window rules are used, they do not need to be explicitly defined. For advanced usage rules must be defined.

Update and feasibility rules specify how resources are updated along a path and are checked for feasibility, see resource concepts.

Rules are defined with a type and a string id of the resource.

```
timeRule = "W", ["timeId"]
capacityRule = "C", ["capacityId"]
mutuallyExclusiveSetsRule = "MES", ["mutuallyExclusiveSetsId"]
```

Currently only rules concerning a single resources is supported. In this case, update and feasibility rules are identically and only need to be defined once.

### Create Subproblems¶

A subproblem is constructed with a graph and source and target vertices for the path together with lower and upper bounds for path flow (usage) and a definition of the path integrality property (domain). That is, a definition of fractional, binary or integral use of a path.

If only capacity and window rules are needed they are implicitly deduced based on the resource information. Subproblems are added like

```
graph: flowty.Graph = model.addGraph(edges=E, edgeCosts=C, vertexCosts=F)
source: int = 0
target: int = 2
obj: float = 0
lb: float = 1 # >= 0
ub: float = 1
domain: flowty.Variable.Domain | str = "C"
subproblem = model.addSubproblem(graph, source, obj, target, lb, ub, domain)
```

To specify rules add subproblems like

```
# add subproblem with rules
rules = [timeRule, capacityRule, mutuallyExclusiveSetsRule]
subproblem = model.addSubproblem(graph, source, obj, target, lb, ub, domain, rules)
```

Get the subproblems and their properties

```
# get subproblems
subproblems = model.subproblems
# get subproblem properties
subproblemId = subproblem.id
source = subproblem.source
target = subproblem.target
```

### Domains¶

Domains are defined like

```
continousType = flowty.Variable.Domain.Continuous
continousType = "C"
integerType = flowty.Variable.Domain.Integer
integerType = "I"
binaryType = flowty.Variable.Domain.Binary
binaryType = "B"
```

## Add Variables¶

Variables are just regular variables as one knows them from mixed integer programming

```
obj: float = 1 # default to 0
lb: float = 0 # default to -inf
ub: float = float("inf") # default to inf
variable = model.addVariable(obj, lb, ub, domain)
# get model variables
variables = model.variables
```

The variable domains are given in the same as for subproblems.

### Lazy Variables¶

It is possible to add variables as lazy. This way variables are dynamically in the same way as generated path variables are added.

```
lazy: bool = True
variable = model.addVariable(obj, lb, ub, domain, lazy)
```

## Add Constraints¶

Flowty supports modelling constraints on subproblems, vertices, edges and variables.

A basic example is

```
x = model.addVariable(obj, lb, ub, domain)
y = model.addVariable(obj, lb, ub, domain)
terms: List[
Tuple[float, flowty.Subproblem | flowty.Vertex | flowty.Edge | flowty.Variable]
] = [(1, x), (2, y)]
rhs: float = 1
sense: flowty.Constraint.Sense = flowty.Constraint.Sense.GreaterEqual
model.addConstraint(terms, sense, rhs)
```

The constraint sense is like

```
senseLEQ = flowty.Constraint.Sense.LessEqual
senseE = flowty.Constraint.Sense.Equal
senseGEQ = flowty.Constraint.Sense.GreaterEqual
```

### Shorthand Notation and Sum Terms¶

```
model += 2 * x - y + 5 <= 4
model += 2 * x - y + 5 == 4
model += 2 * x - y + 5 >= 4
```

Sum terms using the `flowty.sum`

function

```
constant: float = 10
model += flowty.sum(terms) + constant <= rhs
# mixing
model += flowty.sum(terms) + constant + 2 * x - y + 5 <= rhs
```

### Lazy Constraints¶

```
lazy: bool = True
model += flowty.sum(terms) + constant <= rhs, lazy
model.addConstraint(terms, sense, rhs, lazy)
```

### Modelling with Subproblems, Vertices and Edges¶

Adding subproblems, vertices and edges to constraints is like

```
s: flowty.Subproblem = subproblem
v: flowty.Vertex = graph.vertices[0]
e: flowty.Edge = graph.edges[0]
coef: float = 1
model += coef * s + coef * v + coef * e <= rhs
# vertices and edges are accesed through added graphs
vertices = graph.vertices
edges = graph.edges
# set partitioning constraints
for v in vertices:
model += v == 1
# edge capacities
U: List[float] # length |E|
for e, u in zip(edges, U):
model += e <= u
# sum on edges
model += flowty.sum(2 * e for e in graph.edges) == 1
# sum on outgoing edges
vertex = graph.vertices[0]
model += flowty.sum(2 * e for e in graph.edges if e.source == vertex.id) == 1
```

## Share Graphs In Subproblems¶

It is possible to share graphs across multiple subproblems, e.g., in multi-commodity flow like problems.

```
s1 = model.addSubproblem(graph, source=0, target=1, obj=0, lb=0, ub=1, domain="C")
s2 = model.addSubproblem(graph, source=2, target=0, obj=1, lb=1, ub=2, domain="I")
```

This allows modelling on vertices and edges in a graph to span multiple subproblems like

```
graph2 = model.addGraph(costs=C, edges=E)
s3 = model.addSubproblem(graph2, source=2, target=0, obj=1, lb=1, ub=2, domain="I")
# edge capacities for two graphs in different subproblems
for e1, e2, u in zip(graph.edges, graph2.edges, U):
model += e1 + e2 <= u
# edge capacities for one graph in different subproblems
for e, u in zip(graph.edges, U):
model += e <= u
```

One can think of it as a short-hand notation where the one edge represents that particular edge in each of the subproblems.

Besides being convenient for modelling purposes it is also memory efficient since less graph data needs to be stored.

Behind the scenes subproblems may be merged if their underlying graphs are identical and they share source or target vertices.

## Adding and Extracting Paths¶

### Add Initial Paths¶

Add an initial set of paths to the model.

```
edges = [edge for edge in subproblem.graph.edges if edge.source == subproblem.source and edge.target == subproblem.target]
paths = [flowty.Path(subproblem, edges)]
model.addPaths(paths)
```

Paths are checked for validity and cost is based on graph input.

### Extract Generated Paths¶

At the end of the solve extract the generated paths.

```
paths = model.getPaths()
```

## Parameters¶

Set parameters to control the solvers behavior like this

```
model.setParam("parameterName", value)
```

Supported parameters are

Parameter | Description | Type | Default |
---|---|---|---|

Branch_NumStrongBranchCandidates | Number of strong branch candidates | `int` |
128 |

Branch_StrongBranchParallel | Do strong branching in parallel | `bool` |
`True` |

LicenseFilepath | Path to license file | `str` |
`None` |

LogFilepath | Path to log file | `str` |
`logs/flowty.log` |

LogLevel | Level of logging to console (trace=0, debug=1, info=2, warn=3, error=4, critical=5, off=6) | `int` |
2 |

LogLevelFile | Level of logging to file (trace=0, debug=1, info=2, warn=3, error=4, critical=5, off=6) | `int` |
2 |

Lp_MaxIterationsRecover | Number of iteration to try to recover from an unstable LP | `int` |
10 |

Master_Cut_LimitIteration | Max number of cuts added per iteration | `int` |
10 |

Master_Cut_LimitTotal | Max number of cuts added in total | `int` |
1000 |

master_Cut_MinViolation | Minimum violation of cut (absolute) | `float` |
0.05 |

Master_Cut_UseSubsetRow | Use subset row inequalities. Use only when valid for formulation (set partition constraints on vertices) | `bool` |
`False` |

Master_DumpGraphFilename | Name of file to dump graphs to | `str` |
`None` |

Master_DumpLpFilename | Name of file to dump LPs to | `str` |
`None` |

Master_MaxColIterations | Maximum number of iterations to generate columns | `int` |
max |

Master_MinColInactivity | Number of iterations before inactive columns are removed from master problem | `int` |
max |

Master_MinRowInactivity | Number of iterations before inactive rows (cuts/lazy constraints) are removed from master problem | `int` |
5 |

Master_NgSet_MaxLargeCycleSize | Max size for detecting large cycles in simple paths | `int` |
100 |

Master_NgSet_MaxNeighbours | Max number of neighbours in mg-sets | `int` |
24 |

Master_NgSet_MaxSmallCycleSize | Max size for detecting small cycles in simple paths | `int` |
5 |

Master_PricerFrequency | Frequency of solving pricing problem | `int` |
1 |

Master_PrintFreqency | Master problem iteration print frequency | `int` |
1 |

Master_PrintOnlyRoot | Print only master problem details in the root node | `bool` |
`True` |

Master_PrintTimingDetails | Print total timing details for master problem | `bool` |
`False` |

Master_SepFrequency | Master problem cut separation frequency | `int` |
1000 |

Master_SepLazyFrequency | Master problem lazy cut separation frequency | `int` |
1 |

Master_SepNgSetFrequency | Master problem NG-set separation frequency | `int` |
max |

Master_UnusedThreshold | Threshold for tracking inactive rows | `float` |
0.9 |

MIPGap | The relative MIP gap in percentage | `float` |
1e-4 |

MIPGapAbs | The absolute MIP gap | `float` |
1e-10 |

MIPHeuristicEmphasis | How much effort to use in MIP heuristics. Higher value is more effort ([0.0-1.0]) | `float` |
0.05 |

NumThreads | Number of threads used for multi-processing | `int` |
number of threads available |

Pricer_Algorithm | Pricing dynamic programming algorithm to use (default=0 (we decide), pull=1, push=2) | `int` |
0 |

Pricer_HeuristicHighFilter | Minimum number of in/out degree of vertex in graph filter for high heuristic effort (disable with 0) | `int` |
12 |

Pricer_HeuristicLowFilter | Minimum number of in/out degree of vertex in graph filter for low effort heuristic (disable with 0) | `int` |
7 |

Pricer_HeuristicMediumFilter | Minimum number of in/out degree of vertex in graph filter for medium effort heuristic (disable with 0) | `int` |
0 |

Pricer_MaxNumCols | Maximum number of columns added per iteration | `int` |
400 |

Pricer_MaxNumPricings | The maximum number of pricing problems to solve in parallel | `int` |
400 |

Pricer_MaxNumVars | The maximum number of variables to add in each pricing iteration | `int` |
400 |

Pricer_MultiThreading | Allow multi-threading in pricing problems | `bool` |
True |

Pricer_UseSparseStorage | Use sparse storage in shortest path algorithm | `bool` |
`False` |

PrimalHeu_DiveFrequency | Number of branch nodes to process between each dive | `int` |
11 |

PrimalHeu_DiveMaxColIterations | Maximum number of iterations to generate columns when diving | `int` |
max |

PrimalHeu_DiveMaxIterations | Maximum number of iterations in the primal dive heuristic | `int` |
100 |

PrimalHeu_DivePrintFreqency | Primal dive heuristic print frequency | `int` |
10 |

PrimalHeu_DiveStrongBranchParallel | Do strong branch in parallel when diving | `bool` |
`True` |

PrimalHeu_NumStrongBranchCandidates | Maximum number of strong branch candidates | `int` |
32 |

PrimalHeu_RestrictedMipFrequency | Frequency of calling restricted MIP heuristic | `int` |
101 |

PrimalHeu_RestrictedMipMaxIterations | Maximum number of iterations in restricted MIP heuristic | `int` |
500 |

TimeLimit | Solver time limit in seconds | `int` |
max |

TreeManager_MaxBranchNodes | Maximum number of branch nodes (0=unlimited) | `int` |
0 |

TreeManager_PrintFreqency | Branch tree print frequency | `int` |
1 |

## Read/Write Instance Files¶

Write instance files to disk. This results in a `.lp`

or `.mps`

file describing the mixed integer linear programming part of the problem and a `.graph`

part with information on graphs and subproblems.

```
# write model.lp/mps and model.graph files
model.write("model.lp")
model.write("model.mps")
```

Reading a file is done with

```
# read the .lp file and related model.graph
model.read("model.lp")
```

## Visualization¶

Use NetworkX together with Matplotlib for simple visualization of networks.

Pip install the libraries

```
pip install networkx matplotlib
```

Assume you have solved a model and have extracted a solution. Let's draw a network with labeled vertices and edges with non-zero values.

Consider the code snippet below.

```
import networkx
import matplotlib.pyplot as plt
# the graph
graph = model.graphs[0]
# get best solution
solution = model.getSolution()
# get the first path
path = solution.paths[0]
edges = [(e.source, e.target) for e in path.edges]
gx = networkx.DiGraph()
gx.add_nodes_from([v.id for v in graph.vertices])
gx.add_edges_from(edges)
# pos = {i: (x[i], y[i]) for i in range(n)} # for lists of x,y coordinates
pos = networkx.spring_layout(gx) # alternative layout
networkx.draw_networkx_nodes(gx, pos, nodelist=gx.nodes)
networkx.draw_networkx_labels(gx, pos, labels={i: i for i in gx.nodes})
networkx.draw_networkx_edges(gx, pos, nodelist=gx.edges)
# plt.show() # if gui backend is supported
plt.savefig("mypath.png")
```

First the non-zero edges are extracted from the graph, next part builds the network and adds labels, and last the graph is drawn.