×

An indefinite quadratic optimization over an integer efficient set. (English) Zbl 1402.90110

Summary: In this paper, a new exact method is proposed for solving the maximization problem, say \(QP_E\), of an indefinite quadratic utility function over the efficient set of a multi-objective integer linear programming (MOILP) problem. Indeed, we develop a branch and cut algorithm based on a continuous indefinite quadratic optimization, for reaching an integer optimal solution of \(QP_E\) problem without having to enumerate explicitly all integer efficient solutions of MOILP problem. The branch and bound process, strengthened by efficient cuts and tests, allows us to fathom considerably nodes in the tree. Thus, a large number of feasible and non-efficient solutions can be avoided. An experimental study is reported to validate the theoretical results.

MSC:

90C20 Quadratic programming
90C29 Multi-objective and goal programming
90C10 Integer programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ozlen, M; Azizoglu, M; Burton, BA, Optimising a nonlinear utility function in multi-objective integer programming, J Global Optim, 56, 1, 93-102, (2013) · Zbl 1273.90188
[2] Henderson, JM; Quandt, RE, Microeconomic theory, (1971), McGraw-Hill, New York (NY) · Zbl 0224.90014
[3] Axehill, D, (2008)
[4] Belkeziz, K; Metrane, A, Optimisation d’une fonction linéaire sur l’ensemble des solutions efficaces d’un problème multicritère quadratique convexe, Ann Math Blaise Pascal, 11, 1, 19-33, (2004) · Zbl 1132.90014
[5] Benson, HP, Optimization over the efficient set, J Math Ana App, 98, 562-580, (1984) · Zbl 0534.90077
[6] Jorge, JM, An algorithm for optimizing a linear function over an integer efficient set, Eur J Oper Res, 195, 98-103, (2009) · Zbl 1161.90443
[7] Yamamoto, Y, Optimization over the effcient set : overview, J Global Optim, 22, 1-4, 285-317, (2002) · Zbl 1045.90061
[8] Zerdani, O; Moulaï, M, Optimization over an integer efficient set of a multiple objective linear fractional problem, App Math Sci, 5, 50, 2451-2466, (2011) · Zbl 1247.90201
[9] Ehrgott, M; Hamacher, HW; Klamroth, K; Nickel, S; Schobel, A; Wiecek, MM, A note on the equivalence of balance points and Pareto solutions in multiple-objective programming, J Optim Theory Appl, 92, 1, 209-212, (1997) · Zbl 0889.90122
[10] Swarup, K, Quadratic programming, CCERO, 8, 4, 223-234, (1966) · Zbl 0143.42602
[11] Bector, CR, Indefinite quadratic fractional functional programming, Metrika, 18, 1, 21-30, (1972) · Zbl 0225.90034
[12] Hadley, M, Linear programming, (1962), Addison Wesley, Reading Mass · Zbl 0102.36304
[13] Isermann, H, Proper efficiency and the linear vector maximization problem, Oper Res, 22, 189-191, (1974) · Zbl 0274.90024
[14] Ecker, J; Kouada, I, Finding efficient points for linear multiple objective programs, Math Prog, 8, 375-377, (1975)
[15] Chergui, MEA; Moulaï, M, An exact method for a discrete multiobjective linear fractional optimization, J Appl Math Deci Sci, 2008, 760191, (2008) · Zbl 1175.90347 · doi:10.1155/2008/760191
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.