6
$\begingroup$

I use the weighted sum approach for a multiobjective optimization problem that is formulated as a MILP. This means that the objective function is linear. I read quite often that the weighted sum approach can't find certain pareto-optimal solutions in case of non-convex objective spaces (see for example slide 12 in this presentation https://engineering.purdue.edu/~sudhoff/ee630/Lecture09.pdf).

Now, having a MILP problem, can I deduce that basically the weighted sum approach can find all pareto optimal solutions if I just vary the weights? Of course the number of pareto-optimal solutions might be infinite, but I'd like to know whether there is the risk of missing some areas of the pareto-front. My gut feeling is that in a MILP the weighted sum approach can in fact find all pareto-optimal solutions.

Can anyone tell me more about this issue? I'd really appreciate every comment.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ I agree with @Sune's answer below, and I would also add: Don't get too freaked out about the points that the weighting method fails to find. For most MILPs (at least in my experience) there are a lot of non-dominated solutions, and the weighting method will find most of them. You might miss a few here and there "in the corners", but unless there's a particular reason you need all of the solutions, you're not losing a lot of information by ignoring the ones missed by the weighting method. $\endgroup$
    – LarrySnyder610
    Commented Oct 9, 2020 at 16:09
  • $\begingroup$ Thanks LarrySnyder for your answer. Do you know any (scietific) source or a website that underlines what you said "For most MILPs (at least in my experience) there are a lot of non-dominated solutions, and the weighting method will find most of them"? $\endgroup$
    – PeterBe
    Commented Oct 12, 2020 at 8:10
  • $\begingroup$ I don't know of any scientific evidence that supports my claim -- it was only my own anecdotal experience. But, for example, if you look at Figure 3 in this paper (by Snyder and Daskin 2005) you'll see a tradeoff curve with a ton of points. This was generated by the weighting method. If the method missed any points, they're hiding in the little gaps between those points and (I would argue) not likely to be particularly different or better than the points that the method did find. $\endgroup$
    – LarrySnyder610
    Commented Oct 12, 2020 at 14:56

1 Answer 1

Reset to default
4
$\begingroup$

No. You cannot be sure to find all Pareto optimal solutions to a MILP using the weighted sum approach. You are not even guaranteed to find all non-dominated outcomes. You are only guaranteed to be able to generate the supported non-dominated solutions. All the unsupported non-dominated solutions cannot be found using the weighted sum approach (without adding additional constraints). This is all due to the fact that it is not enough that the objective functions are convex, also the decision space needs to be convex for the weighted sum approach to guarantee all non-dominated outcomes.

Consider the following small bi-objective MILP example: \begin{align} \min\ & 4 + 2x_1+x_2+\frac{1}{2}y\\ \min\ & 2+x_1+2x_2+3y\\ \mbox{s.t.:}\ & x_1+x_2+y\geq 2\\ \ & x_1,x_2\geq 0\\ \ & y\in\{0,1\} \end{align} The non-dominate solutions can be illustrated as follows: Non-dominated frontier

The red line (solid and dotted) is the efficient front for $y=1$ and the blue solid line is the efficient front for $y=0$. Hence, the set of non-dominated outcomes is given by the union of the two solid lines. However, it is only the top left red dot and everything one the blue line you can find using the weighted sum scalarization. You can find the top red point using weights $(0.9,0.1)$, the middel blue point using weights $(0.6,0.4)$, and the lower right blue point using weights $(0.1,0.9)$.

Thus, you cannot generate the entire set of non-dominated outcomes for MILP problems in general using the weighted sum scalarization.

Improve this answer
$\endgroup$
14
  • $\begingroup$ Thanks Sune for your answer. I have difficulties understand it and I have follow up questions. 1)What are supported and unsupported solutions (never heard about this)? 2) Why is the lower red point pareto-efficient? The upper blue point has better objective values and (pareto) dominates it. So there is no need of finding it. The weighted sum approach does not need to find it because it is not pareto-efficient. Thus the weighted sum approach in your example can in fact find all pareto-efficient solutions as far as I understood $\endgroup$
    – PeterBe
    Commented Oct 9, 2020 at 14:18
  • $\begingroup$ 1) Supported solutions are those solutions that produce outcome vectors lying on the boundary of the convex hull of the set of non-dominated outcomes. That is, loosely speaking, those that maps to the lower envelope of the feasible space in outcome space. 2) the lower red point is non dominated for the sub problem where $y=1$. But it is not non-dominated for the MILP. However, everything on the solid red line is non-dominated and cannot be found using a weighted sum approach. $\endgroup$
    – Sune
    Commented Oct 9, 2020 at 15:51
  • 1
    $\begingroup$ It is not the lower red point that is the problem. It is all the points on the solid red line! Those points on the solid red line are non-dominated and they are unsupported. Thus, you cannot find them using the weighted sum approach. The only points you can find using a weighted sum approach is the two blue points, the points on the line between them, and the upper left red point. But, you cannot access the points on the solid red line using a weighted sum approach. $\endgroup$
    – Sune
    Commented Oct 12, 2020 at 9:05
  • 1
    $\begingroup$ If indeed there is a solution, which optimizes both objectives simultaneously then that solution is certainly efficient, and it is also the only efficient solution (the argument is simple using contradiction). Given that is is the only efficient solution, it is also supported and can thus be found using the weighted sum approach. $\endgroup$
    – Sune
    Commented Oct 12, 2020 at 18:11
  • 1
    $\begingroup$ Hi @PeterBe like with everything "multi-objective"-flavored I would look in Ehrgott's book. In the chapter on the weighted sum method, there is at least one example showing that non-convex problems cannot necessarily be solved using weighted sum. If you don't have the book, feel free to cite this answer 😉 $\endgroup$
    – Sune
    Commented Sep 1, 2022 at 11:25

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.