I already introduced various coding examples implementing multi-objective optimization. In these examples I implemented different strategies for searching a multi-objective optimum. One of these strategies was based on scalarizing multiple objectives into a single objective function using weights for each indivual objective function. In this article I want to provide a more comprehensive explanation on different kinds of scalarizing strategies.
In multi-objective optimization problems one is facing competing objectives. There is not a single standard method for how to solve multi-objective optimization problems. One popular approach, however, is scalarizing.
Overview of popular techniques
As I already mentioned, scalarizing techniques are applied to transform a multi-objective optimization problem in such a way that only a single objective function is optimized. I have found that there are many techniques for doing so. In this article I present three of them:
- Linear scalarization
- Epsilon-constraint method
- Sen`s programming
Scalarizing multiple objectives with linear scalarization
This method applies weighting factors to combine competing objective functions into a single objective function. Analysts have to set or monitor the weight values, as they represent the weight of the respective objective.
I best describe this approach with a mathematical formulation og the linearly scales objective function, as posted below:
Normally, I like to set the sum of weights to equal 100%. This makes it easier to view the relative weighting of the respective objectives. Please see my article on multi-obejctive optimization with PuLP in Python to view a demonstration of this approach.
Scalarizing multiple objectives with epsilon-constraint method
Epsilon-constraint models will convert the problem into a single-objective problem by keeping only one function as an objective function. The other functions are modelled as constraint functions. Each function should achieve its individual optima by some extent, as indicated by the value epsilon.
Again, I best describe this appraoch by posting the mathematical notation below:
When I apply this approach I usually solve for each objective separately first. Thereby I reveal the individual optima of each objective. Next, I construct the epsilo-constraint version of the problem. In the problem statement I set the model to the individual optima by a at least a defined extend.
I published an article on this blog demonstrating the implementation of this approach using PuLP in Python for multi-objective optimization.
Scalarizing multiple objectives with Sen`s programming
This approach normalizes each objective function by dividing through its absolute individual optima before summation into a single joint objective function. I illustrate this approach using mathematical notation. See below. Please note that in this examples obejctives 1 to r are maximization objectives, while objectives r+1 to s are minimization objectives.
Other popular approaches for scalarizing
Many supply chain analysts also apply a scalarizing technique presented by Wiezbicki, which you can read more about here: https://www.sciencedirect.com/science/article/pii/0270025582900380?via%3Dihub
Coding examples for (multi-objective) optimization
I have contributed a series of blog posts covering linear optimization in Python and R. Here is a list that will get you started in R and Python. I also included two examples including multi-objective optimization, namely linear scalarizing and the epsilon-constraint method. Here are some of my posts:
- Solving linear problem with fuzzy constraints by sampling beta with FuzzyLP in R
- Linear optimization with fuzzy constraints conducted in R with FuzzyLP
- Continuous linear optimization in PuLP (Python)
- Linear optimization in Python: Using SciPy for linear programming
- Gradient descent in R, for non-linear optimization (nloptr package)
- Solving linear transport problem with lp.transport in R, using lpSolve
- Constraint programming for work scheduling with Google OR-Tools
- Lean coding of simple linear optimization ortools models in Python
- Cost minimal production scheduling – solving the assignment problem with lpSolve in R
- Multi-objective linear optimization with weighted sub-problems, using PuLP in Python
- Multi-objective linear optimization with PuLP in Python
Data scientist focusing on simulation, optimization and modeling in R, SQL, VBA and Python