Model¶

General-purpose optimization model for column-generation based solving. Supports graphs with resource constraints, subproblems, master variables, and constraints.

Formulation¶

$\begin{aligned} \min{ } & \sum_{k \in K} c_k x_k + \sum_{(V,E) \in G} \Big ( \sum_{v \in V} c_v x_v + \sum_{e \in E} c_e x_e \Big ) + \sum_{i \in N} c_i y_i \\ \text{s.t. } & \sum_{k \in K} \alpha_{jk} x_k + \sum_{(V,E) \in G} \Big (\sum_{v \in V} \alpha_{jv} x_v + \sum_{e \in E} \alpha_{je} x_e \Big ) + \sum_{i \in N} \alpha_{ji} y_i = b_j & & j \in M \\ & x_v, x_e \geq 0 && (V,E) \in G, v \in V, e \in E\\ & 0 \leq L^k \leq x_k \leq U^k && k \in K \\ & y_i \in [\mathbb{R}, \mathbb{Z}, \mathbb{B}] && i \in N \end{aligned}$

Where $N$ is the set of master variables, $M$ the constraints, $(g, s, t) \in K$ the subproblems with graph $(V,E) = g \in G$ and source/target $s, t \in V$. Path usage may be continuous, integer, or binary.

Constructor¶

import flowty

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

Graphs¶

addGraph¶

graph = model.addGraph(
    edges,                  # list of (source, target) tuples
    edgeCosts=[],           # list of float, length |E|
    vertexCosts=[],         # list of float, length |V|
    resources=[],           # list of resource tuples
    pathSense="N",          # "N" (any) or "S" (simple/no cycles)
    neighbourhoods=[]       # NG-set neighbourhoods
)

Parameter	Type	Description
`edges`	`list[tuple[int, int]]`	Directed edges as `(source, target)` pairs
`edgeCosts`	`list[float]`	Cost per edge
`vertexCosts`	`list[float]`	Cost per vertex
`resources`	`list`	Resource definitions (see Resources & Rules)
`pathSense`	`str`	`"N"` = any path, `"S"` = simple (no repeated vertices)
`neighbourhoods`	`list[list[int]]`	NG-set neighbours per vertex

Vertices are zero-indexed. The max vertex index determines the number of vertices -- avoid gaps.

Graph Properties¶

graph.id           # int
graph.edges        # list of Edge objects
graph.vertices     # list of Vertex objects
graph.edgeCosts    # list of float
graph.vertexCosts  # list of float
graph.resources    # list of resources

Edge and Vertex Properties¶

edge.id       # int
edge.source   # int
edge.target   # int

vertex.id     # int

NG-Sets¶

Define NG-set neighbourhoods to strengthen simple path enforcement:

# vertices 1, 2, 3 are each other's 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], pathSense="S", neighbourhoods=NG)

Multiple subproblems can share a graph. Constraints on shared edges span all subproblems using that graph:

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 capacity constraint applies to both subproblems
for e, u in zip(graph.edges, U):
    model += e <= u

Subproblems¶

addSubproblem¶

subproblem = model.addSubproblem(
    graph,          # Graph object
    source,         # int: source vertex
    target,         # int: target vertex
    obj,            # float: objective offset
    lb,             # float: lower bound on path usage (>= 0)
    ub,             # float: upper bound on path usage
    domain,         # str or Domain: "C", "I", or "B"
    rules=[]        # optional rule definitions
)

See Resources & Rules for the rules parameter.

Subproblem Properties¶

subproblem.id       # int
subproblem.source   # int
subproblem.target   # int
subproblem.graph    # Graph

Domains¶

"C"  # or flowty.Variable.Domain.Continuous
"I"  # or flowty.Variable.Domain.Integer
"B"  # or flowty.Variable.Domain.Binary

Variables¶

addVariable¶

variable = model.addVariable(obj=1.0, lb=0.0, ub=float("inf"), domain="C", lazy=False)

Parameter	Type	Default	Description
`obj`	`float`	0	Objective coefficient
`lb`	`float`	-inf	Lower bound
`ub`	`float`	inf	Upper bound
`domain`	`str`	--	`"C"`, `"I"`, or `"B"`
`lazy`	`bool`	`False`	Add dynamically like generated paths

Constraints¶

addConstraint¶

terms = [(1.0, x), (2.0, y)]
model.addConstraint(terms, flowty.Constraint.Sense.LessEqual, rhs=10.0, lazy=False)

Terms can reference variables, subproblems, vertices, or edges.

Operator Overloading¶

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

Lazy Constraints¶

model += flowty.sum(terms) <= rhs, True      # lazy=True
model.addConstraint(terms, sense, rhs, True)  # lazy=True

flowty.sum¶

model += flowty.sum(terms) + constant <= rhs
model += flowty.sum(2 * e for e in graph.edges) == 1

Modeling with Subproblems, Vertices, and Edges¶

s = subproblem
v = graph.vertices[0]
e = graph.edges[0]

# mix in constraints
model += 1.0 * s + 1.0 * v + 1.0 * e <= rhs

# set partitioning
for v in graph.vertices[1:n-1]:
    model += v == 1

# edge capacities
for e, u in zip(graph.edges, U):
    model += e <= u

# sum on outgoing edges
vertex = graph.vertices[0]
model += flowty.sum(e for e in graph.edges if e.source == vertex.id) == 1

Constraint Sense¶

flowty.Constraint.Sense.LessEqual     # <=
flowty.Constraint.Sense.Equal         # ==
flowty.Constraint.Sense.GreaterEqual  # >=

Solving¶

solve¶

status = model.solve()

Status¶

flowty.Model.Status.Optimal
flowty.Model.Status.Infeasible
flowty.Model.Status.TimeLimit
flowty.Model.Status.NodeLimit

getSolution¶

best = model.getSolution()          # best solution, or None
nth = model.getSolution(n)          # n-th solution (0 = best)
all_solutions = model.getSolutions()
num = model.getNumSolutions()

Solution Object¶

solution.cost       # float: objective value
solution.paths      # list of Path objects
solution.variables  # list of VariableX objects

Path Object¶

path.x              # float: solution value
path.subproblem     # Subproblem
path.edges          # list of Edge objects

VariableX Object¶

var.variable        # Variable
var.x               # float: solution value

Paths¶

Add Initial Paths¶

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

Extract Generated Paths¶

paths = model.getPaths()

Read/Write¶

Write and read .lp/.mps + .graph files:

model.write("model.lp")
model.write("model.mps")
model.read("model.lp")

Model Properties¶

model.name          # str
model.graphs        # list of Graph
model.subproblems   # list of Subproblem
model.variables     # list of Variable
model.constraints   # list of Constraint