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. Addtionaly, 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", q

# create a resource constrained graph
graph = model.addGraph(costs=C, edges=E, 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

Add 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", b

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 vertecies in the graph and may result in excessive memory usage for storing the graph.

# graph with no resource constraints
C: List[float] = [1, 3, 2, 5]  # length |E|
E: List[Tuple[int, int]] = [(0, 1), (0, 2), (2, 1), (2, 1)]
noResourceGraph = model.addGraph(costs=C, edges=E)

# graphs with resource constraints
oneResourceGraph = model.addGraph(costs=C, edges=E, resources=[time])
twoResourceGraph = model.addGraph(costs=C, edges=E, resources=[time, capacity])

# get graphs
graphs = model.graphs

# get graph properties
graph = graphs[0]
graphId = graph.id
vertices = graph.vertices
edges = graph.edges
resources = graph.resources

Add Subproblems

Subproblems defines paths properties in a graph. It 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.

graph: flowty.Graph = model.addGraph(costs=C, edges=E)
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)

# 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 accross 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
NumThreads Number of threads used for multi-processing int number of cores available
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
MIPGap The relative MIP gap in percentage float 1e-4
MIPGapAbs The absolute MIP gap float 1e-10
Pricer_MaxNumPricings The maximum number of pricing problems to solve in parallel int max
Pricer_MaxNumVars The maximum number of variables to add in each pricinng iteration int max
Pricer_MultiThreading Allow multi-threading in pricing problems bool True
PrimalHeu_DiveMaxIterations Maximum number of iterations in the primal dive heuristic int 100
PrimalHeu_DivePrintFreqency Primal dive heuristic print frequency 10 10
TimeLimit Solver time limit in seconds int max
TreeManager_PrintFreqency Branch tree print frequency int 1

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.