Transcript Linear Programming (Optimization)

IE 531 Linear Programming
Spring 2012
Sungsoo Park
1
 Instructor
Sungsoo Park (room 4112, [email protected], tel:3121)
Office hour: Tu., Thr. 14:30 – 17:00 or by appointment
 Classroom: E2 room 1120
 Class hour: Tu., Thr. 13:00 – 14:30
 Homepage: http://solab.kaist.ac.kr
 TA:
Kyoungmi Hwang (room 4113, [email protected], tel:3161)
Office hour: Mon., Wed. 13:00 – 15:00
 Grading: Midterm 30-40%, Final 40-60%, HW 10-20% (including Software
CPLEX/Xpress-MP)
Linear Programming 2012
2
 Text: "Introduction to Linear Optimization" by D. Bertsimas and J. Tsitsiklis,
1997, Athena Scientific (not in bookstore, reserved in library)
and class Handouts
 Prerequisite: basic linear algebra/calculus,
earlier exposure to LP/OR helpful,
mathematical maturity (reading proofs, logical thinking)
 Be steady in studying.
Linear Programming 2012
3
Course Objectives
 Why need to study LP?
Important tool by itself
Theoretical basis for later developments (IP, Network, Graph, Nonlinear,
scheduling, Sets, Coding, Game, … )
Formulation + package is not enough for advanced applications and interpretation
of results
 Objectives of the class:
Understand the theory of linear optimization
Preparation for more in-depth optimization theory
Modeling capabilities
Introduction to use of software (Xpress-MP and/or CPLEX)
Linear Programming 2012
4
 Topics
Introduction and modeling
System of linear inequalities, polyhedral theory
Simplex method, implementation
Duality theory
Sensitivity analysis
Delayed column generation, Dantzig-Wolfe decomposition
Core concepts of interior point methods
Linear Programming 2012
5
Brief History of LP (or Optimization)
 Gauss: Gaussian elimination to solve systems of equations
Fourier(early 19C) and Motzkin(20C) : solving systems of linear inequalities
Farkas, Minkowski, Weyl, Caratheodory, … (19-20C):
Mathematical structures related to LP (polyhedron, systems of alternatives,
polarity)
Kantorovich (1930s) : efficient allocation of resources
(Nobel prize in 1975 with Koopmans)
Dantzig (1947) : Simplex method
1950s : emergence of Network theory, Integer and combinatorial
optimization, development of computer
1960s : more developments
1970s : disappointment, NP-completeness, more realistic expectations
Khachian (1979) : ellipsoid method for LP
Linear Programming 2012
6
1980s : personal computer, easy access to data, willingness to use models
Karmarkar (1984) : Interior point method
1990s : improved theory and software, powerful computers
software add-ins to spreadsheets, modeling languages,
large scale optimization, more intermixing of O.R. and A.I.
Markowitz (1990) : Nobel prize for portfolio selection (quadratic programming)
Nash (1994) : Nobel prize for game theory
21C (?) : Lots of opportunities
more accurate and timely data available
more theoretical developments
better software and computer
need for more automated decision making for complex systems
need for coordination for efficient use of resources (e.g. supply chain
management, APS, traditional engineering problems, bio, finance, ...)
Linear Programming 2012
7
Application Areas of Optimization
 Operations Managements
Production Planning
Scheduling (production, personnel, ..)
Transportation Planning, Logistics
Energy
Military
Finance
Marketing
E-business
Telecommunications
Games
Engineering Optimization (mechanical, electrical, bioinformatics, ... )
System Design
…
Linear Programming 2012
8
Resources
 Societies:
INFORMS (the Institute for Operations Research and Management Sciences) :
http://www.informs.org
MPS (The Mathematical Programming Society) : http://www.mathprog.org
Korean Institute of Industrial Engineers : http://kiie.org
Korean Operations Research Society : http://www.korms.or.kr
 Journals:
Operations Research, Management Science, Mathematical Programming,
Networks, European Journal of Operational Research, Naval Research
Logistics, Journal of the Operational Research Society, Interfaces, …
Linear Programming 2012
9