What is the difference between blended approach in Gurobi and linear scalarization method ?

[lahlou aziz]

Hi guys,

I would like to know when giving the same weight to an different objective functions in Gurobi have the same interpretation as the so called linear scalarization method ?

Could you elaborate a bit more on this ? Also, I am really confused regarding the combination of the blended and hierarchical approaches, I need to understand well this aspect as I am performing some experiments toward my paper so I would love to avoid mistakes and misunderstandings.

Thanks in advance for your insights and clarifications.

Regards,
Aziz

[Tobias Achterberg]

The blended approach is really simple; a user can do this easily himself. We added this
just for convenience.

If n objective functions all have the same priority, but (potentially different) weights
w1,...,wn, then a single optimization process is launched where the objective function is
set to

w1*c1 + ... + wn*cn

with ci being the coefficients of the different objective functions.

If you use the hierarchical approach, then every priority level gives rise to one
optimization process. The first is optimizing the primary objective function. The second
is then optimizing the secondary objective function, subject to a new constraint that the
primary objective must not degrade (too much) from the optimal solution value. For the
ternary objective, another constraint is added that also the secondary objective must not
degrade too much.

If you combine the two, then the obvious things happen. For example, consider objective
functions with the following weights:

objective priority weight
c1 10 1
c2 10 3
c3 10 8
c4 7 2
c5 7 3
c6 4 5
c7 4 1
c8 2 2

We have four different priority levels, so we will get four optimization processes. The
first will optimize for 1*c1x + 3*c2x + 8*c3x. Say, the optimal objective value is c123*.
Then, the second optimization process will optimize 2*c4x + 3*c5x with an additional
constraint

1*c1x + 3*c2x + 8*c3x <= c123* + eps (1)

(assuming minimization). The third optimization process will optimize 5*c6x + 1*c7 with
additional constraints (1) and

2*c4x + 3*c5x <= c45* + eps (2)

with c45* being the optimal objective value of the second level. Finally, the fourth
optimization process will optimize 2*c8x with constraints (1), (2), and

5*c6x + 1*c7x <= c67* + eps (3)

with c67* being the optimal objective value of the third level.


Regards,

Tobias

[lahlou aziz]

Hi Tobias,

Many thanks for such an explanation and time taken to give this amount of informations. It says all and clarified many things I did not figure out and grasp from the official documentation.

Regards,

Aziz

[vincent gao]

Hi Tobias,

I am working on a hierarchical programming program using Gurobi (and AMPL), and I found this post really helpful.

One quick question I have is if there is a way to prevent the primary objective from degenerating at all? In my test, it seems that the primary objective still degenerates even if I explicitly set the suffix objreltol and objabstol to 0 (let <primaryObjective>.objabstol := 0) in AMPL.

Many thanks,

[Tobias Achterberg]

If you set the tolerances to 0, then the primary objective should not degrade. BUT as all
other constraints, the constraint

cx <= c*

that says that the primary objective should not degrade is subject to the regular
feasibility tolerance (which is 1e-6 by default). Thus, even if you set the obj tolerances
to zero, this constraint can get violated a little bit, which means that the primary
objective degrades a little bit.

Regards,

Tobias

[wujian]

Hi Vincent,

  In my humble opinion, there is a bug in the AMPL driver of Gurobi regards to multiobj functionality.

  I translated the 'multiobj.py' example model into AMPL, see this: https://github.com/wujianjack/optimizationmodels/blob/master/ampl/multiobj.mod , however, to solve it with latest official Gurobi AMPL driver, it gave wrong solution compared to the Python model. I investigated the source code of AMPL driver of Gurobi and fixed the bug (maybe), not sure if you are faced with this issue.

Regards,

wujian

在 2017年12月6日星期三 UTC+8上午4:33:06，vincent gao写道：

[vincent gao]

Hi Wujian,

Many thanks for sharing your insights!

I think I might be facing the same issue. I tried to play around with different priority levels for my objectives with suffix objpriority, But AMPL still calls Gurobi to solve all objectives with the same priority level I think.

Would you mind sharing more details about the bug you discovered and how you fixed it?

Many thanks

[Robert Fourer]

This has been reported as an AMPL-Gurobi interface issue and further updates will be posted as needed.

Bob Fourer
AMPL Optimization Inc.
4...@ampl.com

=======

From: gur...@googlegroups.com [mailto:gur...@googlegroups.com] On Behalf Of wujian
Sent: Tuesday, December 5, 2017 8:45 PM
To: Gurobi Optimization
Subject: Re: [Gurobi] What is the difference between blended approach in Gurobi and linear scalarization method ?

In my humble opinion, there is a bug in the AMPL driver of Gurobi regards to multiobj functionality.
I translated the 'multiobj.py' example model into AMPL, see this: https://github.com/wujianjack/optimizationmodels/blob/master/ampl/multiobj.mod , however, to solve it with latest official Gurobi AMPL driver, it gave wrong solution compared to the Python model. I investigated the source code of AMPL driver of Gurobi and fixed the bug (maybe), not sure if you are faced with this issue.

--

---
You received this message because you are subscribed to the Google Groups "Gurobi Optimization" group.
To unsubscribe from this group and stop receiving emails from it, send an email to gurobi+un...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[wujian]

Hi Bob,

  Thanks for your interest again and waiting for reply, in fact, this is the second time I reported this issue to AMPL, the last time I asked the agent of AMPL in China on behalf of me to report it, but was told I was wrong :-(

Regards,

Wu Jian

在 2017年12月7日星期四 UTC+8上午12:19:17，Robert Fourer写道：

[wujian]

Hi Vincent,

  I reported this possible issue and my patch to AMPL yesterday and waiting for response.

Regards,

Wu Jian

在 2017年12月6日星期三 UTC+8下午2:11:43，vincent gao写道：