# Does the weighted sum approach find all pareto-optimal solutions in MILP

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.

• 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. Oct 9 '20 at 16:09
• 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"? Oct 12 '20 at 8:10
• 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. Oct 12 '20 at 14:56

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: 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.

• 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 Oct 9 '20 at 14:18
• 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.
– Sune
Oct 9 '20 at 15:51
• Thanks Sune for your answer and effort. Still I do not understand why it is an disadvantage when not being able to find the lower red point. For me this solution is dominated and I do not need it at all. Oct 12 '20 at 8:13
• 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.
– Sune
Oct 12 '20 at 9:05
• 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.
– Sune
Oct 12 '20 at 18:11