October  2010, 6(4): 811-823. doi: 10.3934/jimo.2010.6.811

A method for optimizing over the integer efficient set

1. 

USTHB - Faculty of Mathematics - Operations Research Department, Bp 32 El Alia, BEZ, Algiers, 16121, Algeria

2. 

UMONS, Faculté Polytechnique, 9 Rue Houdain-Mons, Mons 7000, Belgium

Received  September 2009 Revised  May 2010 Published  September 2010

In this paper, we are interested in optimizing a linear function on the set of efficient solutions of a Multiple Objective Integer Linear Programming problem ($MOILP $). We propose an exact algorithm for maximizing a linear function denoted $ \phi $ on the set of efficient solutions of a $MOILP$ problem without having to enumerate explicitly all the elements of this set. Two techniques are used: the first is to reduce progressively the admissible domain by adding more constraints eliminating all the dominated points by the current solution; the second, when the new solution obtained by maximizing the function $\phi $ in the reduced area is not efficient, an exploration procedure is applied over the edges incident to this solution in order to find new alternative efficient solutions if they exist. The algorithm produces not only an optimal value of the linear function but also a subset of non-dominated solutions in the direction of $\phi$ that can be helpful in the practice.
Citation: Chaabane Djamal, Pirlot Marc. A method for optimizing over the integer efficient set. Journal of Industrial & Management Optimization, 2010, 6 (4) : 811-823. doi: 10.3934/jimo.2010.6.811
References:
[1]

M. Abbas and D. Chaabane, An algorithm for solving multiple objective integer linear programming problem,, RAIRO Operations Research, 36 (2002), 351.  doi: 10.1051/ro:2003006.  Google Scholar

[2]

M. Abbas and D. Chaabane, Optimizing a linear function over an integer efficient set,, European Journal of Operational Research, 174 (2006), 1140.  doi: 10.1016/j.ejor.2005.02.072.  Google Scholar

[3]

H. P. Benson, Existence of efficient solutions for vector maximization problems,, Journal of Optimization Theory and Appl, 26 (1978), 569.  doi: 10.1007/BF00933152.  Google Scholar

[4]

H. P. Benson and S. Sayin, Optimization over the efficient set: Four special cases,, Journal of Optimization Theory and Appl., 80 (1994), 3.  doi: 10.1007/BF02196590.  Google Scholar

[5]

V. J. Bowman, On the relationship of the Tchebytcheff norm and the efficient frontier of multiple-criteria objectives,, Lecture Notes in Economics and Mathematical Systems, 130 (1976), 76.   Google Scholar

[6]

Chaabane Djamal, "Contribution à l'Optimisation Multicritère en Variables Discrètes,", Ph.D thesis, (2007).   Google Scholar

[7]

A. Crema and J. Sylva, A method for finding the set of non-dominated vectors for multiple objective integer linear programs,, European Journal of Operational Research, 158 (2004), 46.  doi: 10.1016/S0377-2217(03)00255-8.  Google Scholar

[8]

G. B. Dantzig, On a linear programming combinatorial approach to the traveling salesman problem,, Operations Research, 7 (1959), 58.  doi: 10.1287/opre.7.1.58.  Google Scholar

[9]

J. G. Ecker and J. H. Song, Optimizing a linear function over an efficient set,, Journal of Optimization Theory and Applications, 83 (1994), 541.  doi: 10.1007/BF02207641.  Google Scholar

[10]

A. M. Geoffrion, Proper efficiency and the theory of vector maximization,, Journal of Mathematical Analysis and Applications, 22 (1968), 618.  doi: 10.1016/0022-247X(68)90201-1.  Google Scholar

[11]

R. Gupta and R. Malhotra, Multi-criteria integer linear programming problem,, Cahiers du CERO, 34 (1992), 51.   Google Scholar

[12]

M. J. Jorge, An algorithm for optimizing a linear function over an integer efficient set,, European Journal of Operational Research, 195 (2009), 98.  doi: 10.1016/j.ejor.2008.02.005.  Google Scholar

[13]

J. N. Karaivanova and S. C. Narula, An interactive procedure for multiple objective integer linear programming problems,, European Journal of Operational Research, 68 (1993), 344.  doi: 10.1016/0377-2217(93)90190-X.  Google Scholar

[14]

D. Klein and E. Hannan, An algorithm for multiple objective integer linear programming problem,, European Journal of Operational Research, 9 (1982), 378.  doi: 10.1016/0377-2217(82)90182-5.  Google Scholar

[15]

N. C. Nguyen, "An Algorithm for Optimizing a Linear Function Over the Integer Efficient Set,", Konrad-Zuse-Zentrum fur Informationstechnik Berlin, (1992).   Google Scholar

[16]

J. Philip, Algorithms for the vector maximization problem,, Mathematical Programming, 2 (1972), 207.  doi: 10.1007/BF01584543.  Google Scholar

[17]

J. Sylva and A. Crema, A method for finding well-dispersed subsets of non-dominated vectors for multiple objective mixed integer linear programs,, European Journal of Operational Reserach, 180 (2007), 1011.  doi: 10.1016/j.ejor.2006.02.049.  Google Scholar

[18]

Ta Van Tu, Optimization over the efficient set of a parametric multiple objective linear programming problem,, European Journal of Operational Reserach, 122 (2000), 570.  doi: 10.1016/S0377-2217(99)00095-8.  Google Scholar

[19]

J. Teghem and P. Kunsch, A survey of techniques for finding efficient solutions to multiobjective integer linear programming,, Asia Pacific Journal of Operations Research, 3 (1986), 95.   Google Scholar

[20]

D. J. White, The maximization of a function over the efficient set via a penalty function approach,, European Journal of Operational Research, 94 (1996), 143.  doi: 10.1016/0377-2217(95)00184-0.  Google Scholar

[21]

Y. Yamamoto, Optimization over the efficient set, overview,, Journal of Global Optimization, 22 (2002), 285.   Google Scholar

show all references

References:
[1]

M. Abbas and D. Chaabane, An algorithm for solving multiple objective integer linear programming problem,, RAIRO Operations Research, 36 (2002), 351.  doi: 10.1051/ro:2003006.  Google Scholar

[2]

M. Abbas and D. Chaabane, Optimizing a linear function over an integer efficient set,, European Journal of Operational Research, 174 (2006), 1140.  doi: 10.1016/j.ejor.2005.02.072.  Google Scholar

[3]

H. P. Benson, Existence of efficient solutions for vector maximization problems,, Journal of Optimization Theory and Appl, 26 (1978), 569.  doi: 10.1007/BF00933152.  Google Scholar

[4]

H. P. Benson and S. Sayin, Optimization over the efficient set: Four special cases,, Journal of Optimization Theory and Appl., 80 (1994), 3.  doi: 10.1007/BF02196590.  Google Scholar

[5]

V. J. Bowman, On the relationship of the Tchebytcheff norm and the efficient frontier of multiple-criteria objectives,, Lecture Notes in Economics and Mathematical Systems, 130 (1976), 76.   Google Scholar

[6]

Chaabane Djamal, "Contribution à l'Optimisation Multicritère en Variables Discrètes,", Ph.D thesis, (2007).   Google Scholar

[7]

A. Crema and J. Sylva, A method for finding the set of non-dominated vectors for multiple objective integer linear programs,, European Journal of Operational Research, 158 (2004), 46.  doi: 10.1016/S0377-2217(03)00255-8.  Google Scholar

[8]

G. B. Dantzig, On a linear programming combinatorial approach to the traveling salesman problem,, Operations Research, 7 (1959), 58.  doi: 10.1287/opre.7.1.58.  Google Scholar

[9]

J. G. Ecker and J. H. Song, Optimizing a linear function over an efficient set,, Journal of Optimization Theory and Applications, 83 (1994), 541.  doi: 10.1007/BF02207641.  Google Scholar

[10]

A. M. Geoffrion, Proper efficiency and the theory of vector maximization,, Journal of Mathematical Analysis and Applications, 22 (1968), 618.  doi: 10.1016/0022-247X(68)90201-1.  Google Scholar

[11]

R. Gupta and R. Malhotra, Multi-criteria integer linear programming problem,, Cahiers du CERO, 34 (1992), 51.   Google Scholar

[12]

M. J. Jorge, An algorithm for optimizing a linear function over an integer efficient set,, European Journal of Operational Research, 195 (2009), 98.  doi: 10.1016/j.ejor.2008.02.005.  Google Scholar

[13]

J. N. Karaivanova and S. C. Narula, An interactive procedure for multiple objective integer linear programming problems,, European Journal of Operational Research, 68 (1993), 344.  doi: 10.1016/0377-2217(93)90190-X.  Google Scholar

[14]

D. Klein and E. Hannan, An algorithm for multiple objective integer linear programming problem,, European Journal of Operational Research, 9 (1982), 378.  doi: 10.1016/0377-2217(82)90182-5.  Google Scholar

[15]

N. C. Nguyen, "An Algorithm for Optimizing a Linear Function Over the Integer Efficient Set,", Konrad-Zuse-Zentrum fur Informationstechnik Berlin, (1992).   Google Scholar

[16]

J. Philip, Algorithms for the vector maximization problem,, Mathematical Programming, 2 (1972), 207.  doi: 10.1007/BF01584543.  Google Scholar

[17]

J. Sylva and A. Crema, A method for finding well-dispersed subsets of non-dominated vectors for multiple objective mixed integer linear programs,, European Journal of Operational Reserach, 180 (2007), 1011.  doi: 10.1016/j.ejor.2006.02.049.  Google Scholar

[18]

Ta Van Tu, Optimization over the efficient set of a parametric multiple objective linear programming problem,, European Journal of Operational Reserach, 122 (2000), 570.  doi: 10.1016/S0377-2217(99)00095-8.  Google Scholar

[19]

J. Teghem and P. Kunsch, A survey of techniques for finding efficient solutions to multiobjective integer linear programming,, Asia Pacific Journal of Operations Research, 3 (1986), 95.   Google Scholar

[20]

D. J. White, The maximization of a function over the efficient set via a penalty function approach,, European Journal of Operational Research, 94 (1996), 143.  doi: 10.1016/0377-2217(95)00184-0.  Google Scholar

[21]

Y. Yamamoto, Optimization over the efficient set, overview,, Journal of Global Optimization, 22 (2002), 285.   Google Scholar

[1]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

[2]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023

[3]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024

[4]

Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017

[5]

Yuncherl Choi, Taeyoung Ha, Jongmin Han, Sewoong Kim, Doo Seok Lee. Turing instability and dynamic phase transition for the Brusselator model with multiple critical eigenvalues. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021035

[6]

Guido De Philippis, Antonio De Rosa, Jonas Hirsch. The area blow up set for bounded mean curvature submanifolds with respect to elliptic surface energy functionals. Discrete & Continuous Dynamical Systems - A, 2019, 39 (12) : 7031-7056. doi: 10.3934/dcds.2019243

[7]

Chin-Chin Wu. Existence of traveling wavefront for discrete bistable competition model. Discrete & Continuous Dynamical Systems - B, 2011, 16 (3) : 973-984. doi: 10.3934/dcdsb.2011.16.973

[8]

Matthias Erbar, Jan Maas. Gradient flow structures for discrete porous medium equations. Discrete & Continuous Dynamical Systems - A, 2014, 34 (4) : 1355-1374. doi: 10.3934/dcds.2014.34.1355

[9]

Diana Keller. Optimal control of a linear stochastic Schrödinger equation. Conference Publications, 2013, 2013 (special) : 437-446. doi: 10.3934/proc.2013.2013.437

[10]

Guillaume Bal, Wenjia Jing. Homogenization and corrector theory for linear transport in random media. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1311-1343. doi: 10.3934/dcds.2010.28.1311

[11]

Paula A. González-Parra, Sunmi Lee, Leticia Velázquez, Carlos Castillo-Chavez. A note on the use of optimal control on a discrete time model of influenza dynamics. Mathematical Biosciences & Engineering, 2011, 8 (1) : 183-197. doi: 10.3934/mbe.2011.8.183

[12]

Ronald E. Mickens. Positivity preserving discrete model for the coupled ODE's modeling glycolysis. Conference Publications, 2003, 2003 (Special) : 623-629. doi: 10.3934/proc.2003.2003.623

[13]

Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Linear nonbinary covering codes and saturating sets in projective spaces. Advances in Mathematics of Communications, 2011, 5 (1) : 119-147. doi: 10.3934/amc.2011.5.119

[14]

W. Cary Huffman. On the theory of $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes. Advances in Mathematics of Communications, 2013, 7 (3) : 349-378. doi: 10.3934/amc.2013.7.349

[15]

Alexey Yulin, Alan Champneys. Snake-to-isola transition and moving solitons via symmetry-breaking in discrete optical cavities. Discrete & Continuous Dynamical Systems - S, 2011, 4 (5) : 1341-1357. doi: 10.3934/dcdss.2011.4.1341

[16]

Emma D'Aniello, Saber Elaydi. The structure of $ \omega $-limit sets of asymptotically non-autonomous discrete dynamical systems. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 903-915. doi: 10.3934/dcdsb.2019195

[17]

Misha Bialy, Andrey E. Mironov. Rich quasi-linear system for integrable geodesic flows on 2-torus. Discrete & Continuous Dynamical Systems - A, 2011, 29 (1) : 81-90. doi: 10.3934/dcds.2011.29.81

[18]

Fumihiko Nakamura. Asymptotic behavior of non-expanding piecewise linear maps in the presence of random noise. Discrete & Continuous Dynamical Systems - B, 2018, 23 (6) : 2457-2473. doi: 10.3934/dcdsb.2018055

[19]

Hirofumi Notsu, Masato Kimura. Symmetry and positive definiteness of the tensor-valued spring constant derived from P1-FEM for the equations of linear elasticity. Networks & Heterogeneous Media, 2014, 9 (4) : 617-634. doi: 10.3934/nhm.2014.9.617

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (84)
  • HTML views (0)
  • Cited by (8)

Other articles
by authors

[Back to Top]