Course Information

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

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

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.

M8150 Integer programming

Faculty of Science
Spring 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

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

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 2008.

M8150 Integer programming

Faculty of Science
Spring 2004

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

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

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 2006, Spring 2008.

M8150 Integer programming

Faculty of Science
Spring 2002

Extent and Intensity

2/1/0. 4 credit(s). 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 (in Czech)

M4110 Linear programming || M7100 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

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.

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

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 2004, Spring 2006, Spring 2008.

M8150 Integer programming

Faculty of Science
Spring 2000

Extent and Intensity

2/1/0. 4 credit(s). 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 (in Czech)

M4110 Linear 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)

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.

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

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 2002, Spring 2004, Spring 2006, Spring 2008.

M8150 Integer programming

Faculty of Science
Spring 2025

The course is not taught in Spring 2025

Extent and Intensity

2/1/0. 3 credit(s) (příf plus uk k 1 zk 2 plus 1 > 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
Supplier department: Department of Mathematics and Statistics – Departments – Faculty of Science

Prerequisites

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 integer linear 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.
Course objectives: After passing the course the student should be able to find one's way in the theoretical foundations of integer linear programming, he should manage the arithmetical techniques derived from the Gomory algorithms making it possible to solve by hands concrete small integer linear programming problems, and he should also be able to apply the methods based on implicit enumeration and using linear programming relaxations to solve some 0-1 integer programming problems, such as the 0-1 knapsack problem, for example.

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

Teaching of this course consists of lectures supplemented with seminars. The course is completed with written examination.

Language of instruction

Czech

Further comments (probably available only in Czech)

Course is no more offered.
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, Spring 2008.

M8150 Integer programming

Faculty of Science
Spring 2024

The course is not taught in Spring 2024

Extent and Intensity

2/1/0. 3 credit(s) (příf plus uk k 1 zk 2 plus 1 > 4). Type of Completion: zk (examination).

Teacher(s)

doc. RNDr. Jiří Kaďourek, CSc. (lecturer)

Guaranteed by

Prerequisites

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

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

Teaching of this course consists of lectures supplemented with seminars. The course is completed with written examination.

Language of instruction

Czech

Further comments (probably available only in Czech)

Course is no more offered.
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, Spring 2008.

M8150 Integer programming

Faculty of Science
Spring 2023

The course is not taught in Spring 2023

Extent and Intensity

2/1/0. 3 credit(s) (příf plus uk k 1 zk 2 plus 1 > 4). Type of Completion: zk (examination).

Teacher(s)

doc. RNDr. Jiří Kaďourek, CSc. (lecturer)

Guaranteed by

Prerequisites

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

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

Teaching of this course consists of lectures supplemented with seminars. The course is completed with written examination.

Language of instruction

Czech

Further comments (probably available only in Czech)

Course is no more offered.
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, Spring 2008.

M8150 Integer programming

Faculty of Science
Spring 2022

The course is not taught in Spring 2022

Extent and Intensity

2/1/0. 3 credit(s) (příf plus uk k 1 zk 2 plus 1 > 4). Type of Completion: zk (examination).

Teacher(s)

doc. RNDr. Jiří Kaďourek, CSc. (lecturer)

Guaranteed by

Prerequisites

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

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

Teaching of this course consists of lectures supplemented with seminars. The course is completed with written examination.

Language of instruction

Czech

Further comments (probably available only in Czech)

Course is no more offered.
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, Spring 2008.

M8150 Integer programming

Faculty of Science
Spring 2021

The course is not taught in Spring 2021

Extent and Intensity

2/1/0. 3 credit(s) (příf plus uk k 1 zk 2 plus 1 > 4). Type of Completion: zk (examination).

Teacher(s)

doc. RNDr. Jiří Kaďourek, CSc. (lecturer)

Guaranteed by

Prerequisites

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

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

Teaching of this course consists of lectures supplemented with seminars. The course is completed with written examination.

Language of instruction

Czech

Further comments (probably available only in Czech)

Course is no more offered.
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, Spring 2008.

M8150 Integer programming

Faculty of Science
Spring 2020

The course is not taught in Spring 2020

Extent and Intensity

2/1/0. 3 credit(s) (příf plus uk k 1 zk 2 plus 1 > 4). Type of Completion: zk (examination).

Teacher(s)

doc. RNDr. Jiří Kaďourek, CSc. (lecturer)

Guaranteed by

Prerequisites

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

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

Teaching of this course consists of lectures supplemented with seminars. The course is completed with written examination.

Language of instruction

Czech

Further comments (probably available only in Czech)

Course is no more offered.
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, Spring 2008.

M8150 Integer programming

Faculty of Science
Spring 2019

The course is not taught in Spring 2019

Extent and Intensity

2/1/0. 3 credit(s) (příf plus uk k 1 zk 2 plus 1 > 4). Type of Completion: zk (examination).

Teacher(s)

doc. RNDr. Jiří Kaďourek, CSc. (lecturer)

Guaranteed by

Prerequisites

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

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

Teaching of this course consists of lectures supplemented with seminars. The course is completed with written examination.

Language of instruction

Czech

Further comments (probably available only in Czech)

Course is no more offered.
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, Spring 2008.

M8150 Integer programming

Faculty of Science
spring 2018

The course is not taught in spring 2018

Extent and Intensity

2/1/0. 3 credit(s) (příf plus uk k 1 zk 2 plus 1 > 4). Type of Completion: zk (examination).

Teacher(s)

doc. RNDr. Jiří Kaďourek, CSc. (lecturer)

Guaranteed by

Prerequisites

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

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

Teaching of this course consists of lectures supplemented with seminars. The course is completed with written examination.

Language of instruction

Czech

Further comments (probably available only in Czech)

Course is no more offered.
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, Spring 2008.

M8150 Integer programming

Faculty of Science
Spring 2017

The course is not taught in Spring 2017

Extent and Intensity

2/1/0. 3 credit(s) (příf plus uk k 1 zk 2 plus 1 > 4). Type of Completion: zk (examination).

Teacher(s)

doc. RNDr. Jiří Kaďourek, CSc. (lecturer)

Guaranteed by

Prerequisites

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

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

Teaching of this course consists of lectures supplemented with seminars. The course is completed with written examination.

Language of instruction

Czech

Further comments (probably available only in Czech)

Course is no more offered.
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, Spring 2008.

M8150 Integer programming

Faculty of Science
Spring 2016

The course is not taught in Spring 2016

Extent and Intensity

2/1/0. 3 credit(s) (příf plus uk k 1 zk 2 plus 1 > 4). Type of Completion: zk (examination).

Teacher(s)

doc. RNDr. Jiří Kaďourek, CSc. (lecturer)

Guaranteed by

Prerequisites

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

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

Teaching of this course consists of lectures supplemented with seminars. The course is completed with written examination.

Language of instruction

Czech

Further comments (probably available only in Czech)

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, Spring 2008.

M8150 Integer programming

Faculty of Science
Spring 2015

The course is not taught in Spring 2015

Extent and Intensity

2/1/0. 3 credit(s) (příf plus uk k 1 zk 2 plus 1 > 4). Type of Completion: zk (examination).

Teacher(s)

doc. RNDr. Jiří Kaďourek, CSc. (lecturer)

Guaranteed by

Prerequisites

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

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

Teaching of this course consists of lectures supplemented with seminars. The course is completed with written examination.

Language of instruction

Czech

Further comments (probably available only in Czech)

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, Spring 2008.

M8150 Integer programming

Faculty of Science
Spring 2014

The course is not taught in Spring 2014

Extent and Intensity

2/1/0. 3 credit(s) (příf plus uk k 1 zk 2 plus 1 > 4). Type of Completion: zk (examination).

Teacher(s)

doc. RNDr. Jiří Kaďourek, CSc. (lecturer)

Guaranteed by

Prerequisites

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

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

Teaching of this course consists of lectures supplemented with seminars. The course is completed with written examination.

Language of instruction

Czech

Further comments (probably available only in Czech)

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, Spring 2008.

M8150 Integer programming

Faculty of Science
Spring 2013

The course is not taught in Spring 2013

Extent and Intensity

2/1/0. 3 credit(s) (příf plus uk k 1 zk 2 plus 1 > 4). Type of Completion: zk (examination).

Teacher(s)

doc. RNDr. Jiří Kaďourek, CSc. (lecturer)

Guaranteed by

Prerequisites

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

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

Teaching of this course consists of lectures supplemented with seminars. The course is completed with written examination.

Language of instruction

Czech

Further comments (probably available only in Czech)

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, Spring 2008.

M8150 Integer programming

Faculty of Science
Spring 2012

The course is not taught in Spring 2012

Extent and Intensity

2/1/0. 3 credit(s) (příf plus uk k 1 zk 2 plus 1 > 4). Type of Completion: zk (examination).

Teacher(s)

doc. RNDr. Jiří Kaďourek, CSc. (lecturer)

Guaranteed by

Prerequisites

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

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

Teaching of this course consists of lectures supplemented with seminars. The course is completed with written examination.

Language of instruction

Czech

Further comments (probably available only in Czech)

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, Spring 2008.

M8150 Integer programming

Faculty of Science
Spring 2011

The course is not taught in Spring 2011

Extent and Intensity

2/1/0. 3 credit(s) (příf plus uk k 1 zk 2 plus 1 > 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

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

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

Teaching of this course consists of lectures supplemented with seminars. The course is completed with written examination.

Language of instruction

Czech

Further comments (probably available only in Czech)

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, Spring 2008.

M8150 Integer programming

Faculty of Science
Spring 2010

The course is not taught in Spring 2010

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

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

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

Teaching of this course consists of lectures supplemented with seminars. The course is completed with written examination.

Language of instruction

Czech

Further comments (probably available only in Czech)

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, Spring 2008.

M8150 Integer programming

Faculty of Science
Spring 2009

The course is not taught in Spring 2009

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

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

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

Teaching of this course consists of lectures supplemented with seminars. The course is completed with written examination.

Language of instruction

Czech

Further comments (probably available only in Czech)

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, Spring 2008.

M8150 Integer programming

Faculty of Science
Spring 2007

The course is not taught in Spring 2007

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

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

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, Spring 2008.

M8150 Integer programming

Faculty of Science
Spring 2005

The course is not taught in Spring 2005

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

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

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, Spring 2008.

M8150 Integer programming

Faculty of Science
Spring 2001

The course is not taught in Spring 2001

Extent and Intensity

2/1/0. 4 credit(s). 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 (in Czech)

M4110 Linear 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

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

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, Spring 2008.

M8150 Integer programming

Faculty of Science
Spring 2008 - for the purpose of the accreditation

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 Complex Analysis
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

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 2000, Spring 2002, Spring 2004, Spring 2006, Spring 2008.

M8150 Integer programming

Faculty of Science
spring 2012 - acreditation

The course is not taught in spring 2012 - acreditation

The information about the term spring 2012 - acreditation is not made public

Extent and Intensity

2/1/0. 3 credit(s) (příf plus uk k 1 zk 2 plus 1 > 4). Type of Completion: zk (examination).

Teacher(s)

doc. RNDr. Jiří Kaďourek, CSc. (lecturer)

Guaranteed by

Prerequisites

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

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

Teaching of this course consists of lectures supplemented with seminars. The course is completed with written examination.

Language of instruction

Czech

Further comments (probably available only in Czech)

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, Spring 2008.

M8150 Integer programming

Faculty of Science
Spring 2011 - only for the accreditation

The course is not taught in Spring 2011 - only for the accreditation

Extent and Intensity

2/1/0. 3 credit(s) (příf plus uk k 1 zk 2 plus 1 > 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

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

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

Teaching of this course consists of lectures supplemented with seminars. The course is completed with written examination.

Language of instruction

Czech

Further comments (probably available only in Czech)

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, Spring 2008.

Enrolment Statistics (recent)

Course Information

M8150 Integer programming

M8150 Integer programming

M8150 Integer programming

M8150 Integer programming

M8150 Integer programming

M8150 Integer programming

M8150 Integer programming

M8150 Integer programming

M8150 Integer programming

M8150 Integer programming

M8150 Integer programming

M8150 Integer programming

M8150 Integer programming

M8150 Integer programming

M8150 Integer programming

M8150 Integer programming

M8150 Integer programming

M8150 Integer programming

M8150 Integer programming

M8150 Integer programming

M8150 Integer programming

M8150 Integer programming

M8150 Integer programming

M8150 Integer programming

M8150 Integer programming

M8150 Integer programming

M8150 Integer programming

M8150 Integer programming

Other applications