1
$\begingroup$

I have fairly standard linear optimization model with two objectives \begin{align*} \text{max}\, (f_1 &= 4x_1+5 x_2\,,\,f_2 = 1x_1 + 0x_2 ) \\ \text{subject to}& \\ 1x_1 + 1x_2 &\leq 200\\ 1.25x_1 + 0.75x_2 &\leq 200\\ 1x_2 &\leq 150\\ x_1,x_2 &\geq 0 \;\text{and} \;x_1,x_2\in \mathbb{Z}^+ \end{align*} If I use goal attainment method with normalized objective function $$f(x)=\sum\limits_{i=1}^2 \left(\frac{f_i^*(x)-f_i(x)}{f_i^*(x)}\right)^p$$ where $f_i^*(x)=(950,160)$ is the optimal solutions for $f_1,f_2$ and for $p=1,2$. Does this problem reduce to single objective optimization? \begin{align*} \text{min}\, \sum\limits_{i=1}^2 &\left(\frac{f_i^*(x)-f_i(x)}{f_i^*(x)}\right)^{1 \,\text{and}\, 2} \\ \text{subject to}& \\ 1x_1 + 1x_2 &\leq 200\\ 1.25x_1 + 0.75x_2 &\leq 200\\ 1x_2 &\leq 150\\ x_1,x_2 &\geq 0 \;\text{and} \;x_1,x_2\in \mathbb{Z}^+ \end{align*}

If I plug these into Gurobi I get $p=1 \to \mathbf{x} = (160,0)$ and $p=2 \to \mathbf{x}=(136,40)$. The second answer seems reasonable, but $p=1$ doesn't make that much sense. Is this the correct way to use normalized objective functions or am I missing something? Is Gurobi even suitable for such optimization problem?

$\endgroup$
2
+50
$\begingroup$

I get different the same results with Gurobi (with $x_1, x_2$ continuous):

----     64 PARAMETER report  

                         f1          f2          x1          x2         obj

max f1              950.000      50.000      50.000     150.000
max f2              640.000     160.000     160.000
utopia              950.000     160.000
min linear dist     640.000     160.000     160.000                   0.326
min quadr dist      747.735     135.138     135.138      41.437       0.069

When I plot these results (in the $f$ space) I see:

enter image description here

The blue line is the efficient frontier (i.e. the best $f_2$ for a given $f_1$).

When we require integer values for $x_1, x_2$ the quadratic solution changes a little bit:

----     65 PARAMETER report  

                         f1          f2          x1          x2         obj

max f1              950.000      50.000      50.000     150.000
max f2              640.000     160.000     160.000
utopia              950.000     160.000
min linear dist     640.000     160.000     160.000                   0.326
min quadr dist      744.000     136.000     136.000      40.000       0.070 (corrected)

No picture for this case as the frontier is now no longer a nice line.

The models are simply:

enter image description here

$\endgroup$
  • $\begingroup$ Did you use the normalized function? This one: \begin{align*} \text{min}\, \sum\limits_{i=1}^2 &\left(\frac{f_i^*(x)-f_i(x)}{f_i^*(x)}\right)^{1 \,\text{and}\, 2} \\ \text{subject to}& \\ 1x_1 + 1x_2 &\leq 200\\ 1.25x_1 + 0.75x_2 &\leq 200\\ 1x_2 &\leq 150\\ x_1,x_2 &\geq 0 \end{align*} $\endgroup$ – ELEC Jan 13 '16 at 17:00
  • $\begingroup$ Isn't those the same results as I got? min linear dist $(f_1,f_2) = (640,160)$ corresponds to $\mathbf{x} = (160,0)$ and min quadric dist $(f_1,f_2)=(747.735,135.138)$ corresponds in integer domain to $\mathbf{x}=(136,40)$ right? By the way, what programming language do you use Gurobi with? I didn't know you can get efficiency frontier as a callback!! $\endgroup$ – ELEC Jan 13 '16 at 17:08
  • $\begingroup$ Yes. E.g. $(950-640)/950+(160-160)/160=0.3263$ $\endgroup$ – Erwin Kalvelagen Jan 13 '16 at 17:08
  • $\begingroup$ Sorry, I missed you reported the x's. I looked at the f's. So we are in agreement. I used GAMS. No need for a callback. Just a loop. $\endgroup$ – Erwin Kalvelagen Jan 13 '16 at 17:10
  • $\begingroup$ Sorry. I forgot to add $x_1,x_2 \geq 0 \;\text{and} \;x_1,x_2\in \mathbb{Z}^+$ into the second model! Gurobi allows you to do goal programming. Could you post the code you used to attain those results and ill accept the answer :)? $\endgroup$ – ELEC Jan 13 '16 at 17:11

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.