Working With Multiple Objective

Working With Multiple Objective

Of course, specifying a set of objectives is only the first step in solving a multi-objective optimization problem. The next step is to indicate how the objectives should be combined. As noted earlier, we support two approaches: blended and hierarchical.

Blended Objectives

A blending approach creates a single objective by taking a linear combination of your objectives. You specify the weight for each objective through the ObjNWeight attribute. Again, you use the ObjNumber parameter to modify or query the weight for a particular objective. The default weight for an objective is 1.0.

To give an example, if your model has two objectives, <span>$</span>1 + x + 2y<span>$</span> and <span>$</span>y
+ 2z<span>$</span>, and if you give weights of <span>$</span>-1<span>$</span> and <span>$</span>2<span>$</span> to them, respectively, then Gurobi would solve your model with a blended objective of <span>$</span>-1 \cdot (1 + x + 2y) + 2 \cdot (y + 2z) = -1 - x + 4z<span>$</span>.

You should avoid weights that are very large or very small. A very large weight (i.e., larger than <span>$</span>10^6<span>$</span>) may lead to very large objective coefficients, which can cause numerical difficulties. A very small weight (i.e., smaller than <span>$</span>1e-6<span>$</span>) may cause the contribution from that objective to the overall blended objective to be smaller than tolerances, which may lead to that objective being effectively ignored.

Hierarchical Objectives

A hierarchical or lexicographic approach assigns a priority to each objective, and optimizes for the objectives in decreasing priority order. At each step, it finds the best solution for the current objective, but only from among those that would not degrade the solution quality for higher-priority objectives. You specify the priority for each objective through the ObjNPriority attribute. Priorities are integral, not continuous. Larger values indicate higher priorities. The default priority for an objective is 0.

To give an example, if your model has two objectives, with priorities <span>$</span>10<span>$</span> and <span>$</span>5<span>$</span>, and the optimal solution for the first objective has value <span>$</span>100<span>$</span>, then the solver will find the solution that optimizes the second objective from among all solutions with objective <span>$</span>100<span>$</span> for the first objective.

By default, our hierarchical approach won't allow later objectives to degrade earlier objectives. This behavior can be relaxed through a pair of attributes: ObjNRelTol and ObjNAbsTol. By setting one of these for a particular objective, you can indicate that later objectives are allowed to degrade this objective by the specified relative or absolute amount, respectively. In our earlier example, if the optimal value for the first objective is <span>$</span>100<span>$</span>, and if we set ObjNAbsTol for this objective to <span>$</span>20<span>$</span>, then the second optimization step would find the best solution for the second objective from among all solutions with objective <span>$</span>120<span>$</span> or better for the first objective. Note that if you modify both tolerances, later optimizations would use the looser of the two values (i.e., the one that allows the larger degradation).

Combining Blended and Hierarchical Objectives

You can actually set both a weight and a priority for each objective. This allows you to combine the blended and hierarchical approaches. To understand how this works, we should first provide more detail on how hierarchical objectives are handled.

When you specify a different priority for each of <span>$</span>n<span>$</span> objectives, the solver performs <span>$</span>n<span>$</span> separate optimization steps. In each step, in decreasing priority order, it optimizes for the current objective, while imposing constraints that ensure that the quality of higher-priority objectives isn't degraded by more than the specified tolerances.

If you give the same priority to multiple objectives, then they will be handled in the same optimization step, resulting in fewer than <span>$</span>n<span>$</span> total steps for <span>$</span>n<span>$</span> objectives. More precisely, one optimization step is performed per distinct priority value, in order of decreasing priority, and all objectives with the same priority are blended together, using the weights for those objectives. This gives you quite a bit of flexibility when combining the blended and hierarchical approaches.

One subtle point when blending multiple objectives within a single level in a hierarchical approach relates to the handling of degradations from lower-priority levels. The objective degradation allowed after a blended optimization step is the maximum absolute and relative degradations allowed by each of the participating objectives. For example, if we have three objectives with ObjNPriority equal to <span>$</span>\{2, 2, 1\}<span>$</span>, and ObjNRelTol equal to <span>$</span>\{0.10, 0.05, 0.00\}<span>$</span> and ObjNAbsTol equal to <span>$</span>\{0,
1, 2\}<span>$</span>; and the best solution for the first priority objective is <span>$</span>10<span>$</span>; then the allowed degradation for the first priority objective is <span>$</span>\max\{10 \cdot 0.10, 10 \cdot 0.05, 0, 1\} = 1<span>$</span>.