COURSE UNIT TITLE

: ADVANCED COMBINATORIAL OPTIMIZATION : PROBLEMS AND METHODS

Description of Individual Course Units

Course Unit Code Course Unit Title Type Of Course D U L ECTS
CSC 5048 ADVANCED COMBINATORIAL OPTIMIZATION : PROBLEMS AND METHODS ELECTIVE 3 0 0 8

Offered By

Graduate School of Natural and Applied Sciences

Level of Course Unit

Second Cycle Programmes (Master's Degree)

Course Coordinator

ASSOCIATE PROFESSOR FIDAN NURIYEVA

Offered to

Ph.D. in Computer Science (English)
Computer Science

Course Objective

The aim of the course is to give an advanced mathematical methodology of the modern heuristics for important combinatorial optimization problems together with the computational complexity considerations.

Learning Outcomes of the Course Unit

1   1. To have knowledge about the basic concepts of combinatorial optimization.
2   2. Modeling of combinatorial optimization problems
3   3. To be able to solve combinatorial optimization problems.
4   4. To be able to design effective algorithms with combinatorial optimization concepts.
5   5. To be able to solve problems in different disciplines with combinatorial optimization concepts.

Mode of Delivery

Face -to- Face

Prerequisites and Co-requisites

None

Recomended Optional Programme Components

None

Course Contents

Week Subject Description
1 1. Optimization Problems
2 2. Complexity of Algorithms
3 3. Integer programming
4 4. Models for Combinatorial Optimization problems - 1
5 5. Models for Combinatorial Optimization problems - 2
6 6. Models for Combinatorial Optimization problems - 3
7 7. NP completeness problems
8 8. Recap
9 9. Solving methods of combinatorial optimization problems
10 10. Branch and Bound strategies
11 11. Dynamic Programming
12 12. Local Search Algorithms
13 13. Heuristic algorithms
14 14. Metaheuristic algorithms

Recomended or Required Reading

Textbook(s):
1. Papadimitriou C.H., Steiglitz K., Combinatorial Optimization: Algorithms and Complexity, Prentice Hall, 1998.

Supplementary Book(s):
2. Kellerer, H., Pferschy U., Pisinger D., Knapsack Problems, Springer, 2004.
3. Korte, B., Vygen, J., Combinatorial Optimization: Theory and Algorithms, 4th Edition (Algorithms and Combinatorics), Springer, 2008.
4. Martello, S., Toth, P., Knapsack Problems: Algorithms and Computer Implementations,John Wiley &Sons, 1990.
5. Edited by Ding-Zhu Du, Panos M. Pardolos, Handbook of Combinatorial Optimization (Volume A), Kluwer, 1999.
6. Edited by Ding-Zhu Du, Panos M. Pardolos, Handbook of Combinatorial Optimization (Volume B), Kluwer, 1999.
7. Lawler Eugene, Combinatorial Optimization Network and Matroids, 2001.
8. Nemhauser G. L., Wolsey L. A., Integer and Combinatorial Optimization, John Wiley&Sons, 1988.

Planned Learning Activities and Teaching Methods

The course is taught in a lecture, class presentation and discussion format. In some weeks of the course, results of the homework given previously are discussed.

Assessment Methods

SORTING NUMBER SHORT CODE LONG CODE FORMULA
1 MTE MIDTERM EXAM
2 FIN FINAL EXAM
3 FCG FINAL COURSE GRADE MTE * 0.40 + FIN * 0.60
4 RST RESIT
5 FCGR FINAL COURSE GRADE (RESIT) MTE * 0.40 + RST * 0.60


Further Notes About Assessment Methods

None

Assessment Criteria

To be announced.

Language of Instruction

English

Course Policies and Rules

To be announced.

Contact Details for the Lecturer(s)

fidan.nuriyeva@deu.edu.tr

Office Hours

To be announced.

Work Placement(s)

None

Workload Calculation

Activities Number Time (hours) Total Work Load (hours)
Lectures 14 3 42
Preparations before/after weekly lectures 13 4 52
Preparation for midterm exam 1 50 50
Preparation for final exam 1 60 60
Midterm 1 2 2
Final 1 2 2
TOTAL WORKLOAD (hours) 208

Contribution of Learning Outcomes to Programme Outcomes

PO/LOPO.1PO.2PO.3PO.4PO.5PO.6PO.7PO.8PO.9PO.10
LO.1534
LO.2555555
LO.35554
LO.443545
LO.545