**Extended Multiroute Flow for Multilink Attack Networks**

**(拡張マルチルートフローとマルチリンク攻撃問題への応用)**

**Jean-François Alexis Baffier**

**バフィエール ジャンフランソワ アレクシ**

**The University of Tokyo**

**Imai Laboratory/JFLI(CNRS)**

**Supervisor: Hiroshi Imai**

**Co-Supervisor: Abdel Lisser**

**Vorapong Suppakitpaisarn (NII - ERATO)**

Hidefumi Hiraishi (Todai)

Wenkai Dai (Universitat des Saarlandes)

Hidefumi Hiraishi (Todai)

Wenkai Dai (Universitat des Saarlandes)

**Network Flow**

**MLA Flows**

**MLA-Robust**

MLA-Reliable

MLA-Decomposition

Complexity

MLA-Reliable

MLA-Decomposition

Complexity

**History**

Algorithms

Under Attacks

Algorithms

Under Attacks

**Multiroute Flow**

**History**

Properties

Algorithms

Properties

Algorithms

**Extended**

Multiroute Flow

Multiroute Flow

**h is non-integer parameter**

solves MLA-Robust Flow

capacity-differentiation

solves MLA-Robust Flow

capacity-differentiation

**Experiments**

**Efficiency of EMRF**

Gap between bounds

Integral mapping

Gap between bounds

Integral mapping

Flow in Network

max-flow

History

Algorithms

Attacks

Network

Flow

Cut

Duality

Soviet railway network (Harris and Ross, 1955)

Ford-Fulkerson: general case, algorithm, max-flow/min-cut duality (1956)

Edmonds-Karp: polytime algorithm (1972)

Applications include:

Network management

Computer vision

Task scheduling

Multilink-Attack (MLA)

MLA-robust

MLA-reliable

MLA-effectiveness

Definition

Related

Properties

MLA-decomposition

MLA-attack (finding the best k attacks on a given flow) is NP-hard, by Wenkai Dai and Vorapong Suppakitpaisarn.

MLA-Reliable NP-hard for integral case (new result)

Special case of minimax problem by Lee, Misra, and Rubenstein that is solved heuristically.

Multiroute Flow

Definition

Variants

About

History

Applications

Algorithms

(k+1)-approximation

Inequalities

Implications

Bounds

Extended Multiroute Flow (EMRF)

Extensions

Capacity

differentiation

Solution to MLA-flows

Improvements

Tighter bounds

Average Speed

Completed Multiroute Flow

Bad Example

IMRF

Iterative Multiroute Flow

source s, sink t

edge-connectivity \lambda

Number of attacks k

Not a max-flow in the general case

No NP-hardness proved (*)

A solution to the max-(k+1)-route flow problem is also a (k+1)-approximation to the MLA-robust flow, the MLA-reliable flow , and the MLA-decomposition problems.

Theorem

Experiments

Bounds and IMRF

Efficiency of EMRF

Settings

Mapping & Integers

Contributions

Definition of MLA-robust flow, MLA-reliable flow, and other MLA problems

NP-hardness of MLA-robust flow

Analysis of Extended Multiroute Flow algorithms

Relations between Multiroute and MLA-robust flows:

A (k+1)-approximation algorithm

EMRF solves MLA-robust flow for a class of network

Results hold for MLA-reliable

Classification of instances (EMRF-solvable, Flying Cut)

Experiments (through our c++ library):

EMRF is efficient on many instances, but R-MAT

Approximation algorithm is under 80% gap on R-MAT

IMRF is fast and efficient in pratice

A feasible flow is a linear combination of elementary paths from s to t under the capacity constraint.

Its value is the sum of the linear coefficients.

A solution to the max-flow problem is a feasible flow with the maximum flow value.

A cut is a partition of the nodes in two subsets. Its capacity is the sum of the links from the source side to the sink side.

The value of a max-flow is equal to the value of a min-cut.

The first max-flow algorithm is based on an augmenting path approach. Edmonds&Karp improved it to a polytime version.

The push-relabel method is the fastest on the average on practical cases.

Here k=1

Two cases:

The attacker strike first (MLA-robust)

First comes the flow (MLA-reliable)

A solution to MLA-robust flow is a max-flow with the maximum value on the network after deleting any set of k links.

The attacker strikes first. Then a flow is routed from the source to the sink.

Given a flow F, its MLA-effectiveness is the minimum value left of F after any set of k attacks on the network.

This problem has a value in itself and is proved to be NP-hard by Wenkai Dai and Vorapong Suppakitpaisarn.

A solution to MLA-reliable flow is flow with a maximum MLA-effectiveness.

In this situation, the attacker knows the flow repartition on the link and strike after the construction of a flow.

(*) We proved the NP-hardness for integral flow case last week. Reduction from Hamiltonian Circuit.

A h-route flow (a multiroute flow of h routes) is a linear combination of h-links disjoint elementary paths from the source to the sink.

Its value is the sum of the linear coefficients.

max-2-route flow

Introduced by Kishimoto and Takeuchi in 1993 along with a polytime algorithm.

Aggarwal and Orlin (2002): improves complexity through the analyse of a restricted max-flow function.

Simpler duality proof by Bagchi et al. in 2004

Correctness and complexity proofs in 2006 by Du and Chandrasekaran.

Aggarwal and Orlin 2002:

Birkhoff's theorem can be generalized to matricees that are not doubly stochastic

Machine scheduling problem

Direct applications to robust flows

2-route flow guarantee the restoration of networks after one failure

In this work, it is apply to solve or approximate MLA-robust flow, MLA-reliable flow and MLA-decomposition.

All polytime algorithms use a parametric max-flow function.

This function is a restricted max-flow such that given a real value x, the capacity c on any link is equal to the minimum between c and x.

Kishimoto's algorithm

Binary search (integral capacities only)

Primal-dual algorithm

Kishimoto extended this notion to more general case with delta-relaible flow, and alikes.

A multi-commodity version is studied through linear programming.

NP-hardness of multi-commodity flow implies that the three polytime algorithm can not be used directly.

Any multiroute flow value is lower than the value of a MLA-reliable flow.

If a multiroute flow value is equal to the value of a MLA-robust flow, then MLA-reliable and MLA-robust flow values are equals.

The approximation ratio of the multoute flow can be really bad when k is huge.

There exist infinite graphs were the equality hold for each case.

The bound can be further improved when k is close to the connectivity lambda.

Two extensions from Aneja et al.:

The number of routes h can be non-integer (Aneja, Chandrasekaran, Kabadi, Nair, 2007)

h can be a parameter, O(n*T) algorithm (Aneja, Chandrasekaran, Nair, 2003)

Guaranted ratio of k+1 from multiroute flow

Lower determinisic bound to MLA-reliable flow from the pseudo-tangent projection

Upper heuristic bound to MLA-robust flow from the duality of MLA-robust flow and cut

Speed-up twice by skipping at most half of the breakpoints (if no switching cut)

Reduce heuristically the step to the minimal number of switching cut (but can fail)

Construct a reliable flow by iterating multiroute flow algorithms.

Start with a lambda-route flow.

Then compe a (lambda-1)-route flow on the residual network. And so on till h=1.

Finally, sum the multiroute flow.

Guarantee a high tolerance to any number of failures. Can be far from the optimal value.

Each setup contains 1000 networks, and each network lead to lambda instances.

Complete network: n in [4,256]

2D grid: n in [4,64] on each dimension

3D grid: n in [4,8] on each dimension

Random shape: n in [4,256], m in [n,2^n]

Link are generated randomly. Uniformly for grids and complete networks. Following 5 distributions for random-shape networks.

R-MAT

Publications

(Accepted)

Submissions

(acceptance should be known in January or February for LAGOS 2015 and Discrete Optimization)

Future Works

Class Diagram

About me

Introduction

Problem

Number of attacks k (here k=1)

Goldberg and Tarjan (2014)

Related Works

Max-flow

Soviet railway network (Harris and Ross, 1955)

Ford-Fulkerson: general case, algorithm, max-flow/min-cut duality (1956)

Edmonds-Karp: polytime algorithm (1972)

Applications include:

Network management

Computer vision

Task scheduling

Duality

The value of a max-flow is equal to the value of a min-cut.

Multiroute flow

Introduced by Kishimoto and Takeuchi (1993)

h-route flow : multiroute flow of h routes

Combinations of edge-disjoint paths with the same value

Extension of Duality to multiroute flow/cut

max-2-route flow

Algorithms

n nodes

m links

f max-flow value

U highest capacity

A max-h-route flow can be computed in h max-flow iterations

Kishimoto and Takeuchi (1993)

Aggarwal and Orlin (2002)

Improved to min[log(hU),h] max-flow iterations)

Overview

Network Flow

Multiroute Flow

Extended

Multiroute Flow

Grouped and analyzed

Average Speed-up

Multilink-Attack Network Flow

Definitions, analysis,

duality, complexity

Exact Algorithm

Class of instances

Capacity Differentiation

Approximation

k+1 approximation

Heuristic Upper Bound

Deterministic Lower Bound

Experiments

Network Synthesis

Maximum Flow (max-flow)

source

sink

Maximum Flow of value 6 from s to t

[· · · ], algorithm design techniques and data structures developed to compute maximum flows are useful for other problems as well. Although a special case of linear programming, the maximum flow problem is general enough so several important problems (such as the maximum bipartite matching problem) reduce to it.

Motivations

Network management

Tolerance to attacks or failures (recovery)

Resources consumption (energy, infrastructures)

MLA-robust flow shares max-flow properties

Computer Vision, Distribution Network

Stock Management, Task Scheduling

State-of-the-art (need of a trade-of)

Efficient algorithm on specific problems

Very broad problem often too complex or hard

Max-2-route flow

Multiroute Flow (max-h-route flow)

No attack

max-2-route flow = 10; max-flow = 10

One attack

max-2-route flow = 5; max-flow = 6

Contribution 1

MLA-robust flow

Number of attack k

Definition

MLA-robust duality

Definition (MLA-robust capacity)

Lemma 3.1

Definition (MLA-robust cut)

MLA-reliable flow

Definition (MLA-effectiveness)

Definition (MLA-reliable)

MLA-decomposition

Similar to MLA-reliable flow, but the attacker also know the routing information at the nodes.

Bad decomposition

Best Decomposition

(MLA-decomposition)

Exact Algorithm

Multiroute & MLA-robust cuts

Extended Multiroute Flow

s-t connectivity λ

restricted max-flow:

λ+1 parts (at most)

algorithm in O(λmn)

Extensions: (Aneja et al.)

non-integer

number of routes h (2007)

route-parametric

multiroute flow (2003)

Main Theorem (Corollary 3.9)

Informal:

**Contribution 3**

Flying Cut

EMRF does not detect the "Flying Cuts"

However, an approximation algorithm exists

The cut separating s and a

is the solution for 1 attack

The cut separating b and t

is the one detected by EMRF

k+1 approximation

Theorem 3.4

MLA-decomposition

MLA-reliable

MLA-robust

Guaranteed

max-(k+1)-route

Bounds

Heuristic upper bound (MLA-robust duality)

Deterministic lower bound of MLA-reliable (Extended Multiroute Flow)

Other results

Complexity: MLA-robust flow is NP-hard

Heuristic approximation algo: iterative multiroute flow

By W. Dai and V. Suppakitpaisarn:

MLA-attack of a decomposition is NP-hard

MLA-effectiveness of a flow is NP-hard

Compute a multiroute flow at each step

max-λ-route flow, then max-(λ-1)-route flow on residual network, and so on. Complexity: O(λ²mn)

Exact algorithm improvements (EMRF)

Speed average run-time: deterministic and heuristic

Capacity differentiation: enlarge class EMRF-solvable

Experiments

Classical flow versus completed multiroute flow

z

Success of exact algorithm (EMRF)

Approximation: gap bounds

COCOON 2015 (submit next month)

J.-F. Baffier, W. Dai, and V. Suppakitpaisarn

LAGOS 2015 (results February 3rd)

J.-F. Baffier, W. Dai, and V. Suppakitpaisarn

Discrete Optimization Special Issue (ISCO 2014)

J.-F. Baffier, V. Suppakitpaisarn, H. Hiraishi, H. Imai

WALCOM 2014

J.-F. Baffier and V. Suppakitpaisarn

ISCO 2014

J.-F. Baffier, V. Suppakitpaisarn, H. Hiraishi, H. Imai

TJIA 2014

V. Suppakitpaisarn and J.-F. Baffier

Broaden the scope of instances solved

Spectral Graph Theory

Wider field of problems

Variety of constraints

max-flow/min-cost

Real word flow constraints (CSP?)

Best MLA-flow

Candidate: Iterative Multiroute Flow

Resources optimization (at synthesis and use)

k=1 attack (red edge)

(Submitted)

HSPR 2015

Discrete Optimization (Special Issue ISCO 14)

MLA-robust

MLA-reliable

1. attacker strike

2. compute flow

1. compute flow

2. attacker strike

Contributions

Previous Works

Introduction and Analysis of Multilink-Attack (MLA) Network flows

MLA-robust flow

Duality of MLA-robust flow and cut

MLA-reliable flow

MLA-decomposition

**Contribution 2**

Analyze of Extended

Multiroute Flow (EMRF)

Relation between Multiroute cut and MLA-robust cut

Necessary condition for polytime algorithm

Flying cut (problematic case)

Approximation algorithm

max-(k+1)-route flow is a (k+1)-approximation algorithm to MLA-robust, MLA-reliable and MLA-decomposition

Upper Bound (duality of MLA-robust cut/flow)

Lower Bound (analysis of EMRF algorithm)

construct pairs of edge-disjoint paths with the same value (a pair of paths cannot share any common link)

Contributions

Max-h-route flow

(maximum multiroute flow of h routes)

max-2-route flow: guarantee a value of 5 after 1 attack

Definition:

A multiroute flow of h route is a combination of h edge-disjoint paths with the same value.

A max-h-route is multiroute flow of h routes with the maximum value.

min-h-route cut

MLA-robust cut

(k attacks)

By duality: relation between

multiroute flow and MLA-robust flow

Flow left = 2

Flow left = 3

(MLA-reliable flow)

Success rate of the EMRF algorithm on random shape networks

Success rate of EMRF algorithm on RMAT networks

Gap between the upper and lower bounds on random shape networks

Gap between upper and lower bounds on RMAT networks

Improvement of the multiroute flow over the classical max-flow

Bachelor/Master

at Paris-Sud

I was born in Paris (France)

Ph.D. at Todai

Post-Doc at ERATO Tohoku University

Network Flow (main topic)

Games

Game analysis (Skull&Roses board game)

Game AI (Starcraft, RTS games, Warhammer board game)

Alonso Gragera, Vorapong Suppakitpaisarn

Florian Richoux, Alberto Uriarte, Alonso Gragera

Search Algorithm (Local Search, Adaptive Search, CSP)

Application to both previous topics

Alex Fukunaga

Improvement of Search Methods

Salvador Abreu