The Intuitive Basics of Optimization
This article will give you knowledge on the basic components of optimization using your intuition and an "everyday" example. After this read, you will understand the definitions and roles of (1) objectives, (2) constraints, (3) decision variables, (4) solution space and (5) solutions in solving optimization problems. This is meant to be an introduction to the concepts of optimization – it does not cover the math or specific techniques of how optimization can be performed. That is for future articles!
After reading this article, you can see how the Optimization framework can be used in the ‘real world' stock cutting problem in the linked article below (it was my first TDS article!).
Contents
- The intuition of optimization
- Objectives – what is our goal?
- Constraints – what can't we do?
- Decision Variables and Parameters — what can and what can't we control?
- Feasible Region & Solution Space – Where does our optimal solution come from?
- Solutions – what does the optimization recommend we do?
- Wrapping it up
The Intuition of Optimization
Optimization is everywhere in the world. From our daily lives, to complex engineering problems, to the board room. Because of its ubiquitous nature, optimization is often very intuitive to us. My goal is to use our intuition to tie informal, everyday optimization to the more formal concepts of mathematical optimization (although we will stop before we get to the actual mathematical components).
At its core, optimization is simply trying to get the most of something good or, the least of something bad given the resource limitations you have. In other words, it is wanting the best given our circumstances. In general, I think we all want that in essentially all aspects of our lives!
This article will go over the main components of optimization following the intuitive example of optimizing a commute to work. There are so many other ways that optimization shows up in our daily lives! I'll list a few here just to get your thoughts going:
- Selecting movies or shows that we will enjoy the most
- Looking for the cheapest place to buy gas
- Creating a lawn watering schedule that will use the least amount of water
- Planning an exercise goal that will improve your fitness the most
- Scheduling your day to be as productive as possible
While the examples above are not in the language of formal optimization, these are all legitimate optimization problems! Let's transition to talking about the components of formal optimization so we can understand how to translate everyday optimization problems to problems that can be solved using mathematical optimization techniques.
Objectives
The objective is the purpose of your optimization. The objective will answer the question "what is our goal?" Every optimization problem will have an objective that is one of two forms – maximization (when you want the most of a good thing, e.g., profit) or minimization (when you want the least of a bad thing, e.g., cost). Given an optimization problem, it is pretty intuitive to understand whether it is an minimization or maximization problem. Below are the types of optimization problems for the examples we set out in the first section:
After figuring out what type of an optimization problem we have, we need to create an objective function in order to prepare for mathematical optimization. An objective function is a mathematical formula that calculates the objective metric. In our commute example, a possible objective function would take a specific route to work and return the length of the route in miles. Creating the objective function requires us to be very specific about what we want to optimize, there is no space for ambiguity!
We really want to make sure we take our time when setting up our objective. It is like pointing a boat in the right direction before going on a long voyage. It is worth taking the time to get it correct and precise at the beginning. Otherwise you may get some unexpected results in the end!
Let's think more about creating the objective function for our example of finding the shortest commute to work. What do we mean by shortest? Shortest amount of time? Shortest total distance? They aren't necessarily the same. We should also take a step back and make sure ‘shortest' is the right superlative for our optimization. Maybe there are better things we could optimize for — perhaps we want the route with the lowest total expense (gas usage, tolls etc.) or maybe the lowest stress (less traffic or fewer stressful driving elements). We will stick with the ‘shortest' objective and decide that we want the shortest commute defined as miles driven for the rest of this article. But I hope that I've demonstrated that we should always be thoughtful and precise when deciding on an objective function.
Okay, so our objective is to minimize the number of miles in our commute. If we just ran an optimization on that objective, we would get a straight line from our house to the office. This is completely useless because it's impossible — we would have to drive through trees and buildings! Correctly formulated constraints, which we discuss in the next section, will guarantee that our optimization gives us reasonable and useful results.
Constraints
Most optimization problems have constraints, especially problems in the "real world." As we discussed at the end of the last section, constraints give us reasonable and usable optimization results (assuming we set them up correctly). Without constraints, we are very likely to get solutions that are completely useless because we can't actually implement them.
Some constraints are needed to get feasible solutions, others we add to get better solutions. __ The constraint that our route needs to use roads is a constraint that forces the optimization to give us a feasible solution. Other constraints can give better solutions by balancing other factors with the objective function. In the example, our primary concern is that our commute has as few miles as possible (that is why it is our objective), but we are also concerned with other aspects of the commute. We can influence those aspects by adding constraints to our optimization problem.
Here are some examples of potential constraints we could add to control the type of optimal solution we get:
While it may seem like a good idea to add a bunch of constraints to an optimization, constraints come at a cost. More constraints make the optimization problem more complicated and require more computation resources. But worse than that, constraints will lower the optimal value of the objective function. For example, adding the traffic light constraint could increase the total miles of the commute that the optimization selects. If you add too many constraints, you may not even be able to find a solution!
Let's demonstrate the cost of constraints with the traffic light constraint from above.
We originally set the traffic light limit to less than or equal to three. That constraint excludes route D, which happens to be the shortest route. Of the remaining routes, route A is the shortest and therefore is the constrained optimal solution.
One way to measure the cost of a constraint is to run the optimization with and without it and compare the results. In our example above, with it, we select route A with 9 miles and without it, we select route D with 8 miles. So our constraint costs us 1 additional mile in our commute. With the knowledge of the cost, we can review if we want the traffic light constraint at the level we originally specified.
Below are the details of the results and costs of different levels of traffic light constraints:
The main takeaway here is that the more restrictive the constraint, the worse your constrained optimal result will be. If the constraints are too restrictive, then it is possible that there are no solutions that meet the constraint. It is important to be prudent about the constraints that you use, because they come at a cost. In this article, we only looked at one constraint, but the issues we explored here compound as we add additional constraints.
Before we move to the next section, I do want to quickly add a term to the vocabulary of this article. Let's say you have a constraint that doesn't change the optimization result. This constraint is called ‘non-binding.' Meaning that it actually doesn't impact the optimization. Non-binding constraints increase the computation cost of an optimization, but they don't reduce the quality of the optimization output. Why would we have non-binding constraints? We'll, we don't go out of our way to add them. Non-binding constraints usually happen when another constraint is entirely more restrictive than one of the other constraints.
In our traffic light example, let's say we added a constraint that the time of the commute could not be more than 30 minutes and that Route D (the route with 4 lights) was the only route that had a commute >30 minutes. Since route D also had 4 lights, it was excluded by the light constraint. So, with and without the time limit constraint, the optimization would return the same results. So, if non-binding constraints aren't doing anything, should we just drop them? The answer is maybe – usually whether or not a constraint is non-binding depends on the solution space, which could change. If the solution space changes to a point where the non-binding constraint becomes a binding constraint, we will definitely want it! If you know that the solution space won't change or you have reason to believe that the non-binding constraint will always be non-binding, you should take it out. Otherwise, it is might be a good idea to leave it in.
Decision Variables and Parameters
Decision variables are the things that are in our control in the optimization; they are what we can choose. Parameters are inputs into an optimization. They should represent the problem we are facing and are out of our control to modify.
In the commuter example, our decision variables are whether or not we select a specific route. The optimization has the power to select routes to find the best solution given the constraints. The number of miles and traffic lights for each route are parameters. They are given in the problem and the optimization has to work with them, rather than change them. Typically, the objective function will have both decision variables and parameters – the optimization will put various decision variables through the optimization function, which will use the combination of the decision variables and parameters to calculate the objective value of the possible solutions it explores.
Most optimization problems have many possible solutions to explore. In the next section, we will discuss key terms regarding the possible solutions an optimization can consider.
Feasible Region & Solution Space
The solution space for an optimization problem is the set of all possible solutions. For our commute example, the solution space consists of all possible routes to get from home to work.
The feasible region is a subset of the solution space. The feasible region is the available solutions that remain after the optimization's constraints have been applied.
A common challenge that comes up in optimization is gigantic solution spaces and feasible regions. For some types of problems, the solution space is essentially infinitely large. For our example (though we used a simplified representation above), think of all of the potential unique routes to get from one place to another! There are various techniques to grapple with this challenge — but these techniques are out of scope for this article and will be tackled in future optimization articles.
Let's get some intuition as to why solution spaces and feasible regions can grow so quickly (I also cover this topic in the link at the beginning of the article). We'll say that there are 3 turns you have to take to go to work. At each turn, you can go left or right. How many potential routes can you take (we'll make the simplifying assumption that no matter which combination of turns you take you get to work)? At the first turn you can go left or right, at the second turn you can go left or right etc. Since there are two choices per turn the number of potential routes to work you can take is 2³ or 8. That isn't too bad right? But beware, for a small problem this is very manageable. But the issue is how fast the problem grows as you add more turns. Now, let's suppose that you have to take 10 roads to work, the total number of options dramatically increases to 1024, but it gets worse! To go from 10 to 11, we increase from 1024 to 2048 — that is from adding just one more turn! The chart below demonstrates how adding additional turns to our commute causes the solutions space to explode.
Solutions
I've already used the term solution multiple times in this article and I still haven't defined it! I think the definition is pretty intuitive – so I probably got away with it, but let's define it here just in case. A solution to an optimization problem is the set instructions for how to achieve optimal results. For the commute example, a solution is a specific route to work. I listed what a solution constitutes for the optimization examples I gave earlier below:
Solutions are in the solution space, and if they are feasible solutions (these are the ones we are interested in), they are in the feasible region as well.
Of course, not all solutions are created equally – otherwise there would be no point in optimization! We want the best solution we can possibly find! We rank solutions against each other using their objective values. Each solution has an objective value, which is the output you get when you put a particular solution through the objective function. In our commute example, the miles associated with each route are the objective values for the solutions.
The optimal solution is the solution with the best (lowest for minimization, highest for maximization) objective value. In our commute example, route D is the unconstrained optimal solution – because it has the fewest miles.
Some algorithms guarantee that the solutions they find are optimal, while others seek to approximate the optimal solution. Why not always use an algorithm that is guaranteed to find the optimal? Well, depending on the optimization problem, finding optimal solutions can be really hard. Often, algorithms that guarantee the optimal solution can be very expensive in computation power and time. Generally, approximately optimal solutions are much easier to find and are sufficiently optimal for many optimization problems.
Below is a diagram that explains the various solution-related terms we've covered:
Note: in the diagram, there is a single optimal solution. This doesn't necessarily have to be the case. It could be that there are multiple solutions that have the same optimal objective value.
Wrapping it up
I hope that you've been able to capture the role of the main parts of optimization from this article. The graphic below gives a definition and quick notes for each optimization component we covered.
With this knowledge, we have the basic understanding and vocabulary to explore how optimization is implemented. Optimization is a powerful tool that can give insights that make big impacts! Stay tuned for multiple series on the details of specific optimization approaches!
