Discrete optimization

The course can be part of the following programmes:

1. Computer Science, Master's Programme (N2COS)
2. Applied Data Science, Master's Programme (N2ADS)
3. Software Engineering and Management, Master's Programme (N2SOF)
4. Computer Science, Bachelor's Programme (N1COS)
5. Mathematical Sciences, Master's Programme (N2MAT)

• 7,5 credits programming in high level language like Java, Python etc
• 7,5 credits basic course in calculus/analysis
• 7,5 credits basic course in linear algebra

Applicants must prove knowledge of English: English 6/English level 2 or the equivalent level of an internationally recognized test, for example TOEFL, IELTS.

The course gives an introduction to modelling various optimization problems using linear programming (LP) and integer linear programming (ILP). The Simplex algorithm to solve LPs is described and analysed. The LP relaxations of ILPs are studied and analysed to design approximation algorithms. The duality theory of linear programs is studied and used to design approximation algorithms. Vector programs to model discrete optimization problems are described and relaxed to semi-definite programs (SDPs).

After completion of the course the student should be able to:

Knowledge and understanding

• Describe what is a linear program (LP) and an integer linear program (ILP).
• Describe the geometry of a LP by visualizing it graphically.
• Describe the relationship between an ILP and its LP relaxation.

Competence and skills

• Formulate a continuous optimization problem as an LP.
• Formulate a discrete optimization problem as an ILP and relax it to an LP, and recover approximate discrete solution to the original problem from the optimal LP.
• Solve an LP using the Simplex algorithm.
• Formulate the dual of an LP and relate it to the original LP.
• Use LP duality to design optimization algorithms.
• Formulate discrete optimization problems as a vector program, relax it to an SDP and recover a discrete solution to the original problem.

Judgement and approach

• Recognize which optimization formulation is appropriate to a given problem.
• Judge which algorithm works efficiently for a given optimization problem.

Lectures twice weekly and exercise sessions.

Language of instruction: English

The course is examined by a written exam (assignments could be used for bonus points).

If a student who has been failed twice for the same examination element wishes to change examiner before the next examination session, such a request is to be granted unless there are specific reasons to the contrary (Chapter 6 Section 22 HF).

If a student has received a certificate of disability study support from the University of Gothenburg with a recommendation of adapted examination and/or adapted forms of assessment, an examiner may decide, if this is consistent with the course’s intended learning outcomes and provided that no unreasonable resources would be needed, to grant the student adapted examination and/or adapted forms of assessment.

If a course has been discontinued or undergone major changes, the student must be offered at least two examination sessions in addition to ordinary examination sessions. These sessions are to be spread over a period of at least one year but no more than two years after the course has been discontinued/changed. The same applies to placement and internship (VFU) except that this is restricted to only one further examination session.

If a student has been notified that they fulfil the requirements for being a student at Riksidrottsuniversitetet (RIU student), to combine elite sports activities with studies, the examiner is entitled to decide on adaptation of examinations if this is done in accordance with the Local rules regarding RIU students at the University of Gothenburg.

Sub-courses

1. Written hall examination, 7.5 credits
   Grading scale: Pass with distinction (5), Pass with credit (4), Pass (3) and Fail (U)

To pass the course, all mandatory components must be passed. To earn a higher grade than Pass, a higher weighted average from the grades of the components is required.

The course is evaluated through meetings both during and after the course between teachers and student representatives. Further, an anonymous questionnaire is used to ensure written information. The outcome of the evaluations serves to improve the course by indication which parts could be added, improved, changed or removed.

The course is a joint course together with Chalmers.

The course replaces the course DIT370, 7.5 credits. The course cannot be included in a degree which contains DIT370. Neither can the course be included in a degree which is based on another degree in which the course DIT370 is included.