How do I decide which flow problem type to use for a given optimization problem?

Map the objective and constraints to a flow formulation: maximize throughput suggests max-flow; minimize a separating cut suggests min-cut; if costs matter, use min-cost flow; for demands and lower bounds, consider circulation.

Can this handle lower bounds and circulation?

Yes. The skill includes modeling circulation with lower bounds and applying reductions to standard flow formulations to obtain feasible solutions.

What algorithms are recommended?

For large graphs, use Dinic or push-relabel for max-flow; for min-cost flow, use successive shortest augmenting path with potentials. Start simple and scale up as needed.

flow-network-builder

Scanned

npx machina-cli add skill a5c-ai/babysitter/flow-network-builder --openclaw

Files (1)

SKILL.md

1.8 KB

Flow Network Builder Skill

Purpose

Model optimization problems as network flow problems, constructing appropriate flow networks and selecting optimal algorithms.

Capabilities

Identify max-flow/min-cut modeling opportunities
Construct flow network from problem description
Select optimal flow algorithm
Handle min-cost flow variants
Bipartite matching reduction
Circulation problems

Target Processes

advanced-graph-algorithms
graph-modeling
optimization problems

Flow Problem Types

Maximum Flow: Find max flow from source to sink
Minimum Cut: Partition minimizing cut capacity
Bipartite Matching: Maximum matching via flow
Min-Cost Max-Flow: Cheapest maximum flow
Circulation: Flow with lower bounds

Reduction Patterns

Assignment problems -> Bipartite matching
Scheduling -> Flow with constraints
Path cover -> Flow reduction
Edge-disjoint paths -> Unit capacity flow

Input Schema

{
  "type": "object",
  "properties": {
    "problemDescription": { "type": "string" },
    "problemType": {
      "type": "string",
      "enum": ["maxFlow", "minCut", "matching", "minCostFlow", "circulation"]
    },
    "constraints": { "type": "object" }
  },
  "required": ["problemDescription"]
}

Output Schema

{
  "type": "object",
  "properties": {
    "success": { "type": "boolean" },
    "networkDescription": { "type": "string" },
    "nodes": { "type": "array" },
    "edges": { "type": "array" },
    "source": { "type": "string" },
    "sink": { "type": "string" },
    "algorithm": { "type": "string" },
    "reduction": { "type": "string" }
  },
  "required": ["success"]
}

Source

git clone https://github.com/a5c-ai/babysitter/blob/main/plugins/babysitter/skills/babysit/process/specializations/algorithms-optimization/skills/flow-network-builder/SKILL.md

View on GitHub

Overview

This skill lets you model optimization problems as flow networks, building appropriate graphs from problem descriptions and selecting effective flow algorithms. By handling max-flow/min-cut, min-cost flow variants, and reductions like bipartite matching or circulation, you can solve complex resource and assignment problems more efficiently.

How This Skill Works

Identify the problem type and map it to a flow formulation (max-flow, min-cut, min-cost flow, or circulation). Construct the network with nodes, edges, capacities, and optional costs, applying reductions (e.g., assignment to bipartite matching) when helpful. Then choose an appropriate algorithm and run the flow, interpreting the result and the corresponding objective (max flow value, min cut, or min-cost).

When to Use It

To maximize throughput from a set of sources to a set of sinks (max-flow).
When you need to minimize the capacity of a cut that separates sources from sinks (min-cut).
When you need a maximum matching via a flow reduction (bipartite matching).
When the cheapest way to achieve a maximum flow is required (min-cost max-flow).
When constraints require lower bounds or demands (circulation problems).

Quick Start

Step 1: Read the problem and decide on the flow model (max-flow, min-cut, min-cost flow, or circulation).
Step 2: Build the network: define nodes, set a source and sink (or create a circulation with demands), add edges with capacities (and costs if needed). Apply reductions (e.g., assignment -> bipartite matching) where appropriate.
Step 3: Choose an algorithm (e.g., Dinic for max-flow, SSP with potentials for min-cost flow) and run the solver; interpret the resulting flow value, costs, and the corresponding solution.

Best Practices

Read the problem description carefully and determine the core objective and constraints that map to a flow model.
Choose the most natural flow formulation (max-flow, min-cut, min-cost flow, or circulation) and apply reductions as needed.
Explicitly define source, sink, edge capacities, and edge costs; document any lower bounds or demands.
Prefer scalable algorithms for large graphs and validate with small, edge-case test cases.
Verify results by inspecting the residual graph, potential cuts, and, if using costs, total cost.

Example Use Cases

Assign workers to tasks using bipartite matching via flow to optimize assignments.
Plan transportation or logistics with min-cost max-flow to minimize shipping costs.
Route data through a network to maximize throughput (max-flow) under capacity constraints.
Schedule operations with resource constraints using flow with lower bounds (circulation).
Solve path cover or scheduling problems by reducing them to standard flow problems.

Frequently Asked Questions

Add this skill to your agents