DMA - Optimization

Optimization problems are one of the three core concepts in HBA1 DMA Course. It’s also likely the majority focus of the final!

Scope

In this course, we deal with two kinds of optimization problems. Linear, and non-linear. Effectively, they’re the same thing to us, we approach them the same way, but we just need to be able to distinguish the two.

When to Use Optimization

This one is straight forward. Whenever you’re asked to pick the most optimal value. Examples include:

• Pricing for tires so you maximize profit
• Maximizing area with a given amount of fencing
• Picking delivery distribution routes

Linear Vs Non-Linear

What does it mean for a problem to be linear? Really all it means is, if I increase a variable by two, it should have double the effect on the end result compared to if I just increased it by one.

That was a bit of a mouthful, so let’s look at an example.

Linear Example

Suppose we have a company that sells widgets. Each widget costs $5 to make, and we sell them for $15. So, for each widget we sell, we make $10 profit.

If we sell $x$ widgets, our profit $P$ can be represented as:

$$P=10x$$

Here, if we increase $x$ by 2 (selling 2 more widgets), our profit increases by $20, which is double the increase in profit if we only sold 1 more widget ($10). This is a linear relationship.

Non-Linear Example

Now, let’s consider a non-linear example. Suppose we have a company that sells software licenses. The more licenses we sell, the more support we need to provide, which increases our costs.

If we sell $x$ licenses, our profit $P$ can be represented as:

$$P=100x-0.5x^2$$

Here, if we increase $x$ by 2, the increase in profit is not simply double the increase when we increase $x$ by 1. This is because of the $-0.5x^2$ term, which introduces a non-linear relationship.

Summary

It’s important to write out the algebra or just conceptually understand the difference between the two. The only difference to us, however, is:

1. We should know when to use GRG Nonlinear vs Simplex LP in Excel Solver.
2. The sensitivity report will look different when using the two solvers. We only look at sensitivity reports from Simplex LP.

If you’re interested, behind the scenes, the two solvers work very differently. The linear solver assumes that it’s walking on a plane, so it has a much easier time finding the max. In contrast, the nonlinear solver uses derivatives to find the maximum of continuous functions!

How to Perform Optimization

Step 1: Set up the Problem

Optimization requires 3 things!

Thing 1: Objective Function

This is a function we are seeking to maximize or minimize. It’s important that this is a single function, you can’t optimize for two things at once. We talk about what to do in that scenario in the “Other Information for Reference” at the end of this note.

Examples of objectives functions are:

• Revenue (maximize)
• Cost (minimize)
• Profit (maximize) (it’s important to understand that sometimes, profit is nonlinear whereas revenue is linear, and we need to choose which one makes the most sense)

Thing 2: Constraints

Sometimes, you’ll get a nasty error saying that the problem is unconstrained. What does that mean? It means that, you told it to… problem maximize profit. But forgot to tell it a maximum number of hours you can work, so the optimizer told you to work an infinite number of hours and thus create all the profit in the world! Bad, so let’s talk constraints now…

Constraints are limitations on certain variables. They can take multiple forms:

• Less than or equal to. Think about, investing a maximum of 100% of your portfolio into stocks.
• Greater than or equal to. Think about, needing at least 8 hours of sleep per night.
• Equal to. Think about, needing to exactly spend $100 on groceries this week.
• integer. Think about, you can’t sell half a car!
• binary. Think about, you either buy the car or you don’t.
• non-negative. Think about, you can’t sell negative cars!

There’s also a thing called “Binary Constraints” that are discussed at the bottom.

Thing 3: Decision Variables

These are the inputs to your model, essentially, what you’re trying to optimize. Some examples include:

• The price to sell our tires at
• The number of tires to produce
• how much to ship between each distribution center
• how much to produce at each powerplant

Example Optimizer Setup

Let’s say we run a factory that produces two products: widgets and gadgets. We want to maximize our profit from selling these products.

Let:

• $x$ = number of widgets produced
• $y$ = number of gadgets produced
• Profit from widgets = $20 per widget
• Profit from gadgets = $30 per gadget
• Maximum production capacity = 100 units
• Minimum production requirement = 10 units of each product
• Maximum budget for production = $2000
• Cost to produce a widget = $15
• Cost to produce a gadget = $25
• Labor hours available = 400 hours
• Labor hours required per widget = 2 hours
• Labor hours required per gadget = 3 hours

Our objective function (profit) can be expressed as:

$$P=20x+30y$$

Our constraints are:

1. Production capacity: $x+y\le 100$
2. Minimum production: $x\ge 10$, $y\ge 10$
3. Budget: $15x+25y\le 2000$
4. Labor hours: $2x+3y\le 400$
5. Non-negativity: $x,y\ge 0$ (this is often included by default in excel but good to explicitly mention it)
6. Integer constraints: $x,y$ must be whole numbers
7. Binary constraints: Not applicable in this example, but could be used if we had a yes/no decision (e.g., whether to launch a new product line).

Our decision variables are $x$ and $y$.

Step 2: Implement the Solver

We use the solver add-in for Excel. Just set up your model, make sure your functions work by playing around with some of the decision variables, and then open the solver.

Set the objective cell, whether you want to maximize or minimize it, and then select your decision variable cells. Finally, add your constraints.

Interpreting Results of the Solver

Optimal Variables

This is the primary result of the solver. After running your optimization, the solver would have set your decision variables to their optimal value. This is the main thing you’re looking for!

Sensitivity Report

This is a big part of this course. The sensitivity report looks different for linear vs nonlinear problems, but generally, we only look at linear problems for this course.

The sensitivity report gives you information about how sensitive your optimal solution is to changes in the coefficients of your objective function and the right-hand side values of your constraints. Additionally, it allows you to consider the impact of a change in your constraints without recalculating the whole report.

Below are the different columns and tables in the sensitivity report and what they mean.

Table 1: Variable Cells

This table provides information about the decision variables in your optimization problem.

Final Value

This is the optimal value of each decision variable after the solver has run.

Reduced Cost

This indicates how much the objective function coefficient of a decision variable would need to improve before that variable would take on a positive value in the optimal solution. That is, “this option is not worth it unless the profit per unit increases by at least this much.”

This variable only has meaning if the “Final Value” is 0, or I’m not including it. If the Final Value is positive, then ignore this value. This is because this is solver convention and means confusing things.

For maximization problems, a positive reduced cost means that increasing that variable would increase the objective function value. For minimization problems, a negative reduced cost means that decreasing that variable would decrease the objective function value.

Objective Coefficient

This is the coefficient of the decision variable in the objective function. This means how much each unit of the variable contributes to the objective function. Recall what I said about Linear vs Non-linear below? This is where that matters. If you have a nonlinear function, this coefficient may not be constant.

Allowable Increase

This indicates how much you can increase the objective function coefficient of a decision variable before the optimal solution changes. Once you increase more than this, you need to redo your optimization.

Allowable Decrease

This indicates how much you can decrease the objective function coefficient of a decision variable before the optimal solution changes. Once you decrease more than this, you need to redo your optimization.

Table 2: Constraints

This table provides information about the constraints in your optimization problem.

Final Value

This is the value of the left-hand side of each constraint at the optimal solution. That is, if you had a constraint that said cost had to be below $2000, this is the actual cost at the optimal solution.

Shadow Price

This indicates how much the objective function value would improve if the right-hand side of a constraint is increased by one unit. That is, how much would it benefit us to increase this constraint by one unit.

For maximization problems, a positive shadow price means that increasing the right-hand side of the constraint would increase the objective function value. For minimization problems, a negative shadow price means that decreasing the right-hand side of the constraint would decrease the objective function value.

Note that shadow prices will only be non-zero for “binding” constraints (which means LHS our value = RHS value), which makes sense, I’m only going to benefit from increasing a constraint if I’m already at the limit of that constraint!

Constraint R.H. Side

This is the right-hand side value of each constraint. This is the value you set when you created the constraint.

Allowable Increase

This indicates how much you can increase the right-hand side of a constraint before the shadow price changes. Once you increase more than this, you need to redo your optimization.

Allowable Decrease

This indicates how much you can decrease the right-hand side of a constraint before the shadow price changes. Once you decrease more than this, you need to redo your optimization.

Other Information for Reference

Optimizing for Multiple Variables

So you can’t do this, you just can’t. But we have creative ways to express this…

Option 1: Optimize for One, Set other as Constraint

You can optimize for one variable, and set the other as a constraint. You can often run it multiple times, tweaking this constraint.

An example of the above was the stock trading case. We had both risk and returns. While we would love to minimize risk and maximize returns, we had to pick one. So we optimized for returns, and set risk as a constraint (maximum risk allowed). We even picked multiple risk levels to see how that changed our returns. Below is the table we created:

Max Allowed Risk	Resulting Return
10%	5.45%
20%	10.9%
30%	16.4%
40%	21.8%

This pretty effectively demonstrated the Efficient Frontier.

Option 2: Create a Compound Objective Function

You can create a compound objective function that combines multiple objectives into a single function. This is often done by assigning weights to each objective based on their importance (a Linear Combination), or a ratio can be used.

In the above example, we could create a compound objective function like this:

$$Objective=w_1\cdot \text{Return}-w_2\cdot \text{Risk}$$

Where $w_1$ and $w_2$ are weights that reflect the importance of return and risk, respectively. By adjusting these weights, you can prioritize one objective over the other.

Another alternative would be to use the Sharpe Ratio.

Unbounded Vs Infeasible Solutions

Sometimes, when you run an optimization, you’ll get an “unbounded solution” or “infeasible solution” error. Let’s talk about the difference.

As we mentioned above, unbounded solutions refer to when the optimizer was able to optimize your function to infinity! This usually means you missed a constraint and the solver kept on increasing your profit unto infinity!

Infeasible solutions, on the other hand, refer to when the optimizer couldn’t find any solution that satisfied all your constraints. This usually means your constraints contradict each other, making it impossible to find a valid solution.

Binary Constraints

Binary constraints refer to constrains on binary variables.

Binary variables are numbers that can only be 1 or 0. You set these up by setting a “binary” constraint on the variable.

Binary constraints can be particularly challenging because they’re not directly understood, I included a few examples below, but take some time to conceptually understand it!

Example 1: If A is Chosen, then B Must also Be Chosen

$$a\le b$$

• If $a=1$, then $b$ must be 1.
• If $a=0$, then $b$ can be either 0 or 1.

Example 2: If A is Chosen, then B Cannot Be Chosen

$$a+b\le 1$$

• Prevents both being 1 at the same time.
• Equivalent to “at most one of A or B.”

Example 3: Can only Choose A or B (mutually exclusive)

$$a+b=1$$

• Exactly one must be chosen
• If $a=1$, then $b=0$.
• If $a=0$, then $b=1$.

Example 4: At Least One Must Be Chosen

$$a+b\ge 1$$

• Ensures that you cannot leave both unselected.

Example 5: If A is Chosen, then C Must not Be Chosen

$$a+c\le t$$

• Same logic as example 2, but with different variables.

Example Applications

• Facility location: “If warehouse A is opened, distribution center B must also be opened.”
• Scheduling: “If worker A is assigned, worker B cannot be assigned.”
• Portfolio selection: “Choose exactly one of two mutually exclusive projects.”