Skip to navigation | Skip to main content | Skip to footer
Menu
Menu

This is an archived syllabus from 2014-2015

COMP60342 Optimization for Learning, Planning and Problem-Solving syllabus 2014-2015

COMP60342 Optimization for Learning, Planning and Problem-Solving

Level 6
Credits: 15
Enrolled students: 26

Course leader: Joshua Knowles


Additional staff: view all staff

Assessment methods

  • 60% Written exam
  • 40% Coursework
Timetable
SemesterEventLocationDayTimeGroup
Sem 2 P4 Lecture 2.15 Fri 09:00 - 13:00 -
Sem 2 P4 Lab 2.25 (A+B) Fri 13:00 - 17:00 -
Themes to which this unit belongs
  • Reasoning and Optimisation
  • Information Management 2

Overview

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.

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

Feedback methods

* Face-to-face individual feedback on lab/coursework
* Written feedback on coursework
* Oral and email feedback to the whole class covering common queries and/or misconceptions

Study hours

  • Assessment written exam (2 hours)
  • Lectures (20 hours)
  • Practical classes & workshops (15 hours)

Employability skills

  • Analytical skills
  • Innovation/creativity
  • Problem solving
  • Research
  • Written communication

Learning outcomes

Programme outcomeUnit learning outcomesAssessment
A1 A2Gain a broad understanding of discrete optimization, including an appreciation of how it supports machine learning, operations management and planning, and general computer problem-solving.
B3Develop personal problem-solving skills and algorithmic thinking.
A1 A2 A3Gain experience in applying and developing algorithms for a range of practical discrete optimization problems.
C4Gain an introduction to the current literature on optimization methods.

Reading list

TitleAuthorISBNPublisherYearCore
Combinatorial optimization: algorithms and complexityPapadimitriou, Christos H. and Kenneth Steiglitz9780486402581Dover2000
Multi-objective optimization using evolutionary algorithmsDeb, Kalyanmoy9780470743614Wiley2008
Dynamic programming: a practical introductionSmith, David Kendall013221797XEllis Horwood1991
Integer programmingWolsey, Laurence A.0471283665Wiley1998

Additional notes

Course unit materials

Links to course unit teaching materials can be found on the School of Computer Science website for current students.