THE UNIVERSITY of EDINBURGH

DEGREE REGULATIONS & PROGRAMMES OF STUDY 2020/2021

Information in the Degree Programme Tables may still be subject to change in response to Covid-19

University Homepage
DRPS Homepage
DRPS Search
DRPS Contact
DRPS : Course Catalogue : School of Mathematics : Mathematics

Postgraduate Course: Integer and Combinatorial Optimization (MATH11192)

Course Outline
SchoolSchool of Mathematics CollegeCollege of Science and Engineering
Credit level (Normal year taken)SCQF Level 11 (Postgraduate) AvailabilityAvailable to all students
SCQF Credits10 ECTS Credits5
SummaryIn many optimization problems, the solution is found among a set of finite elements. However, exhaustive search is usually prohibitive and, thus, specialized mathematical techniques must be used to explore the solution space in an efficient way. This course will study exact and heuristic methods for solving several of the most important integer and combinatorial optimization problems.
Course description In many optimization problems, the solution is found among a set of finite elements. Typical such problems are routing problems, matching problems or scheduling problems. However, the space search can be very large (combinatorial explosion) and, as a consequence, exhaustive search is usually prohibitive. Therefore, specialized mathematical techniques must be used to explore the solution space in an efficient way. In order to study these techniques, it is important to understand fundamental notions from integer programming and graphs theory (total unimodularity, matching, spanning tree, etc.) as well as general techniques (lagrangean relaxation, branch-and-cut, metaheuristics).

This course will study exact and heuristic methods for solving several of the most important integer and combinatorial optimization problems. We will first cover some basic notions in integer programming and graph theory. Later, they will be applied to the study of specific problems and solution algorithms.

1. Integer Programming. Total Unimodularity. Valid Inequalities and Preprocessing.
2. Solution Algorithms. Branch-and-Cut. Lagrangean Relaxation. Metaheuristics.
3. Matching Problems. The Assignment Problem.
4. Network Problems. Spanning Trees.
5. Covering Problems.
6. The Traveling Salesman Problem. Heuristics for the TSP.
7. Other Applications: Knapsack Problems, Scheduling Problems.
Entry Requirements (not applicable to Visiting Students)
Pre-requisites Students MUST have passed: Fundamentals of Operational Research (MATH10065) AND Fundamentals of Optimization (MATH11111)
Co-requisites
Prohibited Combinations Other requirements None
Information for Visiting Students
Pre-requisitesVisiting students are advised to check that they have studied the material covered in the syllabus of each prerequisite course before enrolling.
High Demand Course? Yes
Course Delivery Information
Academic year 2020/21, Available to all students (SV1) Quota:  None
Course Start Semester 2
Timetable Timetable
Learning and Teaching activities (Further Info) Total Hours: 100 ( Lecture Hours 20, Seminar/Tutorial Hours 5, Summative Assessment Hours 2, Programme Level Learning and Teaching Hours 2, Directed Learning and Independent Learning Hours 71 )
Assessment (Further Info) Written Exam 50 %, Coursework 50 %, Practical Exam 0 %
Additional Information (Assessment) There will be two assessments, each worth 25% of the final mark. There will be one week for submitting each assessment. The first assessment will be published on Week 5 and the second on Week 10.
Feedback Feedback in writing.
Exam Information
Exam Diet Paper Name Hours & Minutes
Main Exam Diet S2 (April/May)Integer and Combinatorial Optimization (MATH11192)1:30
Learning Outcomes
On completion of this course, the student will be able to:
  1. Identify optimization problems which require integer variables.
  2. Formulate mathematical models for integer and combinatorial optimization problems.
  3. Identify and apply suitable solution techniques for integer and combinatorial optimization problems.
  4. Demonstrate an understanding of the theoretical results behind integer and combinatorial optimization, e.g., by proving unfamiliar results or applying them to unfamiliar problems.
Reading List
Combinatorial Optimization: Theory and Algorithms. B. Korte and J. Vygen. 5th edition. Springer (2012).
Combinatorial Optimization. W. Cook, W.H. Cunningham, W.R. Pulleyblank, A. Schrijver. Wiley (1998).
Integer and Combinatorial Optimization. G.L. Nemhauser and L.A. Wolsey. Wiley (1988).
Integer Programming. L.A. Wolsey. Wiley (1998).
Additional Information
Graduate Attributes and Skills Not entered
KeywordsICO,Combinatorial Optimization,Integer Programming,Algorithms
Contacts
Course organiserDr Sergio Garcia Quiles
Tel: (0131 6)50 5038
Email: Sergio.Garcia-Quiles@ed.ac.uk
Course secretaryMiss Gemma Aitchison
Tel: (0131 6)50 9268
Email: Gemma.Aitchison@ed.ac.uk
Navigation
Help & Information
Home
Introduction
Glossary
Search DPTs and Courses
Regulations
Regulations
Degree Programmes
Introduction
Browse DPTs
Courses
Introduction
Humanities and Social Science
Science and Engineering
Medicine and Veterinary Medicine
Other Information
Combined Course Timetable
Prospectuses
Important Information