16
$\begingroup$

The newer versions of Gurobi include a couple of built-in functionalities for multi-objective optimization: blended objectives and hierarchical (lexicographically ordered) objectives.

Suppose we wanted to minimize $2x + 3.5y + 7z$. Using the "blended" functionality by specifying weights for each objective, the relevant parts of the python code would be something like:

model.setParam('NumObj', 3)
model.SetObjectiveN(x, index = 0, weight = 2)
model.SetObjectiveN(y, index = 1, weight = 3.5)
model.SetObjectiveN(z, index = 2, weight = 7)
model.optimize()

On the other hand, if we wanted to do the same minimization by manually specifying a weighted-sum objective, the python code would look like:

model.setObjective(2*x + 3.5*y + 7*z)
model.optimize()

Q: It seems to me, based on the documentation available, that specifying "blended" objectives is no different from the manual weighted-sum approach. From an algorithmic/computational efficiency perspective, are there any possible benefits to using one approach over the other? Does Gurobi tackle the optimization differently if the objective is constructed in one way versus the other? Or are the differences purely "cosmetic"?

$\endgroup$
  • 1
    $\begingroup$ From what I read in the docs it seems indeed the same in your example but also allows for weighting whole (linear) expressions. Note that you also can combine blended mode with the hierarchical mode. Then expressions with the same priority are blended using their individual weights. $\endgroup$ – JakobS Jul 15 '19 at 6:55
  • $\begingroup$ @JakobS True. Still, in both of those situations, the programmer can simply create the weighted sums themselves as necessary without using the functionality. It would definitely be convenient to use the functionality in many cases if the programmer is managing many objectives when creating the model. I'm curious if there are some benefits beyond the ones you mentioned, where the solution speed/quality would be affected by using the functionality. $\endgroup$ – Dipayan Banerjee Jul 16 '19 at 0:14
  • 1
    $\begingroup$ I deleted my answer which had the wrong focus. Yet, I think the answer is fairly simple: For something as naive as a linear weighting of different terms it is unlikely that you benefit from anything beyond convenience - if that was the case we could benefit from changing other problems involving linear terms to blended evaluation. On the other hand you can seamlessly migrate from blended to hierarchical where the benefits of the internal representation are obvious. $\endgroup$ – CMichael Jul 17 '19 at 15:50
5
$\begingroup$

Q: It seems to me, based on the documentation available, that specifying "blended" objectives is no different from the manual weighted-sum approach? ...

It's two different explanations of the same way of specifying the same parameters.

In the prior section of the documentation titled: Multi-objective Attributes it says:

These are the attributes for setting and querying multiple objectives (refer to the "Multiple Objectives" section for additional information on multi-objective optimization).

Subsections

  • ObjN
  • ObjNCon
  • ObjNPriority
  • ObjNWeight $\Large{\color{red}{\Leftarrow\!\!\!\bbox{\small\text{ This is the parameter you asked about. See below.}}}}$
  • ObjNRelTol
  • ObjNAbsTol
  • ObjNVal
  • ObjNName
  • NumObj

The "Multiple Objectives" section (mentioned above) says:

" While typical optimization models have a single objective function, real-world optimization problems often have multiple, competing objectives. For example, in a production planning model, you may want to both maximize profits and minimize late orders, or in a workforce scheduling application, you may want to minimize the number of shifts that are short-staffed while also respecting worker's shift preferences.

The main challenge you face when working with multiple, competing objectives is deciding how to manage the trade-offs between them. Gurobi provides tools that simplify the task: Gurobi allows you to blend multiple objectives, to treat them hierarchically, or to combine the two approaches. In a blended approach, you optimize a weighted combination of the individual objectives. In a hierarchical or lexicographic approach, you set a priority for each objective, and optimize in priority order. When optimizing for one objective, you only consider solutions that would not degrade the objective values of higher-priority objectives. Gurobi allows you to enter and manage your objectives, to provide weights for a blended approach, or to set priorities for a hierarchical approach.

Subsections

From your first link:

"Blended Objectives

A blending approach creates a single objective by taking a linear combination of your objectives. You provide a weight for each objective as an argument to setObjectiveN. Alternatively, you can use the ObjNWeight attribute, together with ObjNumber. The default weight for an objective is 1.0.".

From the webpage: "AMPL-Gurobi Parameter Reference":

"feasrelax
    Whether to modify the problem into a feasibility relaxation problem:
    0 = no (default)
    1 = yes, minimizing the weighted sum of violations
    2 = yes, minimizing the weighted count of violations
    3 = yes, minimizing the sum of squared violations
    4-6 = same objective as 1-3, but also optimize the original objective, subject
    to the violation objective being minimized
 
    Weights are given by suffixes .lbpen and .ubpen on variables and .rhspen on constraints (when positive), else by keywords lbpen, ubpen, and rhspen, respectively (default values = 1). Weights ≤ 0 are treated as ∞, allowing no violation.".

You can specify pre-solve tactics, dual (many) solver approaches, and weights/methods for each. Some methods work better on different datasets, allowing something that's working to succeed in one thread and a poorly progressing solution in another thread to be terminated; allowing the best/easiest/fastest/worst choice to be preferred depending on what it to be optimized for.

The ObjNWeight webpage says:

Type:       double
Modifiable:   Yes
 
This attribute is used to query or modify the weight of objective $n$ when doing blended multi-objective optimization. You set $n$ using the ObjNumber parameter.

The default weight for an objective is 1.0.

The number of objectives in the model can be queried (or modified) using the NumObj attribute.

Please refer to the discussion of Multiple Objectives for more information on the use of alternative objectives.

For examples of how to query or modify attributes, refer to our Attribute Examples.".

 

Q: Does Gurobi tackle the optimization differently if the objective is constructed in one way versus the other?

Yes, see above, "Specifying Multiple Objectives", "Working With Multiple Objective" and "Additional Details"; which are previous and next links of the links above.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.