INDR 262 Introduction to Optimization Methods

 > INDR 262 Introduction to Optimization Methods

Instructor:      Metin Türkay

Office:            ENG-205, x1586

E-Mail:           mturkay@ku.edu.tr e-mail for the course: indr262faq@ku.edu.tr

 

Lectures:   

Section 01: Mn&We 14:30-15:45 ENG-Z50

Section 02: Mn&We 16:00-17:15 ENG-Z50

   

PS:

A: Fr 16:00-17:15 ENG-120

B: Th 17:30-18:45 SNA-B152

C: We 17:30-18:45 CASE-B24

 

Lab:

A: Tu 17:30-18:45 SNA-B152

B: Mo 17:30-18:45 SNA-B152

C: Fr 08:30-09:45 SNA-B152

 

Office Hours: Mn&We 13:00-14:30, Tu 10:00-11:30

 

TAs:

Esma Bozgeyik (EB), ENG-212, indr262faq@ku.edu.tr

Soheil Derakhshan Nejad (SDN), ENG-212, indr262faq@ku.edu.tr

Sadra Shoarinejad (SS), ENG-212, indr262faq@ku.edu.tr

Emre Kaan Yılmaz (EKY), ENG-212, indr262faq@ku.edu.tr

Tugce Uzer (TU), ENG-212, indr262faq@ku.edu.tr

 

Hümeyra Akyüz (HA), ENG-212

Ezgi Kalemoglu (EK), ENG-212

Perinaz Alp (PA), ENG-212

Abdullah Izgi (AI), ENG-212

 

TA Office Hours:

EB: We 11:00-12:00

SDN: Th 14:00-15:00

SS: Th 16:00-17:00

EKY:

TU: We 08:30-10:00

HA: Fr 14:30-15:45

EK: Mo 16:30-17:30

PA: 

AI: Tu 16:00-17:30

 

KOLT Tutor:

Humeyra Akyuz: Mo 10:00-11:15, We: 11:30-12:45, Fr: 10:00-11:15

Brief Description

This course is designed to expose students to the concepts of modeling and optimization. The course emphasizes setting up optimization models from problem description and solving linear programming problems using the simplex method. The role of duality and sensitivity analysis for linear programming problems are examined. The range of problems that can be modeled and solved as linear programming problems are illustrated in engineering and management with computer implementations.

 

Course Goals

The students are expected to acquire the following skills in this course:

–  Develop a fundamental understanding of linear programming models,

–  Able to develop a linear programming model from problem description,

–  Apply the simplex method for solving linear programming problems,

–  Apply the revised simplex method to solve linear programming problems,

–  Express the dual of a linear programming problem and solve the resulting dual problem using the dual simplex method, interpret the results and obtain solution to the primal problem from the solution of the dual problem,

–  Conduct sensitivity analysis for linear programming problems and interpret the results,

–  Apply the Hungarian method for solving assignment problems,

–  Apply the transportation simplex method to solve transportation problems,

–  Demonstrate hands-on problem solving skills for linear programming problems using a Python and a variety of solvers.

 

Textbook

Hillier, F.S. and G.J. Lieberman, ‘Introduction to Operations Research’, 10th Ed., 2015, McGraw Hill, New York.

 

Computer Laboratory and Problem Sessions

This course has 4 credits and involves problems sessions and computer laboratory. The problem sessions cover basic problem solving skills and reinforce the material covered in the lectures. There may be quizzes related to homework questions during the problem sessions. The computer laboratory sessions cover basic skills in developing models and using solvers by using Python. You will apply these skills in the homework assignments.

Note: Failure to attend the PS and Computer Labs will result in an automatic F in the course. Students can miss at most 1 PS or Computer Labs in the semester with approved excuse.

 

Homework and Computer Exercises

Homework is assigned to expose students to exercise problems and understanding of the theory, and to evaluate their abilities and knowledge. Students should be prepared to spend considerable time for preparing homework. Students are expected to submit their homework before the due date and time. In addition, there are computer exercises for modeling and solution of mathematical programming problems. The aim of the computer exercises is to help students gain hands-on experience with state-of-the-art programming software, Python. The computer exercises must be submitted by the announced deadline. Each student is required to complete the computer exercises alone from start to end. Failing to submit homework and computer exercises on time will result in 25% grade reduction for each late day.

 

Exams

There are two midterm exams during the semester and a final exam at the end of the semester. Exams will be closed book and notes. No make-up exams will be given unless required by Koç University policies. Students who are eligible for a make-up exam due to official reasons must contact the instructor at least one week prior to the exam date. If you miss an exam due to unforeseen circumstances such as severe illness, death in the family, etc., you must submit a written and signed statement as soon as possible, stating why you were unable to take the exam, together with any supporting documentation such as a doctor’s medical report. Failure to comply with these instructions unconditionally leads to zero being awarded for the exam grade.

 

Course grade will be determined as follows:

Midterm I  (March 7, 2020, 13:15-16:15, SNA-A52& SNA-B172, SNA-B173) (Sample Exams: 2004, 2012)25%
Midterm II (April 16, 2020, 19:0-22:00, SNA-A21& SNA-A22) (Sample Exams: 2004, 2012)25%
Homework, Computer Exercises and Quizzes10%
Term Project5%
Participation (3% for classes, 2% for PS&Lab)5%
Final Exam (TBA) (Sample Exams: 2004, 2012)30%

Course Outline

DateSubjectMaterial
Week 1

Review of Basic Linear Algebra

Matrices and Vectors

Systems of Linear Equations

Notes

PPT

Notes

Week 1PS: Linear Algebra 
Week 2

Modeling Optimization Problems

Defining the Problem

Formulating a Mathematical Model

Chapter 1, 2

Notes

PPT

Week 2PS: Modeling Optimization Problems 
Week 3

Formulation of Linear Programming Problems

Standard Form of Linear Programming Models

Assumptions in Linear Programming

Examples of Linear Programming Models

Chapter 3

Notes

PPT

Week 3Lab: Introduction to Python 
Weeks 4+5

Solving Linear Programming Problems: The Simplex Method

Setting up the Simplex Method

The Algebra of the Simplex Method

The Simplex Method in Tabular Form

Chapter 4

Notes

PPT

Simplex Tableau

Week 4PS: Simplex Method 
Week 5Lab: Modeling LP problems in Python 
Week 6

Starting Solution and Convergence

The Two-Phase Method

The Big-M Method

Notes

PPT

Week 6PS: Starting Solutions 
Week 7

Mid-Term I (March 7, 2020, 13:15-16:15, SNA-A52& SNA-B172, SNA-B173)

Mid Term I Exercise Set, Solutions

Sample Exams:

2004, 2012

Weeks 7+8

The Theory of the Simplex Method

Extreme Points

Basic Feasible Solutions

The Revised Simplex Method

Chapter 5

Notes

PPT

Week 7PS: The Theory of the Simplex 
Week 8Lab: Solving LPs in Python 
Week 9

Duality Theory

The Essence of Duality Theory and Primal-Dual Relationships

Economic Interpretation of Duality

Chapter 6 (sections 6.1 through 6.4)

Notes

Week 9PS: Duality 
Week 9Mid-Term II (April 16, 2020, 19:0-22:00, SNA-A21& SNA-A22)

Sample Exams:

2004, 2012

Weeks 10+11

Sensitivity Analysis

The Essence of Sensitivity Analysis

Applying Sensitivity Analysis

Chapter 6 (sections 6.5 through 6.7)

Notes

Week 10Lab: Solving LPs in Python 
Week 11PS: Dual Simplex 
Week 12+13

The Dual Simplex Method

Parametric Linear Programming

The Upper Bound Technique

Chapter 7

Notes

Week 12Lab: Managing optimization projects in Python 
Week 13PS: Sensitivity Analysis 
Week 14

Special Cases of Linear Programming Problems

The Transportation Problem

The Assignment Problem

Chapter 8

Notes

Week 14PS: Review 
Final ExamsFinal Exam (TBA)

Sample Exams:

2004, 2012

Note: Topics to be covered and grade percentages may be modified by the course instructor.

 

Koç University Official Statement on Academic Honesty

 

 

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.

March 7, 2020 13:15
SNA-A52& SNA-B172, SNA-B173Mid Term I (Sample Exams: 2004, 2012)April 16, 2020SNA-A21& SNA-A22

 

Mid Term II (Sample Exams: 2004, 2012)

WeekDateTime & RoomSubject
1January 27-31, 2020

A: Fr 16:00-17:15 ENG-120

B: Th 17:30-18:45 SNA-B152

C: We 17:30-18:45 CASE-B24

PS: Linear Algebra
2February 3-7, 2020

A: Fr 16:00-17:15 ENG-120

B: Th 17:30-18:45 SNA-B152

C: We 17:30-18:45 CASE-B24

PS: Modeling Optimization Problems
3February 10-14, 2020

A: Tu 17:30-18:45 SNA-B152

B: Mo 17:30-18:45 SNA-B152

C: Fr 08:30-09:45 SNA-B152

Lab: Introduction to Python
4February 17-21, 2020

A: Fr 16:00-17:15 ENG-120

B: Th 17:30-18:45 SNA-B152

C: We 17:30-18:45 CASE-B24

PS: Simplex Method
5February 24-28, 2020

A: Tu 17:30-18:45 SNA-B152

B: Mo 17:30-18:45 SNA-B152

C: Fr 08:30-09:45 SNA-B152

Lab: Modeling LP problems in Python
6March 2-6, 2020

A: Fr 16:00-17:15 ENG-120

B: Th 17:30-18:45 SNA-B152

C: We 17:30-18:45 CASE-B24

PS: Starting Solutions, big-M, 2-Phase
7March 9-13, 2020

A: Fr 16:00-15:15 ENG-120

B: Th 17:30-18:45 SNA-B152

C: We 17:30-18:45 CASE-B24

PS: The Theory of the Simplex
8March 16-20, 2020

A: Tu 17:30-18:45 SNA-B152

B: Mo 17:30-18:45 SNA-B152

C: Fr 08:30-09:45 SNA-B152

Lab: Solving LPs in Python
9March 23-27, 2020

A: Fr 16:00-17:15 ENG-120

B: Th 17:30-18:45 SNA-B152

C: We 17:30-18:45 CASE-B24

PS: Duality
10March 30-April 3, 2020

A: Tu 17:30-18:45 SNA-B152

B: Mo 17:30-18:45 SNA-B152

C: Fr 08:30-09:45 SNA-B152

Lab: Solving LPs in Python
 April 6-10, 2020SPRING BREAKSPRING BREAK
11April 13-17, 2020

A: Fr 16:00-17:15 ENG-120

B: Th 17:30-18:45 SNA-B152

C: We 17:30-18:45 CASE-B24

PS: Dual Simplex
 
12April 20-24, 2020

A: Tu 17:30-18:45 SNA-B152

B: Mo 17:30-18:45 SNA-B152

C: Fr 08:30-09:45 SNA-B152

Lab: Managing optimization projects in Python
13April 27-May 1, 2020

A: Fr 16:00-17:15 ENG-120

B: Th 17:30-18:45 SNA-B152

C: We 17:30-18:45 CASE-B24

PS: Sensitivity Analysis
14May 4-8, 2019

A: Fr 16:00-17:15 ENG-120

B: Th 17:30-18:45 SNA-B152

C: We 17:30-18:45 CASE-B24

PS: Review

Failure to attend the PS and Computer Labs will result in an automatic F in the course. Students can miss at most 1 PS or Computer Lab in the semester with approved excuse.

Date Due Assignment Solutions PS/Lab Quiz
January 31, 2020 HW#1 PS
February 7, 2020 HW#2 PS
February 17, 2020 Problems 3.1-7, 3.1-9, 3.1-14 Lab
February 21, 2020   Problems 3.2-4, 3.2-5, 3.3-2, 3.4-4, 3.4-5 PS
February 28, 2020 Solve Problems 4.1-2, 4.1-6, 4.3-5, 4.4-3 Lab
March 6, 2020   Solve Problems 4.4-5, 4.4-7, 4.4-8, 4.5-2 PS
March 7, 2020 Mid Term I 13:15-16:15, SNA-A52& SNA-B172, SNA-B173 Sample Exams: 20042012
March 16, 2020 Problems 4.6-2 (excluding part h), 4.6-5 (parts a and c only), 4.6-7 (excluding part h) PS
March 20, 2020 Lab
March 27, 2020 PS
April 3, 2020 Lab
April 17, 2020 PS
April 16, 2020 Mid Term II 19:00-22:00, SNA-A21&SNA-A22 Sample Exams: 20042012
April 24, 2020 Lab
May 1, 2020 PS
May 8, 2019 PS
May 15, 2020 Bonus Project: coding Revised Simplex including 2-phase method and graphical user interface for solving LP problems. You can code in Python, Java, C++, or C#
May 20, 2020 Term Project: form your project groups- max 3 students per group [Project1][Project2] You must login to your Novell account before downloading the solutions. You must login to your Novell account before downloading the solutions.

Reading 1: Optimizasyon, Metin Türkay

 

Reading 2: George B. Dantzig: Operations research Icon, 2005, Operations research, vol. 53, 892-898

 

GAMS download link

Midterm I  (TBA) (Sample Exams: 20042012)

Midterm II (TBA) (Sample Exams: 20042012)

Final (TBA) (Sample Exams: 20042012)