NETWORK OPTIMIZATION

Prerequisites

Basic knowledge of: Discrete Mathematics, Linear Programming, Algorithms and Data Structures, Computational complexity. Basic coding skills.

Contents

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
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 Problem.

Assessment methods

Lectures. Practice with MILP solvers.