This is an introduction to mathematical foundations of discrete optimization and integer programming. In these topics one seeks to minimize or maximize a real function of integer variables, subject to constraints on the variables (equations or inequalities that need to be satisfied by all solutions). The main goals of the module are to describe the main mathematical properties of the discrete optimization problems, to introduce algorithms for finding optimal solutions and to show how these algorithms can be applied to a selection of classical optimization problems.

Recommended Modules: MA0358 Mathematical Programming

• Demonstrate understanding of basic geometry of polyhedra.
• Apply Chvatal-Gomory cutting plane algorithm to solve simple integer linear programs.
• Use the Minkowski fundamental theorems in the geometry of numbers.
• Apply lattice basis reduction algorithms to solve optimization problems over lattices.
• To formulate integer programming models for a selection of classical optimization problems.

27 - 50 minute lectures

Some handouts will be provided in hard copy or via Learning Central, but students will be expected to take notes of lectures.

Students are also expected to undertake at least 50 hours private study including preparation of solutions to given exercises.

Knowledge and Understanding:

The main properties of the lattices and convex sets, fundamentals of computational discrete geometry, algorithms of lattice basis reduction, algorithms for solving integer programming problems.

Skills:

Discrete optimization formulations for scientific and engineering problems

Formative assessment is carried out by means of regular tutorial exercises.  Feedback to students on their solutions and their progress towards learning outcomes is provided during lectures.  

The in-course element of summative assessment is a class test (taken under examination conditions), similar in form to the tutorial exercises. This allows students to demonstrate a level of knowledge and skills appropriate to that stage in the module.

The major component of summative assessment is the written examination at the end of the module.  This gives students the opportunity to demonstrate their overall achievement of learning outcomes.

• Geometry of Polyhedra
• Farkas-Minkowski-Weyl theorem
• Hilbert bases
• Chvatal-Gomory cutting planes
• Convex sets and lattices
• Minkowski's fundamental theorems
• Lattice reduction algorithms: Gauss and LLL algorithm

Theory of Linear and Integer Programming, Schrijver, A., Wiley, 1986

Not applicable.