PřF:M8150 Integer programming - Course Information
M8150 Integer programming
Faculty of ScienceSpring 2006
- Extent and Intensity
- 2/1/0. 3 credit(s) (fasci plus compl plus > 4). Type of Completion: zk (examination).
- Teacher(s)
- doc. RNDr. Jiří Kaďourek, CSc. (lecturer)
- Guaranteed by
- doc. RNDr. Jiří Kaďourek, CSc.
Department of Mathematics and Statistics – Departments – Faculty of Science
Contact Person: doc. RNDr. Jiří Kaďourek, CSc. - Prerequisites
- M4110 Linear programming || M5170 Mathematical Programming
It is necessary to go in advance either through the subject M4110 Linear programming or through the subject M5170 Mathematical Programming. - Course Enrolment Limitations
- The course is also offered to the students of the fields other than those the course is directly associated with.
- fields of study / plans the course is directly associated with
- Mathematics (programme PřF, M-MA)
- Mathematics (programme PřF, N-MA)
- Course objectives
- The contents of this subject consists of general algorithms for solving the linear integer programming problems. These algorithms can be classified in two groups. Cutting-plane algorithms form one such group. Typical representatives of this kind of algorithms are the Gomory algorithms. Another group of algorithms consists of methods based on implicit enumeration and using linear programming relaxations. Both approaches can be combined to yield more powerful procedures for solving the 0-1 integer programming problems, for instance.
- Syllabus
- Integer linear programming problems.
- The status of the integer linear programming problem.
- General cutting-plane algorithm.
- The Gomory fractional cutting-plane algorithm.
- The Gomory all-integer cutting-plane algorithm.
- General branch-and-bound algorithm.
- The branch-and-bound algorithm using linear programming relaxations.
- Dynamic programming and the knapsack problem.
- Solving the knapsack problem using a branch-and-bound algorithm.
- Solving the 0-1 integer programming problems using a cutting-plane/branch-and-bound algorithm.
- Literature
- Assessment methods (in Czech)
- Předmět je ukončen písemnou zkouškou.
- Language of instruction
- Czech
- Further Comments
- The course is taught once in two years.
The course is taught: every week.
- Enrolment Statistics (Spring 2006, recent)
- Permalink: https://is.muni.cz/course/sci/spring2006/M8150