Theory of linear programming; convexity; simplex and algorithmic aspects; duality and sensitivity; computational issues; decomposition and column generation; introduction to integer and nonlinear programming.
Linear Programming and Extensions (IE 501)
2022 Fall
Faculty of Engineering and Natural Sciences
Industrial Engineering(IE)
3
10.00
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 |
| MA-European Studies | |||
| MA-European Studies-Non Thesis | |||
| MA-Political Science | |||
| MA-Political Science-Non Thes | |||
| MA-Visual Arts&Vis. Com Des-NT | |||
| MA-Visual Arts&Visual Com Des | |||
| MS-Bio. Sci. & Bioeng. LFI | |||
| MS-Bio. Sci. & Bioeng. LFI-ENG | |||
| MS-Biological Sci&Bioeng. | * | ||
| MS-Business Analytics | |||
| MS-Computer Sci.&Eng. LFI | |||
| MS-Computer Sci.&Eng. LFI-ENG | |||
| MS-Computer Science and Eng. | * | ||
| MS-Cyber Security(with thesis) | * | ||
| MS-Data Science | * | ||
| MS-Elec. Eng&Comp Sc.LFI-ENG | |||
| MS-Electronics Eng&Comp Sc.LFI | |||
| MS-Electronics Eng&Computer Sc | * | ||
| MS-Electronics Eng. | * | ||
| MS-Electronics Eng. LFI | |||
| MS-Electronics Eng. LFI-ENG | |||
| MS-Energy Techno.&Man. | * | ||
| MS-Industrial Eng. LFI-ENG | |||
| MS-Industrial Engineering | * | ||
| MS-Industrial Engineering LFI | |||
| MS-Manufacturing Eng-Non Thes | * | ||
| MS-Manufacturing Engineering | * | ||
| MS-Materials Sci & Engineering | * | ||
| MS-Materials Sci. & Eng. LFI | |||
| MS-Materials Sci.&Eng. LFI-ENG | |||
| MS-Mathematics | |||
| MS-Mechatronics | * | ||
| MS-Mechatronics LFI | |||
| MS-Mechatronics LFI-ENG | |||
| MS-Physics | |||
| MS-Physics-Non Thesis | * | ||
| MS-Psychology | |||
| MS-Psychology-Non Thesis | |||
| PHD-Biological Sci&Bioeng. | * | ||
| PHD-Comp. Sci and Eng.after UG | * | ||
| PHD-Computer Science and Eng. | * | ||
| PHD-Cyber Security | * | ||
| PHD-Electronics Eng&ComputerSc | * | ||
| PHD-Electronics Eng. | * | ||
| PHD-Electronics Eng. after UG | * | ||
| PHD-Experimental Psychology | |||
| PHD-Industrial Engineering | * | ||
| PHD-Management | |||
| PHD-Manufacturing Eng after UG | * | ||
| PHD-Manufacturing Engineering | * | ||
| PHD-Materials Sci.&Engineering | * | ||
| PHD-Mathematics | |||
| PHD-Mechatronics | * | ||
| PHD-Mechatronics after UG | * | ||
| PHD-Physics | |||
| PHD-Physics after UG | |||
| PHD-Social Psychology | |||
| PHDBIO after UG | * | ||
| PHDCYSEC after UG | * | ||
| PHDEECS after UG | * | ||
| PHDEPSY after UG | |||
| PHDIE after UG | * | ||
| PHDMAN after UG | |||
| PHDMAN after UG-Finance | |||
| PHDMAN after UG-Man. and Org. | |||
| PHDMAN after UG-Op.&Sup. Cha. | |||
| PHDMAN-Finance Area | |||
| PHDMAN-Man. and Org. Area | |||
| PHDMAN-Op. & Supp. Chain Area | |||
| PHDMAT after UG | * | ||
| PHDMATH after UG | |||
| PHDSPSY after UG |
CONTENT
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 OUTCOME
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
Update Date:
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. |