COURSE OBJECTIVES

Ability to model decision problems through linear programming and interpreting results.

TARGET AUDIENCE

Engineers, economists, scientists and developers interested in modeling decision problems and implementing optimization algorithms.

Introduction to Linear Programming
• Introduction: history, set-up.
• Linear programming terminology: definitions, linear program formulation and graphical illustrations, classical reformulations.
• Notion of convexity.

Simplex algorithm
• Simplex method: principle, dictionary form, tabular form, non-degeneration and cycling, initial base. Implementation through simple examples.
• Applying linear programming to scheduling problems. Illustrating the impact of modeling on solver results.

Duality
• Duality: building a dual program, fundamental results (equality constraints and Lagrange multipliers, inequality constraints and Farkas’ lemma, KKT conditions, weak duality).
• Economic interpretation of dual variables. Using dual variables to handle transportation and stock management problems.
• Post-optimality and sensitivity analysis.
• Variants of the simplex method: revised form, dual simplex.

Interior-point methods
• Interior-point methods: quality of nonlinear approaches, Karmarkar’ algorithm, primal-dual interior algorithm, affine algorithm, complexity and polynomial convergence.

Using a solver
• Taking advantage of a linear programming solver: tips and tricks, and good practices (illustrations with FICO® Xpress).