Module 2 A Survey of Optimization

by Patrick Boily and Kevin Cheung


Traditionally, optimization has been one of the most-frequently used arrows in the operations researcher’s and quantitative analyst’s quiver. From its humble beginning as an offshoot of calculus to its current status as the crown jewel in a variety of industrial contexts (scheduling, financial engineering, transportation networks, rankings, machine learning and deep learning, etc.), optimization allows its users to find the largest output, the smallest wait time, the winning conditions, and so on.

Optimization problems seen in first-year calculus are often solved using differential tools. In this whirlwind tour of the optimization landscape, we discuss problems that do not lend themselves to such an approach, providing a quick survey of optimization problems and algorithms, modeling techniques, an software. We end with case studies that use data envelopment analysis.

Contents

2.1 Beginnings

2.2 Single-Objective Optimization Problem
     2.2.1 Feasible and Optimal Solutions
     2.2.2 Infeasible and Unbounded Problems
     2.2.3 Possible Tasks

2.3 Classification of Optimization Problems and Types of Algorithms
     2.3.1 Classification
     2.3.2 Algorithms

2.4 Linear Programming
     2.4.1 Linear Programming Duality
     2.4.2 Methods for Solving LP Problems

2.5 Mixed-Integer Linear Programming
     2.5.1 Cutting Planes

2.6 Useful Modeling Techniques
     2.6.1 Activation
     2.6.2 Disjunction
     2.6.3 Soft Constraints

2.7 Data Envelopement Analysis
     2.7.1 Challenges and Pitfalls
     2.7.2 Advantages and Disadvantages
     2.7.3 SAS, Excel, and R DEA Solvers
     2.7.4 Case Study: Barcelona Schools

2.8 Software Solvers