John W. Chinneck

Systems and Computer Engineering

Carleton University

Ottawa, Ontario K1S 5B6

Canada

http://www.sce.carleton.ca/faculty/chinneck/po.html

The chapters appearing below are draft chapters of an introductory textbook on optimization. The ultimate objective is the creation of a complete, yet compact, introductory survey text on the major topics in optimization. The material is derived from the lecture notes used by the author in engineering courses at Carleton University, and reflects the design considerations for those courses:

- Students need to have a solid
*intuitive*understanding of how and why optimization methods work. This enables them to recognize when things have gone wrong, and to diagnose the source of the difficulty and take appropriate action. It also permits students to see how methods can be combined or modified to solve non-standard problems. - Explanation and diagrams are more effective in transmitting a real understanding than a total reliance on mathematics.
- There should be some exposure to how things are done in practice, which can be significantly different than how they are usually done in textbooks.
- The goal is for students to be able to recognize when problems that they encounter in their jobs or in thesis work can be successfully tackled by optimization methods. Students should be able to abstract a useful formulation of a problem from a messy real world description.

The material is written at the introductory level, assuming no more
knowledge than high school algebra. Most concepts are developed from scratch. I
intend this to be a *gentle* introduction.

You will need an Adobe Acrobat reader to read the files. A free reader is downloadable from www.adobe.com

Comments and suggestions are actively sought. Please contact the author at chinneck@sce.carleton.ca This is a *draft*,
so some diagrams are hand-drawn, and there may be typos, etc. Further chapters
will be added as time permits. Please let me know of any corrections that are
needed.

Browse the algorithm animations. These provide animated illustrations of many of the key concepts. The student developers of these animations were funded through an IBM Faculty Award to Prof. Chinneck. Last revision: August 28, 2007.

Chapter 1: Introduction. An introduction to the process of optimization and an overview of the major topics covered in the course. Last revision: August 22, 2006.

Chapter 2: Introduction to Linear Programming. The basic notions of linear programming and the simplex method. The simplex method is the easiest way to provide a beginner with a solid understanding of linear programming. Last revision: August 18, 2006.

Chapter 3: Towards the Simplex Method for Efficient Solution of Linear Programs. Cornerpoints and bases. Moving to improved solutions. Last revision: August 18, 2006.

Chapter 4: The Mechanics of the Simplex Method. The tableau representation as a way of illustrating the process of the simplex method. Special cases such as degeneracy and unboundedness. Last revision: August 18, 2006.

Chapter 5: Solving General Linear Programs. Solving non-standard linear programs. Phase 1 LPs. Feasibility and infeasibility. Unrestricted variables. Last revision: August 18, 2006.

Chapter 6: Sensitivity Analysis. Simple computer-based sensitivity analysis. Last revision: August 18, 2006.

Chapter 7: Linear Programming in Practice. Mention of other solution methods such as revised simplex method and interior point methods. Mention of advanced techniques used in practice such as advanced and crash start methods, infeasibility analysis, and modelling systems. Last revision: August 18, 2006.

Chapter
8: An Introduction to Networks. Some basic network concepts. The shortest
route problem. The minimum spanning tree problem. Last
revision: August 18, 2006.

Chapter
9: Maximum Flow and Minimum Cut.
The maximum flow and minimum cut problems in networks. Last revision: August 18, 2006.

Chapter 10: Network Flow Programming. A surprising range of problems can be solved using minimum cost network flow programming, including shortest route, maximum flow and minimum cut, etc. Variations such as generalized and processing networks are also briefly introduced. Last revision: August 18, 2006.

Chapter 11: PERT for Project Planning and Scheduling. PERT is a network-based aid for project planning and scheduling. Many optimization problems involve some aspect of the timing of activities that may run sequentially or in parallel, or the timing of resource use. PERT diagrams help you to understand and formulate such problems. Last revision: August 18, 2006.

Chapter 12: Integer/Discrete Programming via Branch and Bound. Branch and bound is the basic workhorse method for solving many kinds of problems that have variables that can take on only integer, binary, or discrete values. Last revision: August 22, 2006.

Chapter 13: Binary and Mixed-Integer Programming. These are specialized versions of branch and bound. A binary program has only binary variables (0 or 1 only). A mixed-integer program looks like a linear program, except that some or all of the variables are integer-valued (or binary-valued), while others might be real-valued. Last revision: August 18, 2006.

Chapter 14: Heuristics for Discrete Search: Genetic Algorithms and Simulated Annealing. Some problems are just too big for branch and bound, in which case you must abandon the guarantee of finding the optimum solution and instead opt for heuristic methods which can only guarantee to do fairly well most of the time. Genetic Algorithms and Simulated Annealing are two popular heuristic methods for use on very large problems. Last revision: August 22, 2006.

Chapter 15: Dynamic Programming. This optimization technique builds towards a solution by first solving a small part of the whole problem, then gradually incrementing the size in a series of stages until the whole problem is solved. Efficiency results from combining the local solution for a stage with the optimum found for a previous stage. We look at the simplest deterministic discrete cases. Last revision: September 8, 2006.

Last update: August 28, 2007.