Master LLMs with our FREE course in collaboration with Activeloop & Intel Disruptor Initiative. Join now!

Publication

Multi-Objective Optimization Problem using Goal Programming
Latest

Multi-Objective Optimization Problem using Goal Programming

Last Updated on August 11, 2021 by Editorial Team

Author(s): Supriya Ghosh

Optimization

Multi-Objective Optimization where Goal Programming wins and Linear programming give up….

It is well known that the three pillars of data science that we need to understand quite well from a mathematical viewpoint are Linear Algebra, Statistics, and Optimization which are used pretty much in all data science algorithms.

Source : https://www.reddit.com/r/MathJokes/comments/f05kuv/lets_mathematically_optimize_our_life/

Optimization is said to be the heart of almost all machine learning and statistical techniques used in data science. The essence of most machine learning algorithms is to build an optimization model and then learn the parameters in the objective function from the given data.

Here in this writeup, I will explain multi-objective optimization problem formulation using Goal programming in detail.

Source : https://users.ece.cmu.edu/~yuejiec/MachineLearning.html

Multi-objective optimization also known as multi-objective programming or Pareto optimization deals with optimization problems involving more than one objective function to be optimized simultaneously. This has been applied in many fields of science, including engineering, logistics, marketing, transportation, economics, etc. where optimal decisions need to be taken with trade-offs between two or more conflicting objectives.

A few of the most common examples seen in our daily life are:

Minimizing cost and maximizing comfort while buying a car,

and

Maximizing performance while minimizing fuel consumption and dangerous pollutant emission of a vehicle.

The above problems involve two and three objectives, respectively. But in practical situations, there can be more than three objectives.

Hence, to understand how multi-objective optimization problems can be developed and modeled, we need to understand Goal Programming thoroughly.

Let us start with a formal definition of Goal Programming as referenced in Wikipedia.

Source : https://www.pinterest.com/pin/17099673557155171/

Goal programming is a branch of multi-objective optimization, which in turn is a branch of multi-criteria decision analysis. It can be thought of as an extension or generalization of linear programming to handle multiple, normally conflicting objective measures.

Now the question arises, why and when do we encounter multiple objective situations, and what is the need for Goal Programming?

In today’s dynamic business environment, most of the time organizations have multiple conflicting objectives to achieve. Not only do firms look for profit and revenue maximization or cost minimization but have other non-profit goals to cater to like social responsibilities, public relations, industrial and employee relations, etc.

Source : https://www.pinterest.com/pin/129337820520206879/

Under such situations, goal programming assumes utmost importance and serves as a powerful quantitative technique capable of handling multiple decision criteria.

But why not Linear programming is used in such cases?

Source : https://www.pinterest.ph/pin/314618723953095984/

To understand this let us see the differences between Linear Programming and Goal Programming with the help of the below table.

Linear Programming vs Goal Programming

Source : By Author

Now since we are familiar with the differences, we know why Linear programming cannot be used in multi-objective problems?

Let’s move on further to discuss how the Goal programming model can be developed using a real-life example. In fact, formulating a correct model based on the problem at hand is the most difficult part of multi-objective decision making /optimization. And believe me, once the model is formulated correctly, solving it, and extracting outcomes are pretty easy.

Source : https://www.performanceinpeople.co.uk/blog/Introducing-Goal-Mapping/

Let me reiterate three main characteristics of Goal programming problems that we need to keep in mind while forming the model.

1. There is no single objective but multiple goals to be attained.

2. Goal programming models are all minimization problems as deviational variables (overachievement and underachievement) need to be minimized.

3. The deviation from the high — priority goal must be minimized to the maximum extent possible before the next-high-priority goal is considered.

Let us understand model formation through an example –

One of the popular lighting companies produces two products range, colorful lampshades and LED lights. Both the product requires a 2 — step production process involving wiring and assembly. It takes about 2 hours to wire each lampshade and 3 hours to wire each LED light. Final assembly of the lampshade and LED light requires 6 and 5 hours respectively. The production capability is such that only 12 hours of wiring time and 30 hours of assembly time are available. The company is stringent on utilizing wiring department hours to the maximum without any wastage and also looking forward to no overtime in the assembly department. It earns a profit of $7 from each lampshade and $6 from each LED light. Also, the company has a contractual obligation to fulfill a minimum of 7 LED lights delivery.

But in parallel, the company is moving to a new strategic location and feels that initially maximizing profit is not a realistic objective. Management sets a profit level of $30 that would be satisfactory during this period.

The company wants to find out the product mix that achieves this goal as closely as possible given the production time constraints.

Here in this example, the company is aiming to achieve several goals altogether. Let me list down the goals first.

1. Goal 1: To gain a profit of $30 during the production period.

2. Goal 2: To fully utilize the available wiring department hours.

3. Goal 3: To avoid overtime in the assembly department.

4. Goal 4: To meet a contract requirement to produce at least 7 LED lights.

Next, I am setting up the deviational variables.

Setting up the choice variables

X1 = Number of Lamp Shades produced

X2 = Number of LED lights produced

Setting up Goal priority as per relevance to the Business and management.

Hence P1 is more important than P2 and P2 more important than P3 and so on.

Let’s consider that it does not impact business and management if there is Overachievement of the profit target and Overachievement of LED light production.

So now our model is all set and formulated as per the requirement of the problem at hand.

Let me summarize the Goal Programming Model Formulation steps.

1. Define Choice variables, Constants, and Goals

The first step in model formation is defining choice variables and right-hand side constants. The right — hand side constants are specified goal levels/values. It requires a careful analysis of the problem in order to identify all relevant variables that have some effect on the set of goals laid down by the business stakeholders/decision-makers.

2. Add deviational variables

Identify and set up deviational variables. These variables represent the possible deviations below(underachievement) or above the target value (overachievement).

3. Determine the priority

Priority associated with each goal should be neatly laid down. For e.g. –

Priority level P1, if most important should be laid down first, followed by Priority level P2 which is next important, and so on.

4. Formulate Constraints

A set of constraints should be formulated based on the relationships amongst choice variables and their relationships with the set of goals.

A constraint can be either a system constraint that may influence but is not directly related to goals or a goal constraint that are directly related to goals.

Each constraint equation is developed by adding deviational variables. If there are no deviational variables to add on, then a new constraint with a deviational variable is created.

5. Develop the objective function

To develop an objective function, first, the preemptive priority factors should be assigned to the deviational variables that are relevant for goal attainment. Second, weights must be assigned to deviational variables at the same priority levels. One important thing to note here is that goals at the same priority level must be commensurable.

Source : https://www.rosettatg.com/blogtoon/2018/3/12/what-are-you-optimizing-for

With this, I conclude on Part 1 of the write-up which strictly focuses on the model formulation for multi-objective optimization problems using goal programming.

In the second part, I will take it to next level wherein I will focus primarily on solving the objective functions to derive optimal solutions using techniques of Goal programming.

Hope you enjoyed this article.


Multi-Objective Optimization Problem using Goal Programming was originally published in Towards AI on Medium, where people are continuing the conversation by highlighting and responding to this story.

Published via Towards AI

Feedback ↓