Module min_cost_flow 

Minimum-cost flow, exact and certified: the dual of every scheduling and retiming problem whose constraints are differences of two variables, which is how a register cut of least area at a target clock is found.

min_cost_flow runs the primal network simplex on a strongly feasible spanning tree (Cunningham, A network simplex method, 1976): an artificial root joined to every node, block-search pricing, and the tree kept as a thread list so a pivot touches only the subtree it moves (the layout of LEMON’s NetworkSimplex, Kovács, Minimum-cost flow algorithms: an experimental evaluation, 2015). Integer data give an integer optimum.

Every answer carries what proves it, and check replays it trusting nothing the search did:

• an optimum carries its flow and a potential π under which every arc below capacity has reduced cost cost + π(from) − π(to) ≥ 0 and every arc with flow has it ≤ 0, which is optimality by complementary slackness;
• an infeasible problem carries a node set whose supply exceeds the capacity leaving it;
• one without an optimum carries a cycle of uncapacitated arcs of negative cost.

Structs

Arc

An arc: capacity units at most (None for no bound), at cost a unit.

Enums

FlowError

Why a problem was not solved.

Solution

A problem’s answer, with its certificate.

Constants

COST_LIMIT

The bound on an arc’s cost.

FLOW_LIMIT

The bound on an arc’s capacity and on the supplies’ total size.

Functions

check

Whether solution is the problem’s answer, by its certificate alone.

min_cost_flow

The least-cost flow meeting supply (positive where flow starts, negative where it ends) over arcs.