Instructor: Metin Türkay
Office: ENG-205, Ext:1586
E-Mail: mturkay@ku.edu.tr
Class Hours: MnB3-WedB3 (12:30-13:45) ENG-B21
Office Hours: Mn&We B2+B3, Fri B2
TA: Gokhan Kirlik, ENG-210, Ext:2648, gkirlik[@]ku.edu.tr
Office Hours: Tu&ThB1
Brief Description
This course covers the models and theory of integer and combinatorial optimization problems. The theory and properties of solution spaces for integer and combinatorial optimization problems will be covered.
Textbook
H.P. Williams, “Logic and Integer Programming”, Springer, New York, 2009. (HPW)
L.A. Wolsey, “Integer Programming”, Wiley, New Jersey, 1998. (LAW)
Supplementary Text
Lecture notes for some subjects will be distributed.
Homework
Homework assignmnts are given to expose students to more complex problems and understanding of the theory, and to evaluate their abilities and knowledge. Students should be prepared to spend considerable time for preparing these homework.
Students are expected to submit their homework assignments before the due date and time. Failing to do so will result in 25% grade reduction for each late day. All students are also required to prepare term projects on integer and combinatorial optimization.
Exams
Exams for this course are similar to any other: They are entirely targeted at evaluating the performance of students. So no form of information exchange will be permitted. There will always be a reasonable time limit at the exams. There is a Midterm exam in the middle of the semester and a Final exam at the end of the semester.
Final grades will be determined as follows:
Mid Term Exam Sample Exam | 40% |
Homework | 20% |
Final Exam Sample Exam | 40% |
Course Outline
Subject | Material |
Formulation of integer and combinatorial optimization problems | Chapter 1-LAW |
Introduction to Logic | Chapter 1-HPW |
Integer Programming Models | Chapter 2-HPW |
Modeling in Logic for Integer Programming | Chapter 3-HPW |
Optimality, Relaxation, and Bounds | Chapter 2-LAW |
Mid Term | |
Integer and Combinatorial Optimization Algorithms | Chapters 3, 4, 5-LAW |
Computational Complexity | Chapter 6-LAW |
Branch and Bound | Chapter 7-LAW |
Cutting Plane Algorithms | Chapter 8-LAW |
Valid Inequalities | Chapter 9-LAW |
Duality | Chapter 10-LAW |
Column Generation Algorithms | Chapter 11-LAW |
Note: Topics to be covered and grade percentages may be modified by the course instructor.
PDF copy of the Syllabus
Academic Honesty
Honesty and trust are important to all of us as individuals. Students and faculty adhere to the following principles of academic honesty at Koç University:
Individual accountability for all individual work, written or oral: Copying from others or providing answers or information, written or oral, to others is cheating.
Providing proper acknowledgment of original author: Copying from another student’s paper or from another text without written acknowledgment is plagiarism.
Study or project group activity is effective and authorized teamwork: Unauthorized help from another person or having someone else write one’s paper or assignment is collusion.
Cheating, plagiarism, and collusion are serious offenses resulting in an F grade and disciplinary action.
Attendance Policy
All students are required to attend classes and discussion sessions such as tutorials, labs and problem sessions. The course instructor will take attendance. The students who fail to attend 1/3 of classes and discussion sessions may get an automatic F.
Date | Date Due | Assignment | Solutions |
March 7, 2011 | March 14, 2011 | Homework 1 | Homework 1 |
March 16, 2011 | March 23, 2011 | Homework 2 | Homework 2 |
March 31, 2011 | April 13, 2011 | Homework 3 | |
Reading Assignment (Computational Complexity) |