# Course Details

#### Name:

**Network design / Network Design**

### Basic information

##### Credits:

*Master Degree in Computer Science:* 12 Ects (c)

##### Term:

*Module Network Flows:* 2° semester

*Module Network Optimization:* 2° semester

##### Degree(s):

Compulsory 1^{st} year Master Degree in Computer Science curriculum NEDAS

Compulsory 1^{st} year Master Degree in Computer Science curriculum UBIDIS

Elective 1^{st} year Master Degree in Mathematical Engineering curriculum Comune

##### Language:

English

### Course Objectives

**Module Network Flows:** Ability to recognize and formulate network flow problems
Knowledge of basic and advanced network flow algorithms
Ability to design resolution approaches to solve non standard network flow problems

**Module Network Optimization:** Ability to recognize and model network optimization problems as Integer Linear Programming problems.
Knowledge of fundamental algorithmic techniques for solving large scale Integer Linear Programming problems.
Knowledge of commercial and open source Integer Linear Programming solvers.

### Course Content

##### Module Network Flows

- Network Flows Problem: introduction and definitions
- Maximum Flows and the path packing problem.
Flows and cuts: Max-Flow/Min-Cut theorem.
Augmenting path algorithms: Ford and Fulkerson algorithm, Edmonds and Karp algorithm.
Generic Preflow-Push algorithm.
Flows with lower bounds.
- Maximum Flows: additional topics and applications.
Flows in Unit Capacity Networks.
Flows in Bipartite Networks.
Network Connectivity.
- Minimum Cuts.
Global Minimum Cuts.
Node Identification Algorithm.
Random Contraction.
Applications.
- Minimum-Cost Flow Problems.
Definition and applications.
Optimality Conditions.
The Ford-Bellman algorithm for the shortest path problem.
Primal algorithms: Augmenting Circuit Algorithm for the Min Cost Flow Problem.
- Network Simplex Algorithms.
Applications of Min Cost Flows.

##### Module Network Optimization

- Formulations of Integer and Binary Programs: The Assignment Problem; The Stable Set Problem; Set Covering, Packing and Partitioning; Minimum Spanning Tree; Traveling Salesperson Problem (TSP); Formulations of logical conditions.
- Mixed Integer Formulations: Modeling Fixed Costs; Uncapacitated Facility Location; Uncapacitated Lot Sizing; Discrete Alternatives; Disjunctive Formulations.
- Optimality, Relaxation and Bounds. Geometry of R^n: Linear and affine spaces; Polyhedra: dimension, representations, valid inequalities, faces, vertices and facets; Alternative (extended) formulations; Good and Ideal formulations.
- LP based branch-and-bound algorithm: Preprocessing, Branching strategies, Node and variable selection strategies, Primal heuristics.
- Cutting Planes algorithms. Valid inequalities. Automatic Reformulation: Gomory's Fractional Cutting Plane Algorithm. Strong valid inequalities: Cover inequalities, lifted cover inequalities; Clique inequalities; Subtour inequalities.
Branch-and-cut algorithm.
- Software tools for Mixed Integer Programming
- Lagrangian Duality: Lagrangian relaxation; Lagrangian heuristics.
- Network Problems: formulations and algorithms.
Constrained Spanning Tree Problems; Constrained Shortest Path Problem; Multicommodity Flows;
Symmetric and Asymmetric Traveling Salesman Problem; Vehicle Routing Problem
Steiner Tree Problem; Network Design.
Local Search
Tabu search and Simulated Annealing
MIP based heuristics
- Heuristics for network problems: local search, tabu search, simulated annealing, MIP based heuristics.

### Learning Outcomes (Dublin Descriptors)

On successful completion of this course, the student should

##### Module Network Flows

- Know and formulate network flow problems
- Model decision problems as network flow problems
Use base and advanced algorithms to solve network flow problems
- Ability to identify network flow models scope
- Ability to explain network flows models and algorithms
- Ability to learn state-of-art algorithms for network flow problems

##### Module Network Optimization

### Prerequisites and Learning Activities

**Module Network Flows:** Basic knowledge of:
Discrete Mathematics, Linear Programming, Algorithms and Data Structures, Computational complexity

**Module Network Optimization:** Basic knowledge of:
Discrete Mathematics, Linear Programming, Algorithms and Data Structures, Computational complexity.
Knowledge of at least one programming language.

### Teaching Methods

**Language**: English

**Module Network Flows:** Lectures

**Module Network Optimization:** Lectures and software training

### Assessment Methods and Criteria

**Module Network Flows:** Written text exam

**Module Network Optimization:** Written text exam and assignment

### Textbooks

##### Module Network Flows

- Cunningham, Pulleyblank, Schrijver ,
**Combinatorial Optimization**. * *
- Ahuja, Magnanti, Orlin,
**Network Flows**. * *

##### Module Network Optimization

- L.A. Wolsey,
**Integer Programming**. Wiley. 1998. * *

### Online Teaching Resources

### Course page updates

This course page is available (with possible updates) also for the following academic years:

*Course information last updated on: 10 settembre 2015, 10:50*