# DEGREE REGULATIONS & PROGRAMMES OF STUDY 2018/2019

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

# Postgraduate Course: Integer and Combinatorial Optimization (MATH11192)

 School School of Mathematics College College of Science and Engineering Credit level (Normal year taken) SCQF Level 11 (Postgraduate) Availability Available to all students SCQF Credits 10 ECTS Credits 5 Summary In 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.
 Pre-requisites Students MUST have passed: Fundamentals of Operational Research (MATH10065) AND Fundamentals of Optimization (MATH11111) Co-requisites Prohibited Combinations Other requirements None
 Pre-requisites None High Demand Course? Yes
 Academic year 2018/19, 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) Coursework: 50% Exam: 50%. Feedback Not entered Exam Information Exam Diet Paper Name Hours & Minutes Main Exam Diet S2 (April/May) Integer and Combinatorial Optimization (MATH11192) 1:30
 On completion of this course, the student will be able to: Identify optimization problems which require integer variables.Formulate mathematical models for integer and combinatorial optimization problems.Identify and apply suitable solution techniques for integer and combinatorial.Understand the theoretical results behind integer and combinatorial optimization.Understand the relationship between the theoretical results and the solution algorithms in integer and combinatorial optimization.
 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).
 Graduate Attributes and Skills Not entered Keywords ICO,Combinatorial Optimization,Integer Programming,Algorithms
 Course organiser Dr Sergio Garcia Quiles Tel: (0131 6)50 5038 Email: Sergio.Garcia-Quiles@ed.ac.uk Course secretary Miss 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