4
$\begingroup$

I have a bi-objective MILP (Mixed Integer Linear Programming) problem, where I call the two objective functions as Obj1 and Obj2.

I would like to simultaneously maximize both of them via the Augmented Epsilon-Constraint Method. It will generate a set of Pareto-optimal solutions (called "Pareto Front"), where each of them represents a trade-off between the two objectives.

My question is:

If Obj1 and Obj2 (which are conflicting) represent a special case where, for example:

Obj1 = x1 + x2 + x3
Obj2 = - (x1 + x2 + x3) + (x4 + x5 + x6)

so, where Obj2 is equal to the reversed version of Obj1, plus some other terms,

or, if Obj1 and Obj2 represent even a more special case where Obj2 is equal to Obj1 multiplied by -1, such as:

Obj1 = x1 + x2 + x3
Obj2 = - (x1 + x2 + x3)

So, in both cases, the two objectives are linearly dependent.

Are these special cases not recommended or problematic (for some reasons which come from Operational Research theory) to be solved as a bi-objective MILP via the Augmented Epsilon-Constraint Method, or are they ok?

PS: In the examples above, for a sake of simplicity, I used two objectives made up of the sum of few variables, while in my case each of them is made up by the sum of many (thousands) terms.

$\endgroup$
5
$\begingroup$

Your last example, is certainly not that interesting. Let $f_1(x)$ and $f_2(x)$ abe the objective functions. From multi-objective optimization theory it is well known that if we use strictly positive weights for the objectives and solve the corresponding weighted sum scalarization, any optimal solution is efficient. In this case, we choose weight vector $\lambda=(\tfrac{1}{2},\tfrac{1}{2})$ and get the objective function $f_\lambda(x)=\tfrac{1}{2}(f_1(x)+f_2(x))=0$ as $f_2(x)=-f_1(x)$. Hence, any feasible solution is efficient which is not very interesting.

$\endgroup$
1
  • $\begingroup$ Ok, thank you, all clear. Could you say something about the first example too? $\endgroup$
    – rainbow
    Sep 29 at 12:48

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.