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é


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


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


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.


  Payday Loans In Illinois. The main active actual substance of Levitra Professional online - Vardenafil does not affect the seminal fluid and is not addictive.