Origin-Destination Integer Multicommodity Flow (ODIMCF)

Category
Network Design & Location
Formulation
Combinatorial
Objective
Minimize
Time limit
60 s per instance
Paper
Using Branch-and-Price-and-Cut to Solve Origin-Destination Integer Multicommodity Flow ProblemsCynthia Barnhart, Christopher A. Hane, Pamela H. Vance · Operations Research, 2000

Description

A telecommunications network operator manages a directed network consisting of a set of nodes and a set of directed arcs connecting pairs of nodes. Each arc has a known capacity, expressed in units of bandwidth. The operator must handle a set of commodities, where each commodity represents a group of calls or messages sharing a common origin node and a common destination node. Each commodity has a known demand quantity representing the bandwidth it requires.

Every commodity must be routed as a single, unsplittable unit along exactly one directed path from its origin node to its destination node, or it may be rejected entirely. To allow rejection, the network includes, for each commodity, an artificial direct arc from the commodity's origin to its destination. The artificial arc has no capacity limit and carries a cost equal to the revenue that would have been earned by successfully routing that commodity. All physical arcs in the network have zero routing cost for every commodity.

The operator must choose, for each commodity, exactly one origin-to-destination path (which may be the artificial rejection arc or any path through the physical network). The total demand flowing through any physical arc, summed across all commodities whose chosen paths include that arc, must not exceed the arc's capacity. Flow must be conserved at every node for every commodity: at the origin node of a commodity, exactly one unit of that commodity's flow is produced; at the destination node, exactly one unit is absorbed; and at every intermediate node, the total flow of that commodity entering the node equals the total flow leaving it.

The goal is to minimize the total cost. For each combination of commodity and arc, the cost contribution equals the commodity's demand multiplied by the per-unit cost for that commodity on that arc, counted only when that arc lies on the commodity's chosen path. The total cost is the sum of these contributions across all commodities and all arcs. Because physical arcs have zero cost, the total cost reduces to the sum of artificial-arc costs for rejected commodities, which equals the total lost revenue from commodities not routed through the physical network. Equivalently, minimizing total cost maximizes the total revenue earned from commodities successfully carried on the physical network.

Instance schema

{
  "network": {
    "num_nodes": "<int> Total number of nodes in the directed network.",
    "num_arcs": "<int> Total number of directed physical arcs in the network.",
    "nodes": "<list[int], length num_nodes> Identifiers for all nodes in the network.",
    "arcs": [
      {
        "arc_id": "<int> Unique identifier for this arc.",
        "from_node": "<int> Node where this directed arc originates.",
        "to_node": "<int> Node where this directed arc terminates.",
        "capacity": "<int> Maximum total bandwidth that can flow through this arc across all commodities.",
        "cost": "<int> Per-unit routing cost for any commodity using this arc."
      }
    ]
  },
  "commodities": {
    "num_commodities": "<int> Total number of commodities (call groups) to be routed or rejected.",
    "commodity_list": [
      {
        "commodity_id": "<int> Unique identifier for this commodity.",
        "origin": "<int> Node where this commodity originates.",
        "destination": "<int> Node where this commodity must be delivered.",
        "demand": "<int> Bandwidth required by this commodity.",
        "revenue": "<int> Revenue earned if this commodity is successfully routed through the physical network.",
        "artificial_arc_cost": "<int> Cost incurred if this commodity is rejected instead of being routed."
      }
    ]
  },
  "objective": "<str> Direction of optimization for the total routing and rejection cost."
}

Solution schema

{
  "objective_value": "<float> Total cost of rejected commodities across the entire routing plan.",
  "commodities": [
    {
      "commodity_id": "<int> Identifier of the commodity whose routing outcome is described in this entry.",
      "rejected": "<bool> Whether this commodity is rejected and sent on its artificial arc instead of being routed through the network.",
      "path_arcs": [
        {
          "from": "<int> Origin node of an arc used on this commodity's routing path.",
          "to": "<int> Destination node of an arc used on this commodity's routing path.",
          "arc_id": "<int> Identifier of an arc used on this commodity's routing path."
        }
      ]
    }
  ]
}

Public instances

For development. Scoring uses private instances, which are never published. Sign in to download them.

  • tiny_instance.json60 s

Checker

The checker our evaluation runs, from the FrontierOR benchmark (CC BY 4.0) with the recomputed objective added to its result. How to run it. Sign in to download it.

  • feasibility_check.py