Linear Programming and Extensions (IE 501)

2022 Fall
Faculty of Engineering and Natural Sciences
Industrial Engineering(IE)
3
10
Ezgi Karabulut Türkseven ezgi.turkseven@sabanciuniv.edu,
Click here to view.
English
Doctoral, Master
--
Formal lecture,Interactive lecture
Interactive,Discussion based learning,Project based learning
Click here to view.
Programs\Type Required Core Elective Area Elective
Business Analytics - With Thesis *
Computer Science and Engineering - With Bachelor's Degree *
Computer Science and Engineering - With Master's Degree *
Computer Science and Engineering - With Thesis *
Cyber Security - With Bachelor's Degree *
Cyber Security - With Master's Degree *
Cyber Security - With Thesis *
Data Science - With Thesis *
Electronics Engineering and Computer Science - With Bachelor's Degree *
Electronics Engineering and Computer Science - With Master's Degree *
Electronics Engineering and Computer Science - With Thesis *
Electronics Engineering - With Bachelor's Degree *
Electronics Engineering - With Master's Degree *
Electronics Engineering - With Thesis *
Energy Technologies and Management-With Thesis *
Industrial Engineering - With Bachelor's Degree *
Industrial Engineering - With Master's Degree *
Industrial Engineering - With Thesis *
Leaders for Industry Biological Sciences and Bioengineering - Non Thesis *
Leaders for Industry Computer Science and Engineering - Non Thesis *
Leaders for Industry Electronics Engineering and Computer Science - Non Thesis *
Leaders for Industry Electronics Engineering - Non Thesis *
Leaders for Industry Industrial Engineering - Non Thesis *
Leaders for Industry Materials Science and Engineering - Non Thesis *
Leaders for Industry Mechatronics Engineering - Non Thesis *
Management Ph.D. - Finance Area - With Bachelor's Degree *
Management Ph.D. - Finance Area - With Master's Degree *
Management Ph.D. - Management and Organization Area - With Bachelor's Degree *
Management Ph.D. - Management and Organization Area - With Master's Degree *
Management Ph.D. - Operations and Supply Chain Management Area - With Bachelor's Degree *
Management Ph.D. - Operations and Supply Chain Management Area - With Master's Degree *
Management Ph.D. - With Bachelor's Degree *
Management Ph.D. - With Master's Degree *
Manufacturing Engineering - Non Thesis *
Manufacturing Engineering - With Bachelor's Degree *
Manufacturing Engineering - With Master's Degree *
Manufacturing Engineering - With Thesis *
Materials Science and Nano Engineering-(Pre:Materials Science and Engineering) *
Materials Science and Nano Engineering-(Pre:Materials Science and Engineering) *
Materials Science and Nano Engineering - With Thesis (Pre.Name: Materials Science and Engineering) *
Mathematics - With Bachelor's Degree *
Mathematics - With Master's Degree *
Mathematics - With Thesis *
Mechatronics Engineering - With Bachelor's Degree *
Mechatronics Engineering - With Master's Degree *
Mechatronics Engineering - With Thesis *
Molecular Biology, Genetics and Bioengineering (Prev. Name: Biological Sciences and Bioengineering) *
Molecular Biology, Genetics and Bioengineering-(Prev. Name: Biological Sciences and Bioengineering) *
Molecular Biology,Genetics and Bioengineering-With Thesis (Pre.Name:Biological Sciences and Bioeng.) *
Physics - Non Thesis *
Physics - With Bachelor's Degree *
Physics - With Master's Degree *
Physics - With Thesis *

CONTENT

Theory of linear programming; convexity; simplex and algorithmic aspects; duality and sensitivity; computational issues; decomposition and column generation; introduction to integer and nonlinear programming.

OBJECTIVE

This course focuses on the theory of linear programming (LP) although we will discuss some practical implementation issues as well. In the first part of the course, we will review LP modeling, convexity, some essential linear algebra, certain aspects of polyhedral theory, and then present the foundations of linear programming. In the second part of the course, we will discuss the simplex method for solving linear programs and its algorithmic aspects, some related computational issues, duality and sensitivity. Finally, we will cover Dantzig-Wolfe decomposition and column generation for solving large-scale linear programs. If time permits at the end of the semester, we will briefly introduce further decomposition methods that rely on linear programming and interior point algorithms for solving linear programs. Issues related to computer implementations of linear programming algorithms will generally not be discussed in class, but you will be exposed to the computational aspects of linear programming during assignments.

LEARNING OUTCOMES

  • to identify, model, and solve linear programming problems
  • to describe the connection of the structure of linear programming problems to linear algebra and polyhedral theory
  • to leverage on LO-2 in order to design and implement an efficient solution method for linear programming
  • to describe the relationship between primal and dual linear programming problems and exploit it in sensitivity analysis
  • to describe the main difficulties associated with solving large-scale linear programming problems and overcome them by employing decomposition methods

ASSESSMENT METHODS and CRITERIA

  Percentage (%)
Final 25
Midterm 25
Participation 5
Homework 45

RECOMENDED or REQUIRED READINGS

Textbook

Linear Programming and Network Flows, Mokhtar S. Bazaraa, John J. Jarvis, Hanif D. Sherali. John Wiley, 2010. Fourth edition.
Readings

Linear programming and network flows. Mokhtar S. Bazaraa, John J. Jarvis, Hanif D. Sherali. John Wiley, 2009. 4th ed.

Introduction to Linear Optimization. Dimitris Bertsimas, John N. Tsitsiklis. Athena Scientific, 1997.

Linear programming : foundations and extensions. Robert J. Vanderbei. Kluwer Academic Publishers, 1997.

Linear algebra and its applications. Gilbert Strang. Harcourt, Brace, Jovanovich, Publishers, 1988.