That is the (and certain last) a part of a Linear Programming series I’ve been writing. With the core concepts covered by the prior articles, this text focuses on goal programming which is a less frequent linear programming (LP) use case. Goal programming is a selected linear programming setup that may handle the optimization of multiple objectives in a single LP problem.
By the top of this text, you’ll understand:
1. Definition of goal programming and when it must be used
2. The weighted goal programming approach — illustrated with an example
3. The preemptive goal programming approach — illustrated with an example
Definition and Use Case of Goal Programming
Goal programming is a special case of linear programming that enables for multiple — often conflicting — objectives to be balanced. With regular LP problems, you decide a single metric to optimize (minimize or maximize) and set constraints to be certain that the optimal solution is possible. Goal programming is a way that enables for multiple objective metrics to be targeted at the identical time.
The ‘mindset’ of goal programming is fundamentally different from plain vanilla LP problems. Basic LP searches for methods to get as little or as much of a single metric as possible — e.g., maximize profit or minimize waste — subject to constraints. Often conflicting priorities might be present in the target function the constraints. For instance, maximize profit (objective) subject to a maximum amount of waste (constraint). With goal programming, we will move vital constraint metrics into the target function so we will optimize on them moderately than simply constraining them. We will maximize profit and minimize waste at the identical time!
Now could be a superb time to ascertain the instance we are going to probe for the remainder of the article:
Let’s imagine that we manage a factory that makes clothing. Our factory could make pants, shirts, and dresses. Each article of clothing has costs, profit, and waste related to their production. We wish to create a production plan that can make a certain level of profit and likewise waste below a certain quantity because of an environmental commitment. Let’s say that we intend to make $150k a month in profit and we also wish to waste lower than 20k yards of material. Along with our goals, we will’t spend greater than $50k in materials and labor.
The instance above sounds quite a bit like a daily linear programming problem right? Well, the twist is that we will’t make $150k in profit and waste lower than 20k of yards at the identical time. In other words, there can be no feasible solution if we were to plug this into a daily linear programming problem. Typically, the goals set in the issues cannot all be achieved with a single solution, otherwise there wouldn’t be some extent in using goal programming. We’d just use regular old linear programming with our goals as constraints. The true value of goal programming is that it could possibly create a compromise between conflicting goals when regular linear programming would yield an infeasible solution.
The true value of goal programming is that it could possibly create a compromise between conflicting goals when regular linear programming would yield an infeasible solution.
How does goal programming balance and compromise with conflicting goals? There are two popular approaches: (1) weighted and (2) preemptive. We’ll cover these intimately in the next sections.
The weights approach
Here, we’ll dive into the main points of the weights approach. The weights method has a single objective function and runs a single Optimization based on (you guessed it) weights! The proven fact that just one optimization is run under the weights method may seem to be a given — however the preemptive method actually runs multiple linear programming optimizations. We’ll get to that in the subsequent section…
The weights method has specific targets or goals for multiple metrics — e.g., make not less than $150k in profit selling clothes or waste not more than 20k yards of material. For normal LP, we wish to completely optimize. For the weights approach to goal programming, we wish to get as near hitting goals as possible — after we reach a goal, the optimization doesn’t see more profit in further maximization or minimization, so it prioritizes hitting the subsequent most significant goal. If this seems confusing now, don’t worry it’s going to make more sense as we get into the instance.
The objective function for the weights approach is specially formulated to attenuate the differences between a metric’s goal and the actual value of the metric. Let’s jump to our example from above — i.e., we intend to make $150k in profit and waste lower than 20k yards of raw material. Our objective is to attenuate how far off we’re from each of those goals.
Here is the mathematical formulation for this objective:
With our objective function arrange, we’d like to define our constraints. We could have two kinds of constraints (1) goal related constraints and (2) regular linear programming constraints (the identical type of constraints you’ll find in plain vanilla LP). Let’s talk concerning the goal related constraints first.
We’ll have to create two things to establish our goal related constraints, (1) profit and waste functions and (2) multiple slack variables. Let’s undergo these one after the other.
The profit and waste functions are very uncomplicated. They mix our decision variables together to calculate total profit and total waste give a selected solution. Below are the formulas that tie profit and waste to the variety of pants, shirts and dresses we produce:
With our profit and waste functions established, let’s start talking about our slack variables. In goal programming, slack variables are used to measure how far an answer is from hitting a goal. In our example, the variables and are each slack variables — they represent how much lower our profit is in comparison with our profit goal and the way much higher our waste is in comparison with our waste goal. Slack variables are embedded in constraints. Below are the constraint functions for our profit and waste goals — again, the and the are our slack variables:
Note that we’ve plus and minus slack variables — this enables us to miss the goal on either end. We only wish to penalize the slack variable that goes in the other way of our goal (e.g., we don’t wish to penalize profit than our goal, we only wish to penalize profit) — that’s the reason just one slack variable per goal is in the target function. With this latest notation, let’s rewrite our objective function:
Now we have now done all the special work for goal programming. The final thing we’d like to do is quickly add our plain vanilla budget constraint. We’re using a daily constraint for our budget because, in our example, it’s a hard constraint. Unlike with profit and waste, we cannot violate the budget.
Now, we’ve a totally specified goal programming problem. Let’s set it up in Python and solve!
# $150,000 in profit
problem += profit + profit_deviation_neg - profit_deviation_pos == 150000, "Profit_Goal"
# Waste goal: Not more than 20,000 yards of waste
problem += waste + waste_deviation_neg - waste_deviation_pos == 20000, "Cost_Goal"
# Budget constraint
problem += cost <= 50000
# Solve the issue
problem.solve()
# Display the outcomes
print("Status:", pulp.LpStatus[problem.status])
print("Pants produced:", pulp.value(pants))
print("Shirts produced:", pulp.value(shirts))
print("Dresses produced:", pulp.value(dresses))
print("Cost :", pulp.value(cost))
print("Profit :", pulp.value(profit))
print("Profit deviation (positive):", pulp.value(profit_deviation_pos))
print("Profit deviation (negative):", pulp.value(profit_deviation_neg))
print("Waste :", pulp.value(waste))
print("Waste deviation (positive):", pulp.value(waste_deviation_pos))
print("Waste deviation (negative):", pulp.value(waste_deviation_neg))This optimization recommends we make 0 pants, 5,000 shirts and 0 dresses. We make $150k in profit which matches our goal exactly and we waste 50k yards of material which exceeds our max waste by 30k yards. The total results are printed by the code and shown below:
Now that we’ve got the fundamental structure of the weights approach down, let’s actually talk concerning the ! In our first example, we gave equal weights to a dollar of profit and to a yard of waste. This probably doesn’t make a variety of sense because they're different units. Setting the weights is a subjective decision to be made by the practitioner. For our example, we’ll resolve that wasting 1.5 yards of material is as bad as making $1 of profit is sweet. In other words, we’ll increase the load of material waste to 1.5 in our objective function.
problem += profit_deviation_neg + 1.5*waste_deviation_posThe optimization with the updated rates recommends we make about 8,572 pants, 7,143 shirts and 0 dresses. With this solution, we generate $107k in profit (which is a goal miss of $43k) and we waste 20,000 yards of material which matches our goal exactly. The total results are printed by the code and shown below:
Clearly, shifting the weights of the goals can have large impact on the optimization results. We'd like to fastidiously set our weights to adequately balance the relative importance of our goals!
Now that we've a solid understanding of how the weighted approach works, let’s shift to talking concerning the goal programming with the preemptive approach.
Preemptive Approach
While the weights method balances goals using weights in the target function, the preemptive method gives hierarchical priority to goals through iterative optimizations. That’s a variety of words, don’t worry, we’ll break it down!
Listed here are the steps to the preemptive approach:
1. Run a daily linear programming optimization in your first goal — e.g., maximize profit
2. Save the target value from that run
3. Run one other regular linear programming on the subsequent most significant goal — e.g., minimize waste — but, add the target value from the last run as a constraint
4. Repeat the method until you've undergone all goal metrics
Two vital features of the preemptive method are (1) it prioritizes goals by rank and (2) the target value of a better importance goal can't be decreased (due to hard constraint) when optimizing lower priority goals. Let’s go over an example to construct intuition.
For our example, let’s say that profit is crucial goal and minimizing waste is the second. We’ll start out by running a plain vanilla optimization that maximizes profit:
# Define the issue
problem = pulp.LpProblem("Clothing_Company_Goal_Programming", pulp.LpMaximize)
# Decision variables: variety of pants, shirts, and dresses produced
pants = pulp.LpVariable('pants', lowBound=0, cat='Continuous')
shirts = pulp.LpVariable('shirts', lowBound=0, cat='Continuous')
dresses = pulp.LpVariable('dresses', lowBound=0, cat='Continuous')
# Profit and price coefficients
profit = 10 * pants + 3 * shirts + 15 * dresses
cost = 5 * pants + 1 * shirts + 10 * dresses
waste = 1.5 * pants + 1 * shirts + 3 * dresses
# Objective function: Maximize profit
problem += profit
# Constraints
# Budget constraint
problem += cost <= 50000
# Solve the issue
problem.solve()
# Display the outcomes
print("Status:", pulp.LpStatus[problem.status])
print("Pants produced:", pulp.value(pants))
print("Shirts produced:", pulp.value(shirts))
print("Dresses produced:", pulp.value(dresses))
print("Cost :", pulp.value(cost))
print("Profit :", pulp.value(profit))The outcomes of the profit maximizing LP problem are below:
So, our objective function says to make 50k shirts and collect a profit of $150k. This was only the primary optimization we're going to run though! Following the algorithm outlined above, we are going to now run one other LP that minimizes waste but, we are going to add a constraint of profit ≥ $150k to make sure we don’t get a worse profit.
# Define the issue
problem = pulp.LpProblem("Clothing_Company_Goal_Programming", pulp.LpMinimize)
# Decision variables: variety of pants, shirts, and dresses produced
pants = pulp.LpVariable('pants', lowBound=0, cat='Continuous')
shirts = pulp.LpVariable('shirts', lowBound=0, cat='Continuous')
dresses = pulp.LpVariable('dresses', lowBound=0, cat='Continuous')
# Profit and price coefficients
profit = 10 * pants + 3 * shirts + 15 * dresses
cost = 5 * pants + 1 * shirts + 10 * dresses
waste = 1.5 * pants + 1 * shirts + 3 * dresses
# Objective function: Minimize the material waste
problem += waste
# Budget constraint
problem += cost <= 50000
problem += profit >= 150000
# Solve the issue
problem.solve()
# Display the outcomes
print("Status:", pulp.LpStatus[problem.status])
print("Pants produced:", pulp.value(pants))
print("Shirts produced:", pulp.value(shirts))
print("Dresses produced:", pulp.value(dresses))
print("Cost :", pulp.value(cost))
print("Profit :", pulp.value(profit))And listed below are the outcomes of this final optimization:
The astute observer will notice that the optimization is the very same 😅. This will often be the case with the preemptive method. The constraint of previously optimized goals might be very restrictive. The one time when iterative optimizations are different is that if there are multiple ways to get the optimal values for previous goals. For instance, if there have been two ways to get $150k in profit; one had more waste and the opposite had less, our second iteration would return the outcomes of the answer with the lower waste. Within the preemptive method, there isn't a trade off between the goals. Even when there was an answer that made $149k in profit with 0 yards of waste, the preemptive method would all the time select $150k in profit with 50k yards of waste. The additional $1000 of profit is infinitely more vital than any amount of wasted fabric.
The preemptive method must be used when goals are clearly prioritized, and there isn't a substitution between them — meaning no amount of success in lower priority goals can compensate for reduced optimization in higher priority ones. When used appropriately, the preemptive method might help optimize a primary goal while trying to seek out good solutions for lower priority goals very effectively.
Conclusion
Goal programming provides a framework that extends traditional linear programming to optimize multiple metrics at the identical time. The weighted approach balances priorities via weights in the target function and is suitable when objective metrics have relative importance that might be quantified. The preemptive method is an iterative approach that offers priority to metrics based on hierarchy. It is suitable when some objectives are wholly more vital than others. Each approaches might be powerful optimization techniques when applied in the right context!
Glad optimizing!
