Abstract
Recently, Luc defined a dual program for a multiple objective linear program. The dual problem is also a multiple objective linear problem and the weak duality and strong duality theorems for these primal and dual problems have been established. Here, we use these results to prove some relationships between multiple objective linear primal and dual problems. We extend the available results on single objective linear primal and dual problems to multiple objective linear primal and dual problems. Complementary slackness conditions for efficient solutions, and conditions for the existence of weakly efficient solution sets and existence of strictly primal and dual feasible points are established. We show that primal-dual (weakly) efficient solutions satisfying strictly complementary conditions exist. Furthermore, we consider Isermann’s and Kolumban’s dual problems and establish conditions for the existence of strictly primal and dual feasible points. We show the existence of primal-dual feasible points satisfying strictly complementary conditions for Isermann’s dual problem. Also, we give an alternative proof to establish necessary conditions for weakly efficient solutions of multiple objective programs, assuming the Kuhn–Tucker (KT) constraint qualification. We also provide a new condition to ensure the KT constraint qualification.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Arbel A, Oren SS (1996) Using approximate gradients in developing an interactive interior primal-dual multiobjective linear programming algorithm. Eur J Oper Res 89:202–211
Bagchi U (1989) Simultaneous minimization of mean and variation of flow time and waiting time in single machine systems. Oper Res 37:118–125
Balbas A, Heras A (1993) Duality theory for infinite dimensional multiobjective linear programming. Eur J Oper Res 68:379–388
Balbas A, Jimenez P, Heras A (1999) Duality theory and slackness conditions in multiobjective linear linear programming. Comput Math Appl 37:101–109
Carrizosa E, Conde E, Munoz M, Puerto J (1995) Planar pointobjective location problems with nonconvex constraints: a geometrical construction. J Global Optim 6:7786
Carrizosa E, Frenk JBG (1998) Dominating sets for convex functions with some applications. J Optim Theory Appl 96:281–295
Corley HW (1984) Duality theory for the matrix linear programming problem. J Math Anal Appl 104:47–52
Ehrgott M (2005) Multicrit Optim. Springer, Berlin, Heidelberg
Eschenauer H, Koski J, Osyczka A (1990) Multicrit Des Optim. Springer, Berlin
Evans G (1984) Overview of techniques for solving multiobjective mathematical programs. Manag Sci 30:1268–1282
Fu Y, Diwekar UM (2004) An efficient sampling approach to multiobjective optimization. Annals Oper Res 132:109–134
Galperin E, Guerra JJ (2001) Duality of nonscalarized multiobjective linear programs: dual balance, level sets and dual clusters of optimal vectors. J Optim Theory Appl 108:109–137
Gravel M, Martel IM, Madeau R, Price W, Tremblay R (1992) A multicriterion view of optimal ressource allocation in job-shop production. Eur J Oper Res 61:230–244
Heyde F, Lohne A (2008) Geometric duality in multiple objective linear programming. SIAM J Optim 19:836–845
Heyde F, Lohne A, Tammer C (2009) Set-valued duality theory for multiple objective linear programs and application to mathematical finance. Math Methods Oper Res 69:159–179
Isermann H (1978) On some relations between a dual pair of multiple objective linear programs. Zeitschrift fur Oper Res 22:33–41
Kornbluth JSH (1974) Duality, indifference and sensitivity analysis in multiple objective linear programming. Oper Res Quat 25:599–614
Leschine TM, Wallenius H, Verdini WA (1992) Interactive multiobjective analysis and assimilative capacity-based ocean disposal decisions. Eur J Oper Res 56:278–289
Luc DT (2011) On duality in multiple objective linear programming. Eur J Oper Res 210:158–168
Luc DT (2016) Multiobjective linear programming: an introduction. Springer, Switzerland
Luenberger DG, Ye Y (2008) Linear and nonlinear programming, 3rd edn. Springer, New York
Mangasarian OL (1969) Nonlinear programming. McGraw-Hill, New York
Nocedal J, Wright SJ (2006) Numerical optimization. Springer, USA
Prabuddha D, Gosh JB, Wells CE (1992) On the minimization of completion time variance with a bicriteria extension. Oper Res 40:1148–1155
Rodder W (1977) A generalized saddlepoint theory; its application to duality theory for linear vector optimum problems. Eur J Oper Res 1:55–59
Roos C, Terlaky T, Vial J-Ph (1997) Theory and algorithms for linear optimization: an interior point approach. Wiley, New York
Shan S, Wang GG (2005) An efficient pareto set identification approach for multiobjective optimization on black-box functions. J Mech Des 127:866–874
Tavana M (2004) A subjective assessment of alternative mission architectures for the human exploration of Mars at NASA using multicriteria decision making. Comput Oper Res 31:1147–1164
Vanderbei RJ (2014) Linear programming: foundations and extensions, Fourth Edition, International Series in Operations Research and Management Science, Vol 196
White DJ (1998) Epsilon-dominating solutions in mean-variance portfolio analysis. Eur J Oper Res 105:457–466
Wright SJ (1997) Primal-dual interior-point methods. SIAM, Philadelphia
Acknowledgements
The authors thank the Research Council of Sharif University of Technology for supporting this work. They also sincerely thank the two anonymous referees and Thierry Marchant, Editor-in-Chief, for their constructive remarks resulting in an improved presentation of the manuscript.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Mahdavi-Amiri, N., Salehi Sadaghiani, F. Strictly feasible solutions and strict complementarity in multiple objective linear optimization. 4OR-Q J Oper Res 15, 303–326 (2017). https://doi.org/10.1007/s10288-016-0338-7
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10288-016-0338-7
Keywords
- Multiple objective programming
- Duality
- Strictly complementary conditions
- Strictly feasible points
- Farkas’ lemma
- Primal-dual weakly efficient solutions
- Constraint qualification