s2mflow

A high-performance meta-generation framework for lifting single-commodity flow instances into the multicommodity space.

s2mflow is a Python library PyPI with a high-speed Rust core (via PyO3) designed to transform single-commodity minimum-cost flow (MCF) instances into minimum-cost multicommodity flow (MCMCF) instances. It is built for researchers in Operations Research, Mathematical Optimization, and Network Optimization who need to generate reproducible, scalable test data.

The software package s2mflow is presented in SoftwareX:

Felix P. Broesamle, Stefan Nickel, s2mflow: A meta-generator for multicommodity flow instances, SoftwareX, Volume 35, 2026, 102874, ISSN 2352-7110, https://doi.org/10.1016/j.softx.2026.102874.

The theoretical meta-generation framework and mathematical foundations are introduced in:

Felix P. Broesamle and Stefan Nickel. 2026. "On the Single-Multi-Commodity Gap: Lifting Single- to Multicommodity Flow Instances". Optimization Online. Preprint. Available at https://optimization-online.org/?p=34287.

Key Features

• High Performance: Core logic implemented in Rust for zero-overhead data handling.
• DIMACS Compatible: Load standard .min single-commodity files.
• Custom MCMCF Format: Introduces the .mcfmin format for standardized multicommodity data storage.
• Supply Partitioning Methods:
  • method=1: Equal distribution of supply and demand across commodities.
  • method=2: Intermediate heterogeneity via a beta-binomial allocation. The optional parameter concentration_param controls the concentration (default 3.0).
  • method=0: Randomized, heterogeneous distribution of supply and demand across commodities.
• Randomizing Capacities and Costs: Functionality for generating randomized commodity-specific capacities and costs for each arc.
• Zero-Capacity Exclusions: Optionally set a fraction of individual commodity capacities to zero to model excluded arcs, controlled by cap_zero and cap_zero_param.
• Network Utilities: Support for identifying incoming and outgoing neighboring nodes.
• Parallel Arcs: Full support for instances with multiple arcs between the same pair of nodes. Every arc is uniquely identified by a (tail, head, index) triple; commodity arcs use (k, tail, head, index).

Note: Starting with version 0.3.0, arc identities are 3-tuples (tail, head, index). With version 0.2.0, the generation API uses an integer method parameter instead of the boolean is_uniform.

Installation

Standard Installation

s2mflow provides pre-compiled binary wheels for major platforms. Install directly via pip or poetry:

pip install s2mflow
# or via poetry
poetry add s2mflow

Building from Source

git clone https://github.com/FelixBroesamle/s2mflow.git
cd s2mflow
poetry install -vvv
poetry run maturin develop --release

Running Mathematical Models

To run the below mathematical modeling examples included in this repository out-of-the-box, install the optional solver dependencies:

poetry install --extras solver

Verifying the Installation

After building from source, you can verify that both the Rust core and the Python bindings are functioning correctly by running the test suites:

# Run the Rust test-suite
cargo test

# Run the Python test suite
poetry run pytest
# To run the Python tests in parallel, use:
poetry run pytest -n auto

Running the Example Workflows

The repository includes demo scripts and datasets to help you verify the end-to-end workflow after installation. Sample network instances are provided in the data/ directory. Example scripts are locatet in the examples directory.

# Execute the core s2mflow multicommodity instance generation workflow
poetry run python examples/demo.py

# Execute the below Pyomo + HiGHS optimization workflow
poetry run python examples/solve_instance_pyomo.py

Quick Start

The following snippet illustrates an end-to-end workflow: parsing a standard single-commodity DIMACS .min network file, lifting it into a 3-commodity space with high commodity-demand heterogeneity (Spread), and exporting the output. It also demonstrates how to bypass file formats entirely for direct integration.

import s2mflow

# Input file example contents:
# p min 2 1         (2 nodes, 1 arc)
# n 1 10            (Node 1: supply of 10)
# n 2-10            (Node 2: demand of 10)
# a 1 2 0 10 9      (Arc from 1 to 2, min_cap=0, max_cap=10, cost=9)

# 1. Load a single-commodity network (DIMACS .min format)
network = s2mflow.load_min_instance("input.min")

# 2. Generate multicommodity data for 3 commodities
# method=0 activates the stochastic 'Spread' method
mc_data = s2mflow.generate_multi_commodity_data(
    instance=network,
    num_commodities=3,
    method=0,
    randomize_caps=False,
    randomize_costs=False,
    cap_zero=False,
    seed=512,
)

# 3. Save as a multi-commodity instance (.mcfmin format)
s2mflow.save_multi_commodity_instance("output.mcfmin", network, mc_data)

# Output file (.mcfmin format)
# p min 2 1 3 0 0 0 0 0.0 512       (3 commodities, randomize_caps = False (0), randomize_costs = False (0), method = 0 (Spread), cap_zero = False (0), cap_zero_param = 0.0, seed = 512)
# n 1 10 2 5 3      (Supply of 10 split into supplies: 2, 5, 3)
# n 2-10-2-5-3      (Demand of-10 split into demands: -2,-5,-3)
# a 1 2 0 10 10 9

# 4. Load multicommodity instance back into memory
loaded_mc_data = s2mflow.load_multi_commodity_instance("output.mcfmin")

# 5. Direct usage bypassing formal file formats
data = {1: 126, 2:-126}
spread_multi_data = s2mflow.split_supplies_spread(data, num_commodities=5, seed=512)
# spread_multi_data = {1: [6, 24, 23, 12, 61], 2: [-6,-24,-23,-12,-61]}

uniform_multi_data = s2mflow.split_supplies_uniform(data, num_commodities=5)
# uniform_multi_data = {1: [25, 26, 25, 25, 25], 2: [-25,-26,-25,-25,-25]}

beta_binomial_multi_data = s2mflow.split_supplies_beta_binomial(data, num_commodities=5, concentration_param=3.0, seed=512)

The Extended .mcfmin Format

The library uses a natural extension of the DIMACS .min format to support multiple commodities:

• Problem Line: p min <num_nodes> <num_edges> <num_commodities> <randomize_caps> <randomize_costs> <method> <cap_zero> <cap_zero_param> <seed = 0>.
  • randomize_caps (0 or 1): Flag indicating if commodity-specific capacities are randomized.
  • randomize_costs (0 or 1): Flag indicating if commodity-specific costs are randomized.
  • method (0, 1, or 2): Partitioning strategy. 0 = Spread, 1 = Uniform, 2 = Beta-Binomial.
  • cap_zero (0 or 1): Flag indicating if zero-capacity exclusions are applied.
  • cap_zero_param (float): Fraction of arcs excluded per commodity.
  • seed: Relevant if method=0 or method=2, or if randomization of commodity-specific capacities or costs is enabled (randomize_caps = 1 or randomize_costs = 1).
• Node Line: n <node_id> <total_demand> <demand_com_1> <demand_com_2> ... <demand_com_K>.
• Arc Line: Depending on the randomization flags (randomize_caps, randomize_costs):
  • Default (0, 0): a <from> <to> <low> <cap_total> <cap_total> <cost>.
  • Commodity-specific capacities (1, 0): a <from> <to> <low> <cap_total> <cap_1> ... <cap_K> <cost>.
  • Commodity-specific costs (0, 1): a <from> <to> <low> <cap_total> <cap_total> <cost_1> ... <cost_K>.
  • Commodity-specific capacities and costs (1, 1): a <from> <to> <low> <cap_total> <cap_1> ... <cap_K> <cost_1> ... <cost_K>.

Examples for the .mcfmin Format

Below, we illustrate how the file structure shifts when applying different generation configurations.

Based Single-Commodity Instance (input.min)

# c Base single-commodity instance (input.min)
# p min 4 5
# n 1 17
# n 4 -17
# a 1 2 0 10 10
# a 1 3 0 15 5
# a 2 4 0 10 10
# a 3 2 0 5 20
# a 3 4 0 15 4

Strategy 1: Uniform Partitioning

This strategy distributes the nodal demands as evenly as possible across the 4 commodities.

uniform_mc_data = s2mflow.generate_multi_commodity_data(instance=network, num_commodities=4, method=1, randomize_caps=False, randomize_costs=False, cap_zero=False)

s2mflow.save_multi_commodity_instance("uniform.mcfmin", network, uniform_mc_data)

# --- Output File Contents (uniform.mcfmin) ---
# c Multicommodity flow generated by s2mflow
# p min 4 5 4 0 0 1 0 0.0 0
# n 1 17 5 4 4 4
# n 4 -17 -5 -4 -4 -4
# a 1 2 0 10 10 10
# a 1 3 0 15 15 5
# a 2 4 0 10 10 10
# a 3 2 0 5 5 20
# a 3 4 0 15 15 4

Strategy 2: Spread Partitioning with Randomized Capacities and Costs

This strategy generates high commodity-demand heterogeneity and simultaneously applies uniform noise to individual commodity capacities and arc costs.

spread_rand_caps_costs_mc_data = s2mflow.generate_multi_commodity_data(
    instance=network, num_commodities=4, method=0,
    randomize_caps=True, cap_a=0.6, cap_b=1.0,
    randomize_costs=True, cost_a=0.5, cost_b=2.0,
    cap_zero=True, cap_zero_param=0.05,
    seed=42,
)
s2mflow.save_multi_commodity_instance("spread_full.mcfmin", network, spread_rand_caps_costs_mc_data)

# --- Output File Contents (spread_full.mcfmin) ---
# c Multicommodity flow generated by s2mflow
# p min 4 5 4 1 1 0 0 0.05 42
# n 1 17 4 6 1 6
# n 4 -17 -4 -6 -1 -6
# a 1 2 0 10 0 8 8 10 13 15 6 17
# a 1 3 0 15 10 9 10 11 4 10 6 7
# a 2 4 0 10 9 9 0 7 6 6 18 13
# a 3 2 0 5 4 4 5 0 21 34 23 23
# a 3 4 0 15 15 11 12 12 8 6 6 3

(For demonstrations of isolated randomization configurations, see the examples/demo.py file).

End-to-End Optimization Workflows

The instance attributes exposed by s2mflow integrate seamlessly into algebraic modeling languages and solvers.

Workflow 1: File-Based Parsing with Pyomo & HiGHS (Open-Source)

This workflow loads a serialized .mcfmin file, builds a mathematical program in Pyomo, and solves it using HiGHS.

import pyomo.environ as pyo
import s2mflow

# 1. Load multi-commodity benchmark instance
mc = s2mflow.load_multi_commodity_instance("spread_full.mcfmin")

# 2. Initialize Model
model = pyo.ConcreteModel("MCMCF")

# 3. Decision Variables: 0 <= x_e^k <= u_e^k
def commodity_edge_bounds(m, k, u, v, idx):
    upper_bound = mc.commodity_capacities[(u, v, idx)][k]
    return (0.0, float(upper_bound))

model.flow = pyo.Var(
    mc.commodity_edges,    # (k, u, v, idx)
    domain=pyo.NonNegativeReals,
    bounds=commodity_edge_bounds,
    name="x"
)

# 4. Objective: Minimize total routing cost
model.obj = pyo.Objective(
    expr=sum(
        model.flow[k, u, v, idx] * mc.commodity_weights[(u, v, idx)][k]
        for (k, u, v, idx) in mc.commodity_edges
    ),
    sense=pyo.minimize
)

# 5. Shared Mutual Capacity Constraints
model.shared_caps = pyo.ConstraintList()
for i, (u, v, idx) in enumerate(mc.edges):
    model.shared_caps.add(
        sum(model.flow[k, u, v, idx] for k in range(mc.num_commodities)) <= mc.capacities[i]
    )

# 6. Flow conservation — parallel-safe per-node arc lists
in_arcs  = {n: [] for n in mc.nodes}
out_arcs = {n: [] for n in mc.nodes}
for arc in mc.edges:
    u, v, _ = arc
    out_arcs[u].append(arc)
    in_arcs[v].append(arc)

for k in range(mc.num_commodities):
    for node in mc.nodes:
        in_flow = sum(model.flow[k, u, v, idx] for (u, v, idx) in in_arcs[node])
        out_flow = sum(model.flow[k, u, v, idx] for (u, v, idx) in out_arcs[node])
        
        demand = mc.commodity_supply_demand_data[node][k] if node in mc.commodity_supply_demand_data else 0.0
        model.flow_balance.add(out_flow - in_flow == demand)

# 7. Solve
solver = pyo.SolverFactory("highs")
results = solver.solve(model, tee=True)
print(f"[+] Optimal Objective Value: {pyo.value(model.obj)}")

We have provided in examples/solve_instance_pyomo.py a complete workflow / pipeline for running examples on some provided network instances (see data/).

Workflow 2: In-Memory Generation with Gurobi (Commercial Solver)

This example bypasses a file serialization entirely, generating the multicommodity partitions dynamically in-memory. The mathematical model is solved with the gurobipy API for the commercial solver Gurobi (Requires a valid Gurobi license for instances of a certain size).

import gurobipy as grb
import s2mflow

# 1. Load baseline and generate data in-memory
net = s2mflow.load_min_instance("input.min")
mc_data = s2mflow.generate_multi_commodity_data(net, num_commodities=3, method=0, seed=512)

# 2. Initialize Gurobi Model
model = grb.Model("MCMCF")

# 3. Decision Variables
upper_bounds = [mc_data.commodity_capacities[(u, v, idx)][k] for (k, u, v, idx) in mc_data.commodity_edges]
flow = model.addVars(
    mc_data.commodity_edges, 
    lb=0.0, 
    ub=upper_bounds, 
    vtype=grb.GRB.CONTINUOUS, 
    name="x"
)

# 4. Objective Function
model.setObjective(
    grb.quicksum(flow[k, u, v, idx] * mc_data.commodity_weights[(u, v, idx)][k] for (k, u, v, idx) in mc_data.commodity_edges),
    sense=grb.GRB.MINIMIZE
)

# 5. Shared Mutual Capacity Constraints
model.addConstrs(
    (
        grb.quicksum(flow[k, u, v, idx] for k in range(mc_data.num_commodities)) <= net.capacities[i]
        for i, (u, v, idx) in enumerate(net.arcs)
    ), name="Shared_Cap"
)

# 6. Flow Conservation Constraints
in_arcs  = {n: [] for n in net.nodes}
out_arcs = {n: [] for n in net.nodes}
for arc in net.arcs:
    u, v, _ = arc
    out_arcs[u].append(arc)
    in_arcs[v].append(arc)

for k in range(mc_data.num_commodities):
    for node in net.nodes:
        in_flow = grb.quicksum(flow[k, u, v, idx] for (u, v, idx) in in_arcs[node])
        out_flow = grb.quicksum(flow[k, u, v, idx] for (u, v, idx) in out_arcs[node])
        
        demand = mc_data.supply_partition[node][k] if node in mc_data.supply_partition else 0.0
        model.addConstr(
            out_flow - in_flow == demand, 
            name=f"balance_{k}_{node}"
        )

# 7. Solve
model.optimize()
if model.Status == GRB.OPTIMAL:
    print(f"[+] Optimal Objective Value: {model.ObjVal}")

We have provided in examples/solve_instance_gurobi.py a complete workflow / pipeline for running examples on some provided network instances (see data/).

Benchmarks and Scaling

The following benchmarks were executed on an Intel Core Ultra 7 255U (32 GB RAM) using the standard NETGEN-SR instance family (LEMON graph library). The benchmark script and benchmark data are available in the directories examples/benchmark.py and data/.

Benchmark: Standard vs. Randomized Parameter Generation

• Standard: Spread partitioning with shared commodity capacities and costs.
• Randomized: Spread partitioning with randomized capacities and costs for every individual commodity-arc pair.

Benchmark Metrics

• Base Topology: Instance, Nodes, Arcs, Commodities (K), Sources (Srcs), Demands (Dmds), and Total Demand.
• Pipeline Phases: Min-cost flow base load (Load Min), parameter generation (Gen), MCF writer (Write), MCF re-load (Load MCF), and total execution time (Total).

Note: In the largest randomized case (netgen_sr_14a, $K=50$), the Rust engine generates over 104 million independent random parameters. The generation phase remains highly performant (+3.7 seconds), while the total pipeline time increases primarily due to the physical disk I/O required to write and load the expanded (full) .mcfmin file. All benchmark instances and generation configurations are available in the LEMON Graph Library.

Citing

If you use s2mflow in your research, please use the following preferred citation:

@article{BroesamleNickel:s2mflow,
  title   = {s2mflow: A meta-generator for multicommodity flow instances},
  author  = {Broesamle, Felix P. and Nickel, Stefan},
  journal = {SoftwareX},
  volume  = {35},
  pages   = {102874},
  year    = {2026},
  issn    = {2352-7110},
  doi     = {10.1016/j.softx.2026.102874},
  url     = {https://doi.org/10.1016/j.softx.2026.102874}
}

If you refer to the meta-generation framework and mathematical foundations, please cite the following paper:

@misc{BroesamleNickel:SMCG,
  author       = {Broesamle, Felix P. and Nickel, Stefan},
  title        = {On the Single-Multi-Commodity Gap: Lifting Single- to Multicommodity Flow Instances},
  year         = {2026},
  howpublished = {Optimization Online},
  note         = {Preprint. Available at https://optimization-online.org/?p=34287.},
}

Resources

• Documentation: s2mflow.readthedocs.io
• PyPI Package: pypi.org/project/s2mflow

License

Distributed under the MIT License. See LICENSE for more information.