3
$\begingroup$

In the simple case, with only two objectives, I would like to know if it is possible to answer a question like:

  • How many units of objective 1 do I need to reduce, in order to improve objective 2 by one unit? (Assuming the objectives are conflicting, and we have the pareto frontier)

To me, it kind of sounds like sensitivity analysis, but since it's about the objective function only, not including the solutions , I don't feel confident to say "sensitivity analysis on objective 1".

In this paper, the authors used regression to do so (paragraph above Figure 3), but it's not clear to me which type of regression (linear?)

Not limited to the two objectives case, I am asking if regression is a good way to answer the question listed, and if there are other methods.

$\endgroup$
4
  • 4
    $\begingroup$ If you have the Pareto frontier, then isn't its slope essentially the answer to your question? $\endgroup$
    – Max
    Apr 28, 2022 at 8:10
  • $\begingroup$ You have not mentioned whether the problem is discrete or continuous. When you say "we have the Pareto frontier", do you mean that you have all the bounding hyperplanes (continuous linear case), or all the extreme points (continuous case), or all the (finitely many) Pareto efficient points (discrete case), or something else? $\endgroup$
    – prubin
    Apr 28, 2022 at 15:47
  • $\begingroup$ @Max Probably in a linear problem, but I have a MIP. I should have mentioned that. $\endgroup$ Apr 29, 2022 at 3:16
  • $\begingroup$ @prubin It would be a discrete case. I should have given more emphasis to the paper mentioned because I have a similar situation, a DARP-related problem, and I would like to figure out how to choose weights that would balance both objectives across many instances. $\endgroup$ Apr 29, 2022 at 3:16

2 Answers 2

6
$\begingroup$

Understanding the Pareto frontier

In your question, you say that "we have the Pareto frontier." This makes your question difficult to parse, because the object that represents the tradeoff between competing objectives is the Pareto frontier.

Here is an example from the relevant Wikipedia page:

enter image description here

Each square in the picture represents a feasible solution $x$, and they are plotted in $f_2, f_1$ space. There are some points, like the one marked C, that are obviously inoptimal no matter how you appraise the relative importance of the two objectives, because point A has a better value in both objectives. (Here "better" means "lower": Wiki is assuming a minimization problem.) In other words, C is dominated by A.

Why your question cannot be answered by a single number

You asked,

How many units of objective 1 do I need to reduce, in order to improve objective 2 by one unit?

Examining the graph, we can see that the slope of the Pareto frontier between points A and B is about $-2/3$. In other words, to improve (lower) objective 2 by 1 unit, we need to sacrifice (increase) objective 1 by about 2/3 of a unit. In other words, the "tradeoff coefficient" at this location on the Pareto frontier is $z = 2/3$. ($z$ is not a standard symbol for this; I chose it arbitrarily.)

Your question suggests that you would like to know a single value of $z$ that describes the tradeoff for the whole optimization problem. But the graph above makes it clear that $z$ varies in different regions of the Pareto frontier. In the upper left corner, where $f_2$ is prioritized over $f_1$, we have $z \approx 2$, whereas it is closer to $z \approx 1/2$ as we move to the bottom right.

If it seems strange that your question can't be answered by a single value, consider the following question, which is analogous to yours:

How much does the function $f(x) = x^2$ increase when $x$ increases by one unit?

The answer depends on which $x$ you choose! If $x = 1$, the change in $f$ or slope is $2$; if $x = -5$, the slope is $-10$; in general, the slope is the derivative $f'(x) = 2x$.

Why "regression"

Nonetheless, you may wish to describe the average slope of the Pareto frontier in some region of interest. This is not technically difficult. For example, we can plug all the $f_2, f_1$ coordinates from the graph above into a linear regression, which will determine a straight line (i.e. a curve of constant slope) that approximates the Pareto frontier, and then report this line's slope.

But in an operational context, this is seldom the best approach. Presumably, there is some point along the Pareto frontier that represents the status quo. For example, if the decision variable is a production schedule, and $\bar x$ is the current production schedule, you could plot $f_1(\bar x)$ and $f_2(\bar x)$ onto the canvas above, identify the nearest point on the Pareto frontier, and compute the slope $z$ in that region. Now you can tell your boss, "Reducing customer wait times ($f_2$) by one minute relative to the current schedule will cost ($f_1$) us $z$ thousand dollars." If you had computed the average slope instead, you would not be able to make such a precise statement.

Discreteness

You mentioned in a comment that your problem is a discrete problem, an MIP. This doesn't make any practical difference in this context. While there are some continuous problems for which we can express the Pareto frontier in a parametric form, and therefore take derivatives and determine the slope exactly, in practice, the typical way to solve multi-objective optimization problems (even for continuous problems) is to maximize

$$(1 - t) f_1(x) + t f_2(x) \tag{1} \label{1}$$

for a variety of $t \in [0, 1]$, say $t = 0.0, 0.05, 0.10, \dots, 1.0$. Plotting $f_1(x)$ and $f_2(x)$ at each of the associated optima will give you a plot like this:

enter image description here

... which is just the Pareto frontier, and we can easily estimate the slope by computing it between two adjacent points, or get the average slope by running a linear regression.

The fact that you have an MIP matters only in that solving $\eqref{1}$ will require an MIP solver, and therefore take some (probably much) more time. So you might not be able to choose as many values of $t$. But the tradeoff analysis is completely blind to this step.

$\endgroup$
1
  • $\begingroup$ Thanks for the (complete) answer! It does answer my question about how to calculate trade-off and if regression is a good method. I am also curious about the case when we have many pareto frontiers (many instances) and we need to settle on a "good" t, but that's another question. $\endgroup$ May 16, 2022 at 3:29
2
$\begingroup$

When you say "How many units of objective 1 do I need to reduce", I suspect that you mean that you solved your optimization problem, and then you want to do some "post-optimal" analysis, i.e. you want to analyze the tradeoff between objective 1 and 2.

If this is the case, I would do the following. Suppose we start with this, where $f_1(x)$ and $f_2(x)$ are your objectives:

$$ \begin{align} \min . \quad& f_1(x) + f_2(x) \\ \text{s.t.}\quad& Ax \leq b \end{align} $$

After you solved it, I would then solve the following problem to answer your question:

$$ \begin{align} \min . \quad& f_1(x) + f_2(x) \\ \text{s.t.}\quad& Ax \leq b \\ & f_2(x) = f_2^*(x) - 1 \\ \end{align} $$

where "improvement" in my example means reducing (since this is a minimization problem). The value $f_2^*(x)$ is the optimal value calculated in the first optimization problem.

To then find the answer to your question, you calculate $f_1^{**}(x) - f_1^*(x)$, where $f_1^{**}(x)$ is the optimal objective function value of objective 1 in the second problem.

$\endgroup$
3
  • $\begingroup$ Thank you for you answer. Would that be a method to find the slope of the pareto frontier, like @Max said? I failed to mention before, but I have a MIP. I don't know if that would work for MIPs. $\endgroup$ Apr 29, 2022 at 3:19
  • 1
    $\begingroup$ Richard's answer only gives you the slope at one point along the Pareto frontier, namely at the point where $f_1$ and $f_2$ are given equal weight in the joint objective. If you set the objective as $f_1 + 5 f_2$ instead, for instance, you would get a different answer, and there is no reason to assume that one or the other is more or less valid. $\endgroup$
    – Max
    Apr 29, 2022 at 3:51
  • $\begingroup$ Correct. The problem is that mathematically the pareto frontier might be non-differentiable since you have a MIP. You could try and look at the dual values of the extra constraint, but if you want the exact pareto frontier (i.e. analytically), you have to use parametric programming (see e.g. sciencedirect.com/science/article/abs/pii/S0098135415003269) $\endgroup$
    – Richard
    Apr 29, 2022 at 7:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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