Current postgraduate taught students
COMP60342: Optimization for learning, planning and problem-solving (2012-2013)
This is an archived syllabus from 2012-2013
Credit rating: 15
Pre-requisites: No Pre-requisites
Co-requisites: No Co-requisites
Course Leader: Joshua Knowles
Course leader: Joshua Knowles
Additional staff: view all staff
| Semester | Event | Location | Day | Time | Group |
|---|---|---|---|---|---|
| Sem 2 P4 | Lecture | 2.15 | Fri | 09:00 - 17:00 | - |
Coursework: 40%
Lab: 0%
- Information Management 2
- Reasoning and Optimisation
Introduction
A wealth of problems encountered in computer science and the wider world can be viewed as discrete optimization problems, and solved by various types of search procedure. Although optimization problems come in a great variety, we find that they can be grouped into a few large classes that admit common methods of solution. This means that with a basic toolbox of knowledge and methods, it is relatively simple to tackle problems ranging from scheduling the launch time of a space mission to choosing the next move in chess, and from optimizing caching strategies to satisfying large systems of logical clauses.
Aims
In this course we will study the main classes of algorithmic techniques that can be applied to discrete optimization problems. We will consider how these techniques can be applied in a number of practical problems in machine learning, logical problem-solving and operational planning, and how the key features of these problems govern the choice of algorithm.
| Programme outcome | Unit learning outcomes | Assessment |
|---|---|---|
| A1 A2 | Gain a broad understanding of discrete optimization, including an appreciation of how it supports machine learning, operations management and planning, and general computer problem-solving. | |
| B3 | Develop personal problem-solving skills and algorithmic thinking. | |
| A1 A2 A3 | Gain experience in applying and developing algorithms for a range of practical discrete optimization problems. | |
| C4 | Gain an introduction to the current literature on optimization methods. |
Syllabus
We will cover the following topics:
- The general nonconvex discrete optimization problem with constraints
- Constraint satisfaction problems as optimization (SAT and MAX-SAT)
- Complexity and the theory of NP-completeness
- Graphs and other discrete structures
- Greedy search
- Enumeration / exhaustive search
- Dynamic programming, branch-and-bound
- Approximation algorithms and randomization
- Heuristics: local search, tabu search, evolutionary algorithms
- Multiobjective Optimization
- Applications in machine learning, logic and operational planning / logistics
Reading List
Core Text
Title: Combinatorial optimization: algorithms and complexityAuthor: Papadimitriou, Christos H. and Kenneth Steiglitz
ISBN: 9780486402581
Publisher: Dover
Edition:
Year: 2000
Supplementary Text
Title: Dynamic programming: a practical introductionAuthor: Smith, David Kendall
ISBN: 013221797X
Publisher: Ellis Horwood
Edition:
Year: 1991
Supplementary Text
Title: Integer programmingAuthor: Wolsey, Laurence A.
ISBN: 0471283665
Publisher: Wiley
Edition:
Year: 1998
Supplementary Text
Title: Multi-objective optimization using evolutionary algorithmsAuthor: Deb, Kalyanmoy
ISBN: 9780470743614
Publisher: Wiley
Edition:
Year: 2008