Real life problems very often have multiple dimensions along which a solution is measured (Key Performance Indicators, or KPI). In routing problems, tradeoffs have to be found between the cost of a route and the time it takes. In plant planning, it may be possible to produce more, or for a lower cost, if the deadlines for some orders are relaxed. In personnel scheduling, meeting the demands in personels having specific skills may have to be balanced with some fairness goals.
Some of these KPIs may be compared by expressing all of them in a single unit (e.g. money). It is then easy to blend all the KPIs together as a single objective, and the optimal solution will be one that minimizes the sum of all the values of the KPIs. This is easy to implement in the CPLEX engine of IBM ILOG CPLEX Optimization Studio. But CPLEX did not offer support to facilitate the modeling of KPI blending.
In some other cases, the KPIs can’t be compared: some KPIs are absolutely more important than others: there is a well defined hierarchy between the KPIs, and any improvement in one KPI is worth any degradation in lower priority KPIs. This can be approximated using very large or very small coefficients in the objective. But the large spread of these coefficients may create numerical issues.
With CPLEX 12.9, you can define multiple objectives for a single problem, and combine them as a hierarchy, through blending, or with combinations of both. Here are the attributes that can be applied to each sub-objective:
- Priority: an integer, default 0.
Defines the order in which KPIs will be dealt with. If several sub-objectives have the same priority, they are blended together. - Weight: a float, default 1.0.
Applied to the expression of the sub-objective. Useful when blending, or to reverse the optimization direction of a sub-objective with respect to the others. - Absolute and relative tolerances: floats, default 0.0.
Used when there are several priorities. For a MIP model, they define the range over which the KPI may be degraded to accommodate for better optimal values of lower-priority KPIs.
Here’s an example of a trivial LP file that shows how this will work:
Maximize multi-objectives first: abstol=2 x1 second: priority=-1 x2 Subject to x1 + x2 = 10 General x1 x2 End
The log for this model will look like this:
$ cplex –c "read 1.lp" "opt" "display solution variables *"
[...]
Multi-objective solve log . . .
Index Priority Blend Objective
1 0 1 1.0000000000e+01
2 -1 1 2.0000000000e+00
Multi-objective optimal
[...]
CPLEX> Incumbent solution
Variable Name Solution Value
x1 8.000000
X2 2.000000
All other variables matching '*' are 0.
This shows that the two objectives were solved one after the other. First x1 (it has the highest priority, 0), then x2. The optimal value for x1 is 10. Then the tolerance for x1 is applied, such that this variable is increased by at most 2 units during the next iteration. The second sub-objective is solved, getting a value of 2.
There are two main benefits to using multiobjective modeling:
- You can very easily change the order of sub-objectives, their weights and their tolerances. This facilitates the exploration of the various tradeoffs in the decisions that need to be made.
- You can avoid large spreads of coefficients when dealing with non-comparable objectives, and avoid some of the associated numerical issues that may make the problem harder to solve.
You will find more information about multiobjective in CPLEX in these slides, and in the release notes for IBM ILOG CPLEX Optimization Studio 12.9.
Commercial users can download COS 12.9 from Passport Advantage. Students and teachers can download it through the Academic Initiative program, and everybody can get a trial version.
Learn more about IBM ILOG CPLEX Optimization Studio by visiting our product page.
The post Multiobjective optimization for LP and MIP in CPLEX appeared first on IBM Decision Optimization: on Cloud, for Bluemix….