2
$\begingroup$

I am trying to solve the multi-objective function of my linear program. Are there another approaches other than the weighted sum approximation?

$\endgroup$
2
  • 1
    $\begingroup$ Welcome to OR.SE. there are many other methods like eps. constraints, goal programming, etc, to do that. If you are interested in, please, search for multi-objective decision making (MODM) by googling. :) $\endgroup$ – A.Omidi Jan 26 at 12:39
  • 1
    $\begingroup$ Can you order your objectives by decreasing importance ? If so you can checkout the lexicographic method. $\endgroup$ – Kuifje Jan 26 at 15:44
4
$\begingroup$

Yes. There are plenty of other approaches to handle multiple objectives. First of all, you need to figure out, what you consider an optimal solution (set) to your multi objective optimization problem. To name a few notions of optimality you might consider

  1. Pareto optimality
  2. Lexicographic optimality (as @Kuifje suggests in a comment to the question)
  3. Max-ordering optimality
  4. Combinations of some of the above

Next, you need to figure out a way to actually achieve an optimal solution (set). Here you also have quite a toolbox to choose from. I am most familiar with the methodology developed for finding the set of non-dominated outcome vectors (the image of the set of Pareto optimal solutions). I your problem is in fact a multi-objective linear program (MOLP) (no integer constrained variables) the following methods can be used to generate all non-dominated outcome vectors to your MOLP

  1. The perpendicular search method (a simple search strategy based on weighted sum scalarizations). This method is very easy to implement for two objectives, and not so easy to implement for more than two. A method for using this dichotomic search when having more than two objectives is described in this paper by A. Przybylski, X. Gandibleux, and M. Ehrgott.
  2. The $\varepsilon$-constraint method
  3. The weighted $\varepsilon$-method
  4. Benson's method. Details of a primal-dual version is described in this paper by A. Löhne and B. Weißing. The algorithm is implemented in BENSOLVE.

Generally, I would advice you to study chapter 2, 3, 4, and 5 in Multicriteria Optimization by Matthias Ehrgott, 2nd edition. It gives a thorough and easy to follow indtroduction to the different optimality concepts and to some of the methods listed above.

$\endgroup$
1
  • $\begingroup$ Thank you, that's very helpful. $\endgroup$ – Lolla Feb 5 at 9:50
2
$\begingroup$

To Sune's list, I'll add goal programming, in which you set targets for your objectives (possibly more than one target for a single objective), prioritize them, then minimize unfavorable deviations from the target in priority order.

$\endgroup$

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.