Re: How to evaluate the hardness of a Multiobjective Optimization problem?

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

saisai <jing.ai@xxxxxxxxx> wrote:
> Is it the concept of NP-complete still applied on the MOP
> (Multiobjective Optimization)?
>
> I do not know how to decribe decision version of the Multiobjective
> Optimization problem even if we have two objectives say, A and B.
>
> Could you give me an example?
>
> Since a MOP can be usually formulated as an Integer Programming, it is
> at least NP-hard, right?

No. If you can prove that Integer Programming can be reduced
to MOP, then MOP is at least NP-Hard.
For example, "Non-linear Integer Programming" is NP-Hard
because "Integer Programming" is a simplified version
and can be trivially reduced to Non-linear Integer Programming.

> Thanks for any advice!

- --
PaulLiu(劉穎駿)
E-mail address:PaulLiu.bbs@xxxxxxxxxxxxxxxxxxx
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.5 (GNU/Linux)

iD8DBQFCZjdKoQj7xTSiaUYRAqjgAKCSNslQ8WEnwiKwwqT5mhjlCcwg9ACfQQm2
SyaQNyj+TleDrKC0av4USUY=
=b7Wg
-----END PGP SIGNATURE-----
.