ISYE 6501 Module 15 Reference Material Slide 1 - Lesson 15.1 (M): Introduction to Optimization

ISYE 6501 Module 15 Reference Material Slide 1 - Lesson 15.1 (M): Introduction to Optimization In quite a few of the lesson in this class, we've seen various models that I've noted can be solved using optimization. Y ...

ISYE 6501 Module 15 Reference Material Slide 1 - Lesson 15.1 (M): Introduction to Optimization In quite a few of the lesson in this class, we've seen various models that I've noted can be solved using optimization. You've probably heard me refer to optimization in lessons on classification. Clustering, regression, variable selection, time series analysis and more. The reason is that many, perhaps most, statistical and machine learning models involve optimization to find their answers. So optimization is a key underlying part of descriptive and predictive analytics, as we'll see a little bit more formally in this topic. But optimization is also a very important topic in analytics in its own right, especially for prescriptive analytics. The type of analytics that asks, given what I know and what I predict, what's the best course of action to take? Optimization can answer questions like, which airplane mechanic should be scheduled for each shift over the next week? To meet the expected maintenance requirements at O'Hare Airport at lowest cost. Making sure we don't violate any federal regulations or union contract requirements and accounting for unexpected breakdowns. How much crude oil should be send by tanker and by pipeline from each oil field to each refinery to meet demand and avoid oversupply while keeping costs low? What webpages should be optimized in a server farm? And how many copies of each should be stored to maximize the profit made by responding quickly to hits? How should a large machine shop sequence its production to get maximum throughput while meeting all clients' deadlines? Taking into account the reality that some output will fail inspection and need to be remained.And even the GPS routing problem, what's the shortest route from my house to the airport, given current and predicted traffic? In my own research and consulting, I've used optimization models to suggest how Army recruiters could most efficiently use their resources. Create a method for Major League Baseball teams to determine their draft priority. Plan worldwide delivery schedules and routes for giant oil tankers. And schedule electricity generation that accounts for specific effects of current and upcoming weather patterns on the atmospheric effects of pollution. As you can see, optimization can be a very powerful tool in analytics, sitting on top of descriptive and predictive analytics. It allows you to not only use analytics to report on things but also to direct your organization at strategic, operational and tactical levels. But optimization is also a more difficult tool to use than many of the models we've seen before. There's nice software that automates many of the models we've seen, both building them and solving them. In fact, you've had a chance to use some of that software in your homework assignments. But optimization software is different. There's good software for solving optimization models, but there isn't yet good software to build the models for you. Learning to build optimization models takes a lot of practice, more than we have time for in this course.I'll show you some examples and give a few general principles and pointers, but you'll have to practice on your own. Or even better, you can take Georgia Tech's excellent online elective course on Applied Optimization. Where we'll help you learn a lot more of the important details and advanced techniques. Before we go on and start learning about optimization models, I wanna highlight a 2013 study by Gartner. They surveyed lots of companies across a wide variety of industries to find out about their use of analytics. Only 3% reported the use of prescriptive analytics. It wasn't very common, primarily, I believe, because of the following difficulties. In addition to needing good data and descriptive and predictive analytics as a foundation. They need people with specialized training to build optimization models, and to a lesser extent, simulation models. But just three years later, Gartner was predicting growth to 35% by 2020, from 3% to 35% in just seven years. So my perspective is that it's not just worth learning about, it's necessary to learn about prescriptive analytics models. Because either the organization you join will already using them or because they'll want to be using them. And your knowledge can give you an important edge. So go ahead, cue up the next video and let's get started. Slide 2 - Lesson 15.2 (M): Elements of Optimization ModelsIn a previous lesson we saw how optimization is both a key piece of other analytics models we've seen in this course. And also a powerful tool in its own right for answering prescriptive analytics questions. Given what we know and what we can predict, what are the best actions to take? We also saw that in contrast to many of the other models we've seen where there's good software both to create a model and to solve it. In optimization we only currently have good software for solving models. Building optimization models requires a lot of human insights and expertise. So the next few lessons will help you learn the basics of optimization modeling. In this lesson specifically, we're going to see three key pieces of optimization models. Optimization models have three main components: variables, constraints, and objective function. Let's start with variables. The variables in a model are decisions that the optimization solver will pick the best value for. For example, if we're optimizing a political candidate's travels around the country, then we might have variables like these. xi might be the total amount of time the candidate spends in state i, yi might be the number of visits the candidate makes to state i. And zi might be 1 if the candidates ever visit state i and 0 otherwise. We might also want to make more specific decisions,like which days the candidate visits each state. So we might have a variable like wid, the time the candidate spends in state i on day d specifically. And vid might be 1 if the candidate visits state i on day d, and 0 if not. These are all decisions that we're trying to make, and if we build our model correctly, the optimization software will then find the best solution, the best combination of values for the variables. The constraints in a model are restrictions on those decisions that we make, restrictions on values of the variables. For example, we might have restrictions like these. There are only 30 days left in the campaigns so the total time the candidates spends on all states can't be more than 30 total days. In other words, the sum over all states i of xi, the time the candidate spends in state i, must be less than or equal to 30. We might also want to make sure for example, that the candidate visits Florida at least 3 times in the last week, days 24 through 30. In other words, the sum over days d equals 24 through 30 of v Florida d must be greater than or equal to 3. And we need to link our variables together correctly. vid is the number of visits to state i on day d, and yi is the total number of visits to state i. So we need to make sure that when we sum up vid over all days d, the total equals yi. That's an important constraint. We might expect it to be true, because of how we've defined the variables in English, but optimization solvers only look at the math. They don't look at the words of what we want the variables to mean. So if we don't use constraints to explicitly tell the solver how variables should be related. The solver will go happily ahead and find a mathematical solution, telling our candidate to visit state i 12 times, but that each vid should be 0.The last piece of an optimization model is called the objective function. It's a measure of the quality of a solution, the quality of a set of values for the variables, which we're trying to maximize or minimize. In our campaign example, the objective function might measure how many additional votes we could expect the candidate to get based on the campaign schedule. Perhaps, alpha times the population of state i times the square root of time spent in state i plus a third times however long is spent in neighboring states. Plus beta times the number of times each state is visited each day, times the factor for the day, maybe visiting too early or too late dilutes the effect. You might wonder of course, how we know the value of alpha and beta and the square root relationship to the amount of time spent in a state and its neighbors. That's one of the ways that optimization can sit on top of other analytics models. In order to use the optimization model, we first need to use statistical methods, like regression, to find the right values of alpha and beta, to determine the relationship between time and votes, etc. In fact, it's pretty common for optimization models to require input that's found as the output from other models. And we'll see some examples when we get to the part of the course when we start putting a variety of models together to create a comprehensive solution to a question or problem.I've been using the word solution pretty loosely, but in optimization a solution is a value for each variable. For example, the amount of time spent in each state. A solution that satisfies all of the models constraints is called the feasible solution. And the feasible solution that has the best objective function value is called the optimal solution. That language is just like in everyday life, feasible means it’s possible to do and optimal means best. Which brings me to one of my pet peeves. When you're taking about solutions to an optimization problem, pleased don't use the phrases more optimal or most optimal. It's like saying more best or most best, and neither one makes sense. So those are three main pieces of optimization models. Variables, constraints, and objective function, and the output of an optimization model, an optimal solution. But specifying the model itself is as much an art as a science. Sometimes the best answer is pretty straightforward, and other times the straightforward answer doesn't work. We'll see some examples in an upcoming lesson.