On the Multi-Commodity Flow with convex objective function: Column-Generation approaches

This paper proposes a column-generation-based algorithmic framework to efficiently solve both splittable and unsplittable variants of the capacitated Multi-Commodity Flow problem with convex, potentially non-differentiable, link cost functions, offering a robust optimization approach for managing traffic in telecommunication networks.

The Gist

Imagine a massive, bustling city of data called Telecom City. In this city, there are thousands of delivery trucks (data packets) trying to get from various warehouses (sources) to specific stores (destinations). The roads connecting them are the network links.

The goal of this paper is to figure out the best way to route these trucks so that the city runs smoothly, without any road getting so jammed that traffic comes to a complete standstill.

Here is the breakdown of the problem and the paper's solution, explained through simple analogies.

1. The Problem: The "Jamming" Cost

In a normal map, a road might just have a fixed toll. But in Telecom City, roads behave differently.

• The Convex Cost: Imagine a road that is free when empty. As a few cars enter, it's still fine. But as it gets fuller, the "cost" (traffic delay, heat, wear and tear) doesn't just go up a little; it explodes.
• The Analogy: Think of a party. If 5 people are in a room, it's fun. If 10 people are there, it's crowded. If 50 people are there, it's a disaster. The "pain" of adding one more person grows much faster as the room gets fuller.
• The Goal: The paper wants to find a routing strategy that spreads the trucks out. Instead of putting 90% of the traffic on one super-highway (which would cause a massive jam), it wants to split the traffic across many smaller roads, keeping everyone moving at a moderate, efficient pace.

2. The Two Types of Delivery Rules

The paper tackles two different rules for how the trucks can move:

• The "Split" Rule (Splittable): A single delivery order can be chopped up. Half the boxes go down Highway A, and the other half go down Highway B. This is like splitting a large pizza among friends; everyone gets a slice from different pies. This is mathematically easier to solve.
• The "Whole" Rule (Unsplittable): A delivery order must stay together. You can't split the pizza; the whole truck must take one single path from start to finish. This is much harder because if you pick the wrong road, you might get stuck, and you can't just "split" the load to fix it.

3. The Solution: The "Column-Generation" Chef

The authors propose a clever way to solve this using a technique called Column Generation. Think of this as a chef trying to create the perfect menu for a massive banquet.

• The Problem: There are billions of possible routes (paths) a truck could take. You can't write them all down on a piece of paper; the list is too long.
• The Chef's Trick (Column Generation):
  1. The chef starts with a small, manageable menu (a few known routes).
  2. They solve the problem with just those routes.
  3. Then, they ask: "Is there a secret, hidden route that would make the whole banquet cheaper/better?"
  4. If yes, they add that new route to the menu and solve it again.
  5. They repeat this until no better hidden routes exist.

This allows them to handle the "billions of routes" without ever having to look at them all at once.

4. The Secret Weapon: The "Inner Approximation"

The paper introduces a specific trick called Inner Approximation (Section 3).

• The Analogy: Imagine the "Cost Curve" of a road is a smooth, curvy hill. Calculating the exact cost on a curvy hill is hard for computers.
• The Trick: Instead of trying to calculate the curve, the authors build a staircase inside the hill. They approximate the smooth curve with a series of flat steps (polytopes).
• Why it works: Computers are great at solving problems with straight lines (stairs) but terrible at curved lines. By turning the smooth, curvy cost function into a set of straight steps, they can use fast, standard math tools to solve the problem.
• The Bonus: This method is so flexible that it can even handle "black box" costs—situations where we don't know the exact formula for the traffic jam, but we can just measure how bad it is at different levels.

5. Solving the "Whole Truck" Problem (Unsplittable)

Solving the "Whole Truck" version is like trying to fit a set of rigid, unbreakable boxes into a moving truck. It's an NP-Hard problem (a fancy way of saying it's incredibly difficult and takes a long time to solve perfectly).

To solve this, the authors use a Branch-and-Price method:

• Branching: They make guesses. "What if Truck A must go this way?" and "What if Truck A cannot go that way?" They create a tree of possibilities.
• Pruning (The Tightening): To stop the tree from growing forever, they use "tightening" techniques.
  • Tight-INNER: They add rules that say, "If a road is already full, no new truck can squeeze in."
  • PATTERN: This is the most powerful tool. Instead of looking at trucks one by one, they look at groups (patterns) of trucks. They ask, "Can this specific group of trucks fit on this road together?" This creates a much tighter, more accurate map of reality, allowing the computer to find the perfect solution faster.

Summary: Why Does This Matter?

In the real world, internet routers and cell towers get hot and slow down when they are too busy. This paper provides a new, super-efficient way to tell the network: "Don't dump all the traffic on the main highway. Spread it out across the side streets, even if it looks like a longer path, because it keeps the whole system from overheating."

By using these mathematical tricks (staircases instead of curves, and looking at groups of trucks), they can solve these massive routing puzzles quickly, ensuring your video calls don't freeze and your downloads stay fast, even when the network is under heavy load.

Technical Summary

Here is a detailed technical summary of the paper "On the Multi-Commodity Flow with convex objective function: Column-Generation approaches" by Guillaume Beraud-Sudreau et al.

1. Problem Definition

The paper addresses the Convex Multi-Commodity Flow (CMCF) problem in telecommunication networks.

• Context: The network is modeled as a graph $G=(V, A)$ where nodes are devices and arcs are links. A set of commodities $K$ requires bandwidth $b_k$ from a source $s_k$ to a destination $t_k$.
• Objective: Minimize the total cost of the network, defined as the sum of convex cost functions $r_a(x_a)$ for each arc $a$, where $x_a$ is the total flow on the arc.
• Cost Characteristics: The cost functions are increasing, convex, and Lipschitz continuous. They model real-world network behaviors, such as the Kleinrock delay function (where delay increases sharply as bandwidth utilization approaches capacity) or quadratic costs.
• Variants:
  1. Splittable-CMCF: Flow for a commodity can be distributed fractionally across multiple paths.
  2. Unsplittable-CMCF: Each commodity must be routed on a single path (integer constraint). This variant is NP-hard.
• Constraints: Arc capacities must not be exceeded. If a demand cannot be fully routed, a large penalty is applied.

2. Methodology

The authors propose a hierarchy of formulations and solution algorithms, primarily relying on Column Generation and Linearization.

A. Splittable-CMCF Approaches

Three formulations are compared:

1. COMPACT (Compact Formulation): A direct formulation using arc-flow variables ($x_a^k$). It is intuitive but suffers from high dimensionality ($|A| \times |K|$ variables), making it impractical for large instances.
2. CONVEX (Extended Formulation): Uses path-flow variables ($x_p^k$). It employs a standard Column Generation approach where the Restricted Master Problem (RMP) is a nonlinear convex optimization problem. New paths are generated via a pricing problem based on KKT conditions (shortest path with weights derived from marginal costs).
   • Limitation: Requires differentiable cost functions and solving nonlinear RMPs at every iteration.
3. INNER (Inner Approximation Formulation): The paper's novel contribution for the splittable case.
   • Mechanism: It approximates the convex cost function $r_a(x)$ using a polyhedral inner approximation (a convex combination of vertices on the function's epigraph).
   • Linearization: This transforms the nonlinear RMP into a Linear Program (LP).
   • Column Generation: It generates two types of columns dynamically:
     1. Paths: Standard shortest path problems.
     2. Vertices: New points on the cost function curve to refine the approximation (solved via 1D convex optimization or dichotomy).
   • Advantages: Handles non-differentiable and black-box cost functions; avoids solving nonlinear RMPs.

B. Unsplittable-CMCF Approaches

To solve the integer variant, the authors embed the Splittable relaxation into a Branch-and-Price framework.

1. Branching Strategy: A custom branching scheme is developed to partition the solution space effectively. It branches on:
   • Commodity acceptance ($y_k$).
   • Path selection ($x_p^k$), specifically targeting the "divergence node" where fractional paths split, ensuring a partition of feasible integer solutions.
2. Relaxation Tightening: The standard Splittable relaxation is weak for the Unsplittable problem. Two tightening methods are proposed:
   • TIGHT-INNER: Adds constraints based on demand sizes to the INNER formulation, ensuring that arc load approximations respect the indivisibility of flows.
   • PATTERN Formulation: A significantly tighter relaxation. It introduces variables for patterns (subsets of commodities) crossing an arc. Instead of summing individual flows, it calculates the cost based on the total bandwidth of a specific set of commodities.
     • Pricing: Requires solving a convex knapsack problem (pseudopolynomial) to generate new patterns.
     • Result: Provides a much stronger lower bound, often matching the integer optimum at the root node.

3. Key Contributions

1. Generalization of Cost Functions: The proposed methods handle any increasing convex cost function, including non-differentiable and black-box functions, unlike previous methods limited to linear or differentiable functions.
2. Inner Approximation (INNER): A highly efficient linearization technique for the Splittable-CMCF that converts a nonlinear problem into a sequence of LPs, drastically reducing computational time.
3. Pattern-Based Relaxation: For the Unsplittable problem, the introduction of the PATTERN formulation provides a much tighter lower bound than previous approaches, enabling the solution of larger instances via Branch-and-Price.
4. Custom Branching: A specialized branching strategy for the Unsplittable-CMCF that avoids symmetry and ensures a complete partition of the solution space.

4. Experimental Results

The algorithms were tested on SNDLib instances using C++ and CPLEX.

• Splittable Performance:
  • The INNER approach significantly outperformed the COMPACT and CONVEX methods.
  • Solving times were reduced by factors of 10 to 35 for large instances.
  • INNER successfully solved instances where COMPACT failed due to memory limits.
  • It demonstrated robustness with non-differentiable cost functions.
• Unsplittable Performance:
  • Directly solving the integer problem (U-COMPACT) was inefficient.
  • TIGHT-INNER provided weak bounds, often failing to reach the target precision (0.1%) within 24 hours for larger instances.
  • PATTERN formulation showed superior tightness. In many cases, the root node solution was already integer-feasible (100% gap closure).
  • While the PATTERN pricing problem is computationally heavier (slower root node), it drastically reduced the size of the Branch-and-Price tree, allowing the solution of instances (e.g., newyork, sun) that were intractable with TIGHT-INNER.

5. Significance

• Telecommunications Relevance: The work directly addresses the need to model network congestion and delay (via Kleinrock functions) accurately. By minimizing convex costs, the algorithms naturally distribute traffic to avoid saturation, preserving capacity for future demands.
• Algorithmic Flexibility: The ability to handle black-box and non-differentiable costs makes the approach applicable to complex, real-world network performance models where analytical derivatives are unavailable.
• Scalability: The combination of Inner Approximation for the continuous case and Pattern-based tightening for the integer case provides a robust framework for solving large-scale, capacitated network flow problems that were previously computationally prohibitive.

In conclusion, the paper establishes a state-of-the-art framework for convex multi-commodity flow, proving that Inner Approximation is the most efficient method for splittable flows, while Pattern-based Column Generation is essential for solving the harder unsplittable variants.