Research articles on Multi-Objective Non-Linear Programming (MONLP)

Question

I'm looking for papers dealing with multi-objective non-linear programming which could help me implement an algorithm to solve my problem.

My problem is :

Maximize $f(x) = c \cdot x$, while minimizing $g(x) = r \cdot x$, where $\cdot$ is the scalar product.

Constrained by $h_1(x) = \frac{v \cdot x}{p \cdot x} \geq 0.5$ and $h_2(x) = b \cdot x = B$

Given that $b, c, p, r, v \in (\mathbb{N}^*)^n, B \in \mathbb{R}_+^*, x \in [0, 1]^n$

For me, n will be in the order of 1000.

I know there is not a unique solution so I'm looking for the set of Pareto optimal solutions, therefore I am not interested by scalarizing. I could use interactive methods though.

Any help on the subject will be appreciated.

Answer 1

In Gandibleux, X. (Ed.). (2006). Multiple criteria optimization: state of the art annotated bibliographic surveys (Vol. 52). Springer Science & Business Media., I found in chapter 5 many interactive nonlinear multiobjective procedures explained. According to Kaisa Miettinen, none is better than another and they all have their pros and cons.

We can cite :

• Interactive Surrogate Worth Trade-Off Method [1]
• Geoffrion-Dyer-Feinberg Method [2]
• Tchebycheff Method [3]
• Step Method [4]
• Reference Point Method [5]
• GUESS Method [6]
• Satisficing Trade-Off Method [7]
• Light Beam Search [8]
• Reference Direction Approach [9]
• Reference Direction Method [10]

• NIMBUS Method [11]

  [1]: V. Chankong and Y. Y. Haimes. Multiobjective Decision Making Theory and Methodology. Elsevier Science Publishing Co., New York, 1983

  [2]: A. M. Geoffrion, J. S. Dyer, and A. Feinberg. An interactive approach for multi-criterion optimization, with an application to the operation of an academic department. Management Science, 19:357–368, 1972

  [3]: R. E. Steuer. The Tchebycheff procedure of interactive multiple objective programming. In B. Karpak and S. Zionts, editors, Multiple Criteria Decision Making and Risk Analysis Using Microcomputers, pages 235–249. Springer-Verlag, Berlin, Heidelberg, 1989.

  [4]: R. Benayoun, J. de Montgolfier, J. Tergny, and O. Laritchev. Lin- ear programming with multiple objective functions: Step method (STEM). Mathematical Programming, 1:366–375, 1971

  [5]: A. P. Wierzbicki. The use of reference objectives in multiobjec- tive optimization. In G. Fandel and T. Gal, editors, Multiple Cri- teria Decision Making Theory and Applications, pages 468–486. Springer-Verlag, Berlin, Heidelberg, 1980

  [6]: J. T. Buchanan. A naïve approach for solving MCDM problems: The GUESS method. Journal of the Operational Research Society, 48:202–206, 1997.

  [7]: H. Nakayama. Aspiration level approach to interactive multi- objective programming and its applications. In P. M. Pardalos, Y. Siskos, and C. Zopounidis, editors, Advances in Multicriteria Analysis, pages 147–174. Kluwer Academic Publishers, Dordrecht, 1995

  [8]: A. Jaszkiewicz The light beam search – outrank- ing based interactive procedure for multiple-objective mathemati- cal programming. In P. M. Pardalos, Y. Siskos, and C. Zopounidis, editors, Advances in Multicriteria Analysis, pages 129–146. Kluwer Academic Publishers, Dordrecht, 1995.

  [9]: P. Korhonen. Reference direction approach to multiple objec- tive linear programming: Historical overview. In M. H. Karwan, J. Spronk, and J. Wallenius, editors, Essays in Decision Making: A Volume in Honour of Stanley Zionts, pages 74–92. Springer- Verlag, Berlin, Heidelberg, 1997

  [10]: S. C. Narula, L. Kirilov, and V. Vassilev. An interactive algorithm for solving multiple objective nonlinear programming problems. In G. H. Tzeng, H. F. Wand, U. P. Wen, and P. L. Yu, editors, Multi- ple Criteria Decision Making – Proceedings of the Tenth Interna- tional Conference: Expand and Enrich the Domains of Thinking and Application, pages 119–127. Springer-Verlag, New York, 1994

  [11]: K. Miettinen. Nonlinear Multiobjective Optimization. Kluwer Aca- demic Publishers, Boston, 1999

Answer 2

I recently read a paper where someone was solving a nonlinear problem with binary variables and multiple objectives, looking for the Pareto optimal solutions. They used a genetic algorithm (NSGA-II) that seems appropriate, with the caveat that the solutions it gets are not guaranteed to be Pareto optimal, though they should at least be close. (I think the paper argues that the GA's population converges to the Pareto frontier.) It might be worth a look, if you're okay with using a metaheuristic. Here's the citation:

Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and T. Meyarivan (2002). "A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II". IEEE Transactions on Evolutionary Computation, Vol. 6, No. 2 (April), 182-197.