Skip to content

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

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.

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
LicenseFilepath Path to license file str ``
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
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_DumpLpFilename Write the master LP to file str ``
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_MaxNumCols The maximum number of cols 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 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.