M8150 Integer programming

Faculty of Science
Spring 2008
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
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
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
  • NEMHAUSER, George L. and Laurence A. WOLSEY. Integer and Combinatorial Optimization. New York: John Wiley & Sons, 1988, 763 pp. ISBN 0-471-82819-X. info
  • SCHRIJVER, Alexander. Theory of Linear and Integer Programming. Chichester: John Wiley & Sons, 1986, 471 pp. ISBN 0 471 90854 1. info
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.
The course is also listed under the following terms Spring 2008 - for the purpose of the accreditation, Spring 2000, Spring 2002, Spring 2004, Spring 2006.
  • Enrolment Statistics (recent)
  • Permalink: https://is.muni.cz/course/sci/spring2008/M8150