Subject » BMEVISZMA09
Combinatorial Optimization
Kombinatorikus optimalizálás
A tantárgyleírás hatályossága
Hatályosság kezdete:
2026. March 21.
Hatályosság vége:
—
| Subject name (Hungarian, English) |
Kombinatorikus optimalizálás
Combinatorial Optimization
|
||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subject code | BMEVISZMA09 | ||||||||||||
| Subject type | — | ||||||||||||
| Training Level | — | ||||||||||||
| Course types and hours (weekly/semester) |
|
||||||||||||
| Assessment type | vizsga | ||||||||||||
| Credits | 5 | ||||||||||||
| Subject coordinator |
Fleiner Tamás
position: egyetemi tanár
contact:
fleiner.tamas@vik.bme.hu
|
||||||||||||
| Responsible department |
Számítástudományi és Információelméleti Tanszék
|
||||||||||||
| Faculty | Villamosmérnöki és Informatikai Kar | ||||||||||||
| Subject website | — | ||||||||||||
| Primary curriculum type | — | ||||||||||||
| Direct prerequisites – Strong prerequisite | none | ||||||||||||
| Direct prerequisites – Weak prerequisite | none | ||||||||||||
| Direct prerequisites – Parallel prerequisite | none | ||||||||||||
| Direct prerequisites – Milestone prerequisite | none | ||||||||||||
| Direct prerequisites – Exclusion | none |
Objectives
Programme
Network flows, Ford-Fulkerson algorithm, integrality lemma, generalizations of the flow problem.
Characterization of bipartite graphs, maximum matching in bipartite graphs. Theorems of Kőnig, Frobenius and Hall.
Graph colourings. Lower and upper bounds on the chromatic number. Edge colouring of graphs, Vizing's theorem. Edge colouring of bipartite graphs using the integrality lemma.
Egerváry's algorithm for finding maximum total weight matching and perfect matching in bipartite graphs.
Systems of linear inequalities, basic linear programming, solving bivariate problems by graphical method. Solving linear inequality systems by Fourier-Motzkin elimination. Necessary and sufficient conditions for solving systems of linear equations with non-negative variables and systems of linear inequalities: Farkas' lemma.
The basic problem of linear programming in matrix form. Necessary and sufficient conditions for the boundedness of the objective function of a linear program. Concept of duality of a linear program, dualities of linear programs written in different forms.
Duality theorem of linear programming. Algorithmic complexity of the linear programming problem. The basic task of integer programming, its complexity. Formalization of optimization problems as integer programming problems.
Integer programming with a totally
unimodular coefficient matrix. Applications in the area of bipartite
matchings and network flow problems: maximum flow, minimum cost flow,
and multicommodity flow problems.
The notions of local edge and vertex
connectivity and global edge and vertex connectivity, the corresponding
Menger theorems (iteration). Max-return order, Nagamochi-Ibaraki's
algorithm for determining edge connectivity.
Algorithm for increasing graphs to be 2-edge-connected, lower bound on the number of edges required. Algorithm for finding minimum cost spanning tree. Ear resolution, directing graphs to ensure strong connectivity.
Approximation algorithms. Edge chromatic number, approximation of planar graph chromatic number with additive error, approximation of longest cycle with additive error. 2-approximation for the size of covering vertex set, logarithmic approximation for set covering problem.
Scheduling problems. Basic concepts, notation, useful methods: SPT ordering and list scheduling. FD and FFD heuristics for the crate packing problem.
Recap, summary, systematic review of the material studied. Description of the current test items for the oral examination and detailed expectations for each item.
The course provides an introduction to some areas of operations research and combinatorial optimization. Besides describing the main algorithms, methods and their limitations, it aims to provide insights into their technical applications. Thus, it covers areas offering comprehensive algorithmic approaches such as network flow theory and linear and integer programming, but also provides insights into the world of approximation algorithms and scheduling theory, in addition to the higher-order problems that arise in the design of reliable networks. The course also aims to apply and deepen the knowledge previously acquired in the BSc Electrical Engineering course Fundamentals of Computer Science, and to provide a better theoretical background.
Learning outcomes
Ez a tantárgy a KKK rendeletben meghatározott, következő kompetenciák fejlesztését szolgálja:
Knowledge
No learning outcomes recorded.
Skills
No learning outcomes recorded.
Attitudes
No learning outcomes recorded.
Autonomy and responsibility
No learning outcomes recorded.
Oktatási módszertan
Lectures and prolem solving.
Tanulástámogató anyagok
Not provided.
Recommended preliminary knowledge for completing the subject
Knowledge type competencies
(azon előzetes ismeretek összessége, amelyek megléte nem kötelező, de a tantárgy eredményes teljesítését nagyban elősegíti)
basics of linear algebra, graph theory and theory of algorithms
Skill type competencies
(azon előzetes képességek és készségek összessége, amelyek megléte nem kötelező, de a tantárgy eredményes teljesítését nagyban elősegíti)
nincs
Recommended (non-compulsory) preliminary competencies
(azon ajánlott (nem kötelező) előzetesen megszerzendő kompetenciák összessége, amelyek jelentősen hozzájárulnak a tantárgy eredményes teljesítéséhez)
basics of linear algebra, graph theory and theory of algorithms
General rules
Requirements:
During the semester:
There will be two midterms. Both will consist of 4-4 exercises, with a total score of 50 points per test. Both must be at least 20 points to obtain a signature.
Exam period:
You can apply for the exam if you have a valid signature. If a signature is obtained, the student is offered a mark based on the total number of marks obtained in the final examination, as follows: from 40 points satisfactory, from 55 to medium, from 70 to good and from 85 to excellent. The lecturer must be informed of the acceptance of the grade offered during the make-up week. Those who accept the grade offered will not be allowed to sit the oral examination. Anyone who does not notify the lecturer of the acceptance of the mark may obtain the mark in the oral examination. In the oral examination, you may improve the grade offered by up to one mark, and you may lower it without limit.
Additional possibilities:
There will be a retake for both midterms.
Assessment methods
In-term assessments
No detailed assessments provided.
Weight of in-term assessments
No weights provided.
Exam-period assessments
No detailed assessments provided.
Weight of exam elements
No weights provided.
Grade calculation
No grade thresholds provided.
Attendance requirements
No attendance requirements provided.
Rules for retake and resubmission
Not provided.
Short description
Not provided.
Detailed description
Not provided.
Recommended courses
Not provided.
Workload to complete the subject
No workload breakdown provided.
Validity of subject requirements
Requirements valid from:
—
Requirements valid until:
—
Curriculum placement
No curriculum placements recorded for this subject version.