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

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")

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.

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

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.

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
LogFilepath	Path to log file	`int`	`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
Master_Cut_LimitIteration	Max num,ber of cuts generated per separation	`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_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_MaxSmallCycleSize	Max size for detecting small cycles in simple paths	`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_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_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
NumThreads	Number of threads used for multi-processing	`int`	number of cores available
Lp_MaxIterationsRecover	Number of iteration to try to recover from an unstable LP	`int`	10
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_Algorithm	Pricing dynamic programming algorithm to use (default=0 (we decide), pull=1, push=2)	`int`	0
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_HeuristicHighFilter	Minimum number of in/out degree of vertex in graph filter for high heuristic effort (disable with 0)	`int`	12
PrimalHeu_DiveFrequency	Number of branch nodes to process between each dive	`int`	11
PrimalHeu_DiveMaxIterations	Maximum number of iterations in the primal dive heuristic	`int`	100
PrimalHeu_DivePrintFreqency	Primal dive heuristic print frequency	`int`	10
TimeLimit	Solver time limit in seconds	`int`	max
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 infomation 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.