Multi Objective Decision Optimization
Introduction to multi objective concepts and methods. Some hints to start modeling and solving multi objective problems with Decision Optimization.
I will start explaining why multi objective situations happen so frequently, and then provide some examples on how to model the different main cases using the most frequently used modeling languages, Python docplex and OPL.
Some introduction
Let’s first talk about objectives. With Decision Optimization, a model is formulated to solve a problem.
In this model are defined:
- the decision variables, for which the algorithm should prescribe values,
- the constraints, representing combinations of variable values which are forbidden, i.e. a feasible solution has a set of values of decision variables that respect all constraints,
- the objective, representing the quality of a solution, i.e. an optimal solution should have the best value for the objective among all feasible solutions.
Objectives
Life is not mono objective. In your personal life, decisions are hard because there is not a single objective. Think about your diet. You want it to be healthy, but you want it to be tasty. This is a complex multi objective problem as both objectives are almost opposite.
The same happens with business. You want to minimize you stocking costs, but you want to avoid any possible disruption for any of your catalog items. You want to schedule some production to have a as high as possible throughput but you still want to have quality. You want your call center schedule to be economically optimal, but you also want it to be reasonable for employees and respect as much as possible their wishes. You want the hospital nurse planning to be covering as much as possible the different departments and skills needs, but also to be fair among all nurses.
Objective in the Simplex method
Mathematical Programming, because of the nature of linear programs, is naturally mono objective so many people think our engines cannot handle multiple objectives.
Indeed the simplex algorithm, which is at the core of most of Mathematical Programming engines, is relying on a matrix definition of the linear problem.
But, as with many other topics in Operations Research, what is true in theory is not necessary true in practice and the mathematical programming engines offer different ways to handle multiple objective problems.
Relations between different objectives
Let’s first understand how the different objectives can relate to each other.
In my examples above, we can separate two different situations.
On the one hand, there are situations where the different objectives can be compared with each other. For example, the cost of stocking one item in your warehouse can be expressed in dollars, and the cost of being out of stock may also be expressed in dollars (corresponding to lost sales). In these cases, it will be possible to blend the different objectives into a single one, using weights to allow different level of relative importance for the different objective elements.
On the other hand, there are situations where objectives are not directly comparable. The hospital planner may consider that the coverage of the demand is much more important than fairness among nurses. In these cases, a lexicographic order will be used, ordering all objectives elements in priority groups.
Lexicographic refers to the ordering of the words in a dictionary. Imagine a problem with two goals. For each goal, A is the best value and Z the worst one. With lexicographic criteria, AZ is definitely better than BA, just like in a dictionary AZ is before BA, while with most choices of weights, BA might be better than AZ.
This CPLEX Optimization Studio documentation introduces these two alternatives.
How to model multiple objectives
Let’s now talk about how to model these different types of multiple objective problem with Decision Optimization. I will only cover the 2 recommended modelling languages which are Python docplex and OPL. You can also use lower lever API and create multi objective programs directly with CPLEX.
Simple objectives
An objective is defined as the maximization or minimization of an expression of the decision variables.
In Python docplex:
myCost = mdl.sum( costs[i]*decisions[i] for i in indices)
mdl.add_kpi(myCost, 'myCost')mdl.minimize( myCost )
Note that adding the expression as a KPI is optional. It allows a better monitoring during the search and a more readable report output at the end.
In OPL:
dexpr float myCost = sum(i in indices) costs[i]*decisions[i];minimze myCost;
Note that in DO for Cloud Pak for Data, all dexpr created after the constraints block will be considered as KPI.
Weighted sum
To optimize a set of multiple objectives which can be compared, the most common method is to use a weighted sum of these objectives. If some objectives are to be maximized and others to be minimized, then some weights will be negative.
In Python docplex:
myCost1 = mdl.sum( costs1[i]*decisions1[i] for i in indices1)
mdl.add_kpi(myCost1, 'myCost1')myCost2 = mdl.sum( costs2[i]*decisions2[i] for i in indices2)
mdl.add_kpi(myCost2, 'myCost2')mdl.minimize( weight1*myCost1 + weight2*myCost2 )
A realistic example is used in my Network Design post (all weights are the same as all costs are in dollars):
variablePlantCost = mdl.sum( df_productionData.varPlantCost[pl, pr] * shipPlantToDC[pl, pr, dc]
for pl in plants for pr in products for dc in distributionCenters)
mdl.add_kpi(variablePlantCost, 'variablePlantCost')inboundTransportationCost = mdl.sum( df_inboundData.unitCost[pl, dc]*shipPlantToDC[pl, pr, dc]
for pl in plants for pr in products for dc in distributionCenters)
mdl.add_kpi(inboundTransportationCost, 'inboundTransportationCost')outboundTransportationCost = mdl.sum( shipDCCost[dc] for dc in distributionCenters)
mdl.add_kpi(outboundTransportationCost, 'outboundTransportationCost')fixedDistributionCenterCost = mdl.sum( df_distributionCenters.fixedCost[d] * openDC[d] for d in distributionCenters);
mdl.add_kpi(fixedDistributionCenterCost, 'fixedDistributionCenterCost');variableDistributionCenterCost = mdl.sum ( storeDCCost[dc] for dc in distributionCenters)
mdl.add_kpi(variableDistributionCenterCost, 'variableDistributionCenterCost');mdl.minimize( variablePlantCost + inboundTransportationCost +
outboundTransportationCost + variableDistributionCenterCost +
fixedDistributionCenterCost )
In OPL:
dexpr float myCost1 = sum(i in indices1) costs1[i]*decisions1[i];
dexpr float myCost2 = sum(i in indices2) costs2[i]*decisions2[i];minimize weight1*myCost1 + weight2*myCost2;
A realistic example would be as follow:
dexpr float emptySpacePenalty
= sum(s in Shelves) emptySpaceOnShelfVar[s]; dexpr float shortagePenalty
= sum(s in SKUs) unitsShortageVar[s]; dexpr float rectangularityPenalty
= sum(<g,s> in RectangularGroupShelves)
(rectShapeLeftSlack[<g,s>] + rectShapeRtSlack[<g,s>]); dexpr float squarenessPenalty
= sum(g in SquareGroups) squareShapeSlack[g]; dexpr float avgDisplayPricePenalty
= minAvgTargetPriceSlack + maxAvgTargetPriceSlack;
maximize Weight.expectedSales * expectedSales
- Weight.emptySpacePenalty * emptySpacePenalty
- Weight.shortagePenalty * shortagePenalty
- Weight.rectangularityPenalty * rectangularityPenalty
- Weight.squarenessPenalty * squarenessPenalty
- Weight.avgDisplayPricePenalty * avgDisplayPricePenalty;
Lexicographic
When the different objectives cannot be directly compared, then you will want to optimize the first one and then optimize the second one while ensuring the solution will still have the same value for the first objective.
This is what is called lexicographic objective, and we offer syntax to easily add such objective to the model.
In Python docplex, you can use:
myCost1 = mdl.sum( costs1[i]*decisions1[i] for i in indices1)
mdl.add_kpi(myCost1, 'myCost1')myCost2 = mdl.sum( costs2[i]*decisions2[i] for i in indices2)
mdl.add_kpi(myCost2, 'myCost2')model.minimize_static_lex([myCost1, myCost2])
In OPL, the staticLex function can be used:
dexpr float myCost1 = sum(i in indices1) costs1[i]*decisions1[i];
dexpr float myCost2 = sum(i in indices2) costs2[i]*decisions2[i];minimize staticLex(myCost1, myCost2);
See this complete documentation.
Combination
Note that it is possible to combine lexicographic and weights objective: all objectives at the same level of priority being blended together.
In docplex, use the method set_multi_objective. See for example its use for the now well known Zoo, Buses and Kids example.
In OPL, staticLexFull is also available which also includes parameters to control the allowed tolerances.
For example:
dexpr float kpis[i in 1..4] = (i==1)?a:((i==2)?b:((i==3)?c:d));float weights[i in 1..4] = 1;
int priorities[1..4] = [1,2,3,3];
float abstol[i in 1..4] = 0.001;
float reltol[i in 1..4] = 0.001; minimize staticLexFull(kpis, weights, priorities, abstol, reltol);
As mentioned in the documentation, abstolis an array of floats to define the absolute tolerances, and reltolis an array of floats to define the relative tolerances.
You might want to look at this more complete nurses example of multiple objective with docplex.
Objective representations
When there is only one numerical objective, it is easy to represent different solutions and compare them, using a chart.
When several non comparable objectives are taken into account, this does not work any more. Several approaches exist to represent such objectives, for example using spider charts. This is something that is very easy to do in our Decision Optimization experiment visualizations.
More:
Using multiple objectives is a first step which in general opens other questions.
Multiple equivalent optimal solutions — It is possible, when using multiple objectives blended into a weighted sum that the business user questions the provided optimal solution. While the algorithm is providing an optimal solution, he would prefer some other one, where the overall objective value is the same, but each individual objective is different. This is already the case with unique objective that several equivalent optimal solutions may exist, but multiple objectives will make it more frequent.
Multiple non optimal solutions — Even if the business user has ordered or weighted their objectives, they will almost always wonder what would happen if other weights or orders had been considered, and they will want to see different solutions with different combinations of almost equivalent objectives.
This is something quite simple to do with scenarios in Decision Optimization experiments in Cloud Pak for Data. Multiple scenarios can be generated and solved with different combinations of objectives (different weights or different groups).
Pareto Frontier — Finally, when we talk about multiple objective optimization, we need to talk about Pareto frontier. A solution is Pareto optimal if none of the objective can be improved without deteriorating one of the others. There are multiple ways to generate solutions on the Pareto frontier, which can be implemented using the Decision Optimization Client and experiment scenarios.
Conclusions
All real life problems involve multiple competing objectives and in this post, I have introduced different techniques and APIs that can be used to model these multiple objectives with Decision Optimization.
For more stories about AI and DO, follow me on Medium, Twitter or LinkedIn.
You might also look at our IBM DO main landing pages: https://www.ibm.com/products/ilog-cplex-optimization-studio
https://www.ibm.com/analytics/decision-optimization
