## Invited Session Wed.1.H 3002

#### Wednesday, 10:30 - 12:00 h, Room: H 3002

**Cluster 23: Telecommunications & networks** [...]

### Network flows and network design

**Chair: Bernard Fortz**

**Wednesday, 10:30 - 10:55 h, Room: H 3002, Talk 1**

**Tue Rauff Lind Christensen**

Solving the piecewise linear network flow problem by branch-cut-and-price

**Coauthor: Martine LabbĂ©**

**Abstract:**

In this paper we present an exact solution method for the network flow problem with piecewise linear costs. This problem is fundamental within supply chain management and extends the fixed-charge transportation problem in a straight-forward way. This kind of problem has numerous applications and allows modeling of different shipping modes such as packages, less-than-truckloads and truckloads, often found in the logistics and shipping industry. Additionally, it might be used to model price discounts, as often considered within procurement theory. We propose a Dantzig-Wolfe reformulation of the problem and extend this to an exact method by branching and the addition of valid inequalities. On a number of randomly generated test instances the branch-cut-and-price method compares favorable to a standard mixed-integer programming solver with a significant reduction in runtime.

**Wednesday, 11:00 - 11:25 h, Room: H 3002, Talk 2**

**Bernard Fortz**

The hop-constrained survivable network design problem with reliable edges

**Coauthors: Quentin Botton, Luis Gouveia**

**Abstract:**

We study the hop-constrained survivable network design

problem with reliable edges. Given a graph with non-negative edge weights and node pairs *Q*, the hop-constrained survivable network design problem consists of constructing a minimum weight set of edges so that the induced subgraph contains at least *K* edge-disjoint paths containing at most *L* edges between each pair in *Q*.

In this talk, we propose and study the hop-constrained survivable network design problem with so-called *reliable* edges where in addition, we consider a subset of edges that are not subject to failure. We study two variants (a static problem where the reliability of edges is given, and an upgrading problem where edges can be upgraded to the reliable status at a given cost). We adapt for the

two variants an extended formulation proposed in [BFGP11] for the case without reliable edges. Due to the huge number of variables and constraints included in the extended formulations, we use Benders decomposition to accelerate the solving process. We develop an exact

branch-and-cut algorithm and a fix-and-branch heuristic.

**Wednesday, 11:30 - 11:55 h, Room: H 3002, Talk 3**

**Edoardo Amaldi**

Network routing subject to max-min fair flow allocation

**Coauthors: Antonio Capone, Stefano Coniglio, Luca Gianoli**

**Abstract:**

In the Max-min fairness (MMF) flow allocation principle not only the bandwidth of the commodity with the smallest allocation is maximized, but also in turn the second worst, the third worst and so on.

While in previous work the MMF principle has been used as routing

objective, we consider it as a constraint, since it allows to well approximate TCP flow allocation when the routing paths are given.

We investigate the problem of, given a network and set of commodities,

selecting a single path for each commodity so as to maximize a network

utility function subject to MMF flow allocation. We compare some mathematical programming formulations, describe a column generation approach and report some computational results.