# American Institute of Mathematical Sciences

January  2021, 17(1): 117-131. doi: 10.3934/jimo.2019102

## Biobjective optimization over the efficient set of multiobjective integer programming problem

 1 USTHB, Department of Operational Research, Bp 32 El Alia, 16111 Algiers, Algeria 2 USTHB, LaROMaD Laboratory, Bp 32 El Alia, 16111 Algiers, Algeria

Received  May 2018 Revised  April 2019 Published  September 2019

In this article, an exact method is proposed to optimize two preference functions over the efficient set of a multiobjective integer linear program (MOILP). This kind of problems arises whenever two associated decision-makers have to optimize their respective preference functions over many efficient solutions. For this purpose, we develop a branch-and-cut algorithm based on linear programming, for finding efficient solutions in terms of both preference functions and MOILP problem, without explicitly enumerating all efficient solutions of MOILP problem. The branch and bound process, strengthened by efficient cuts and tests, allows us to prune a large number of nodes in the tree to avoid many solutions. An illustrative example and an experimental study are reported.

Citation: Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102
##### References:
 [1] M. Abbas and D. Chaabane, Optimizing a linear function over an integer efficient set, European J. Oper. Res., 174 (2006), 1140-1161.  doi: 10.1016/j.ejor.2005.02.072.  Google Scholar [2] P. Belotti, B. Soylu and M. Wiecek, Fathoming rules for biobjective mixed integer linear programs: Review and extensions, Discrete Optim., 22 (2016), 341-363.  doi: 10.1016/j.disopt.2016.09.003.  Google Scholar [3] N. Boland, H. Charkhgard and and M. Savelsbergh, A new method for optimizing a linear function over the efficient set of a multiobjective integer program, European J. Oper. Res., 260 (2017), 904-919.  doi: 10.1016/j.ejor.2016.02.037.  Google Scholar [4] H. P. Benson, Optimization over the efficient set, J. Math. Anal. Appl., 98 (1984), 562-580.  doi: 10.1016/0022-247X(84)90269-5.  Google Scholar [5] M. E-A Chergui and M. Moulaï, An exact method for a discrete multiobjective linear fractional optimization, J. Appl. Math. Decis. Sci., (2008), 12pp. doi: 10.1155/2008/760191.  Google Scholar [6] W. Drici, F- Z Ouaïl and M. Moulaï, Optimizing a linear fractional function over the integer efficient set, Ann. Oper. Res., 267 (2018), 135-151.  doi: 10.1007/s10479-017-2691-0.  Google Scholar [7] J. G. Ecker, N. S. Hegner and I. A. Kouada, Generating all maximal efficient faces for multiple objective linear programs, J. Optim. Theory Appl., 30 (1980), 353-381.  doi: 10.1007/BF00935493.  Google Scholar [8] J. G. Ecker and I. A. Kouada, Finding all efficient extreme points for multiple objective linear programs, Math. Programming, 14 (1978), 249-261.  doi: 10.1007/BF01588968.  Google Scholar [9] J. G. Ecker and J. H. Song, Optimizing a linear function over an efficient set, J. Optim. Theory Appl., 83 (1994), 541-563.  doi: 10.1007/BF02207641.  Google Scholar [10] J. P. Evans and R. E. Steuer, A revised simplex method for linear multiple objective programs, Math. Programming, 5 (1973), 54-72.  doi: 10.1007/BF01580111.  Google Scholar [11] J. M. Jorge, An algorithm for optimizing a linear function over an integer efficient set, European J. Oper. Res., 195 (2009), 98-103.  doi: 10.1016/j.ejor.2008.02.005.  Google Scholar [12] F- Z Ouaïl, M. E-A. Chergui and M. Moulaï, An exact method for optimizing a linear function over an integer efficient set, WSEAS Transactions on Circuits and Systems, 16(3) (2017), 141-148.   Google Scholar [13] Y. Yamamoto, Optimization over the efficient set: Overview, J. Global Optim., 22 (2002), 285-317.  doi: 10.1023/A:1013875600711.  Google Scholar

show all references

##### References:
 [1] M. Abbas and D. Chaabane, Optimizing a linear function over an integer efficient set, European J. Oper. Res., 174 (2006), 1140-1161.  doi: 10.1016/j.ejor.2005.02.072.  Google Scholar [2] P. Belotti, B. Soylu and M. Wiecek, Fathoming rules for biobjective mixed integer linear programs: Review and extensions, Discrete Optim., 22 (2016), 341-363.  doi: 10.1016/j.disopt.2016.09.003.  Google Scholar [3] N. Boland, H. Charkhgard and and M. Savelsbergh, A new method for optimizing a linear function over the efficient set of a multiobjective integer program, European J. Oper. Res., 260 (2017), 904-919.  doi: 10.1016/j.ejor.2016.02.037.  Google Scholar [4] H. P. Benson, Optimization over the efficient set, J. Math. Anal. Appl., 98 (1984), 562-580.  doi: 10.1016/0022-247X(84)90269-5.  Google Scholar [5] M. E-A Chergui and M. Moulaï, An exact method for a discrete multiobjective linear fractional optimization, J. Appl. Math. Decis. Sci., (2008), 12pp. doi: 10.1155/2008/760191.  Google Scholar [6] W. Drici, F- Z Ouaïl and M. Moulaï, Optimizing a linear fractional function over the integer efficient set, Ann. Oper. Res., 267 (2018), 135-151.  doi: 10.1007/s10479-017-2691-0.  Google Scholar [7] J. G. Ecker, N. S. Hegner and I. A. Kouada, Generating all maximal efficient faces for multiple objective linear programs, J. Optim. Theory Appl., 30 (1980), 353-381.  doi: 10.1007/BF00935493.  Google Scholar [8] J. G. Ecker and I. A. Kouada, Finding all efficient extreme points for multiple objective linear programs, Math. Programming, 14 (1978), 249-261.  doi: 10.1007/BF01588968.  Google Scholar [9] J. G. Ecker and J. H. Song, Optimizing a linear function over an efficient set, J. Optim. Theory Appl., 83 (1994), 541-563.  doi: 10.1007/BF02207641.  Google Scholar [10] J. P. Evans and R. E. Steuer, A revised simplex method for linear multiple objective programs, Math. Programming, 5 (1973), 54-72.  doi: 10.1007/BF01580111.  Google Scholar [11] J. M. Jorge, An algorithm for optimizing a linear function over an integer efficient set, European J. Oper. Res., 195 (2009), 98-103.  doi: 10.1016/j.ejor.2008.02.005.  Google Scholar [12] F- Z Ouaïl, M. E-A. Chergui and M. Moulaï, An exact method for optimizing a linear function over an integer efficient set, WSEAS Transactions on Circuits and Systems, 16(3) (2017), 141-148.   Google Scholar [13] Y. Yamamoto, Optimization over the efficient set: Overview, J. Global Optim., 22 (2002), 285-317.  doi: 10.1023/A:1013875600711.  Google Scholar
Search tree of the example
Optimal simplex table for node 0
 $\mathcal{B}_1$ $x_1$ $x_3$ $x_5$ $RHS$ $x_4$ $5/6$ -$1$ $2/3$ $53/6$ $x_2$ $1/3$ $0$ $2/3$ $16/3$ $x_6$ $1/3$ $5/2$ -$2/3$ 2/3 $\bar{d}^1$ -$7/6$ -$1/2$ -$10/3$ $80/3$
 $\mathcal{B}_1$ $x_1$ $x_3$ $x_5$ $RHS$ $x_4$ $5/6$ -$1$ $2/3$ $53/6$ $x_2$ $1/3$ $0$ $2/3$ $16/3$ $x_6$ $1/3$ $5/2$ -$2/3$ 2/3 $\bar{d}^1$ -$7/6$ -$1/2$ -$10/3$ $80/3$
Optimal simplex table for node 1
 $\mathcal{B}_2$ $x_3$ $x_5$ $x_7$ $RHS$ $x_4$ -$1$ $-1$ $\frac{5}{2}$ $8$ $x_1$ $0$ $2$ -$3$ $1$ $x_6$ $\frac{5}{2}$ $0$ -$1$ $1$ $x_2$ $0$ $0$ $1$ $5$ $\bar{d}^1$ -$\frac{1}{2}$ -$1$ -$\frac{7}{2}$ $\frac{51}{2}$ $\bar{d}^2$ $1$ $0$ $0$ $0$ $\bar{c}^1$ $-1$ $-2$ $5$ $-9$ $\bar{c}^2$ -$\frac{1}{2}$ $0$ -$2$ $10$ $\bar{c}^3$ -$1$ -$2$ $3$ $1$
 $\mathcal{B}_2$ $x_3$ $x_5$ $x_7$ $RHS$ $x_4$ -$1$ $-1$ $\frac{5}{2}$ $8$ $x_1$ $0$ $2$ -$3$ $1$ $x_6$ $\frac{5}{2}$ $0$ -$1$ $1$ $x_2$ $0$ $0$ $1$ $5$ $\bar{d}^1$ -$\frac{1}{2}$ -$1$ -$\frac{7}{2}$ $\frac{51}{2}$ $\bar{d}^2$ $1$ $0$ $0$ $0$ $\bar{c}^1$ $-1$ $-2$ $5$ $-9$ $\bar{c}^2$ -$\frac{1}{2}$ $0$ -$2$ $10$ $\bar{c}^3$ -$1$ -$2$ $3$ $1$
Optimal simplex table for node 3
 $\mathcal{B}_3$ $x_5$ $x_6$ $x_9$ $RHS$ $x_4$ 1 $\frac{5}{2}$ $\frac{21}{4}$ $\frac{21}{5}$ $x_1$ 2 -3 $\frac{15}{2}$ $\frac{11}{2}$ $x_3$ 0 0 -1 1 $x_2$ 0 1 $\frac{5}{2}$ $\frac{7}{2}$ $x_7$ 0 -1 -$\frac{5}{2}$ $\frac{3}{2}$ $x_8$ 0 -1 -$\frac{5}{2}$ $\frac{1}{2}$ $\bar{d}^1$ -1 -$\frac{7}{2}$ -$\frac{37}{4}$ $\frac{79}{4}$
 $\mathcal{B}_3$ $x_5$ $x_6$ $x_9$ $RHS$ $x_4$ 1 $\frac{5}{2}$ $\frac{21}{4}$ $\frac{21}{5}$ $x_1$ 2 -3 $\frac{15}{2}$ $\frac{11}{2}$ $x_3$ 0 0 -1 1 $x_2$ 0 1 $\frac{5}{2}$ $\frac{7}{2}$ $x_7$ 0 -1 -$\frac{5}{2}$ $\frac{3}{2}$ $x_8$ 0 -1 -$\frac{5}{2}$ $\frac{1}{2}$ $\bar{d}^1$ -1 -$\frac{7}{2}$ -$\frac{37}{4}$ $\frac{79}{4}$
Optimal simplex table for node 4
 $\mathcal{B}_4$ $x_6$ $x_9$ $x_{10}$ $RHS$ $x_4$ $1$ $\frac{3}{2}$ -$\frac{1}{2}$ $\frac{11}{2}$ $x_2$ $1$ $\frac{5}{2}$ 0 $\frac{7}{2}$ $x_3$ $0$ -$1$ $0$ $1$ $x_1$ $0$ $0$ $1$ $5$ $x_5$ -$\frac{3}{2}$ -$\frac{15}{4}$ -$\frac{1}{2}$ $\frac{1}{4}$ $x_7$ -$1$ -$\frac{5}{2}$ $0$ $\frac{3}{2}$ $x_8$ -$1$ -$\frac{5}{2}$ 0 $\frac{1}{2}$ $\bar{d}^1$ -$5$ -$13$ -$\frac{1}{2}$ $\frac{39}{2}$
 $\mathcal{B}_4$ $x_6$ $x_9$ $x_{10}$ $RHS$ $x_4$ $1$ $\frac{3}{2}$ -$\frac{1}{2}$ $\frac{11}{2}$ $x_2$ $1$ $\frac{5}{2}$ 0 $\frac{7}{2}$ $x_3$ $0$ -$1$ $0$ $1$ $x_1$ $0$ $0$ $1$ $5$ $x_5$ -$\frac{3}{2}$ -$\frac{15}{4}$ -$\frac{1}{2}$ $\frac{1}{4}$ $x_7$ -$1$ -$\frac{5}{2}$ $0$ $\frac{3}{2}$ $x_8$ -$1$ -$\frac{5}{2}$ 0 $\frac{1}{2}$ $\bar{d}^1$ -$5$ -$13$ -$\frac{1}{2}$ $\frac{39}{2}$
Optimal simplex table for node 5
 $\mathcal{B}_5$ $x_5$ $x_9$ $x_{10}$ $RHS$ $x_4$ $\frac{2}{3}$ -1 $\frac{5}{6}$ $\frac{29}{6}$ $x_1$ 0 0 -1 6 $x_3$ 0 -1 0 1 $x_2$ $\frac{2}{3}$ 0 $\frac{1}{3}$ $\frac{10}{3}$ $x_7$ $-\frac{2}{3}$ 0 $-\frac{1}{3}$ $\frac{5}{3}$ $x_8$ $-\frac{2}{3}$ 0 $-\frac{1}{3}$ $\frac{2}{3}$ $x_6$ $-\frac{2}{3}$ $\frac{5}{2}$ $-\frac{1}{3}$ $\frac{1}{6}$ $\bar{d}^1$ $-\frac{10}{3}$ $-\frac{1}{2}$ $\frac{7}{6}$ $\frac{115}{6}$
 $\mathcal{B}_5$ $x_5$ $x_9$ $x_{10}$ $RHS$ $x_4$ $\frac{2}{3}$ -1 $\frac{5}{6}$ $\frac{29}{6}$ $x_1$ 0 0 -1 6 $x_3$ 0 -1 0 1 $x_2$ $\frac{2}{3}$ 0 $\frac{1}{3}$ $\frac{10}{3}$ $x_7$ $-\frac{2}{3}$ 0 $-\frac{1}{3}$ $\frac{5}{3}$ $x_8$ $-\frac{2}{3}$ 0 $-\frac{1}{3}$ $\frac{2}{3}$ $x_6$ $-\frac{2}{3}$ $\frac{5}{2}$ $-\frac{1}{3}$ $\frac{1}{6}$ $\bar{d}^1$ $-\frac{10}{3}$ $-\frac{1}{2}$ $\frac{7}{6}$ $\frac{115}{6}$
Optimal simplex table for node 6
 $\mathcal{B}_6$ $x_9$ $x_{10}$ $x_{11}$ RHS $x_4$ -1 $-\frac{1}{2}$ 1 5 $x_1$ 0 1 0 5 $x_3$ -1 0 0 1 $x_2$ 0 0 0 3 $x_5$ 0 $-\frac{1}{2}$ $-\frac{3}{2}$ 1 $x_8$ 0 0 -1 1 $x_{6}$ $\frac{5}{2}$ 0 -1 $\frac{1}{2}$ $x_7$ 0 0 -1 2 $\bar{d}^1$ $-\frac{1}{2}$ $-\frac{1}{2}$ -5 17 $\bar{d}^2$ 1 0 0 1 $\bar{c}^1$ -1 -1 2 -2 $\bar{c}^2$ $-\frac{1}{2}$ 0 -2 $\frac{11}{2}$ $\bar{c}^3$ -1 -1 0 4
 $\mathcal{B}_6$ $x_9$ $x_{10}$ $x_{11}$ RHS $x_4$ -1 $-\frac{1}{2}$ 1 5 $x_1$ 0 1 0 5 $x_3$ -1 0 0 1 $x_2$ 0 0 0 3 $x_5$ 0 $-\frac{1}{2}$ $-\frac{3}{2}$ 1 $x_8$ 0 0 -1 1 $x_{6}$ $\frac{5}{2}$ 0 -1 $\frac{1}{2}$ $x_7$ 0 0 -1 2 $\bar{d}^1$ $-\frac{1}{2}$ $-\frac{1}{2}$ -5 17 $\bar{d}^2$ 1 0 0 1 $\bar{c}^1$ -1 -1 2 -2 $\bar{c}^2$ $-\frac{1}{2}$ 0 -2 $\frac{11}{2}$ $\bar{c}^3$ -1 -1 0 4
Optimal simplex table for node 8
 $\mathcal{B}_8$ $x_5$ $x_9$ $x_{11}$ RHS $x_4$ -1 -1 $\frac{5}{2}$ 4 $x_2$ 0 0 1 3 $x_3$ 0 -1 0 1 $x_1$ 2 0 -3 7 $x_6$ 0 $\frac{5}{2}$ -1 $\frac{1}{2}$ $x_7$ 0 0 -1 2 $x_8$ 0 0 -1 1 $x_{10}$ 2 0 -3 1 $\bar{d}^1$ -1 $-\frac{1}{2}$ $-\frac{7}{2}$ 18 $\bar{d}^2$ 0 1 0 1 $\bar{c}^1$ -2 -1 5 0 $\bar{c}^2$ 0 $-\frac{1}{2}$ -2 $\frac{11}{2}$ $\bar{c}^3$ -2 -1 3 6
 $\mathcal{B}_8$ $x_5$ $x_9$ $x_{11}$ RHS $x_4$ -1 -1 $\frac{5}{2}$ 4 $x_2$ 0 0 1 3 $x_3$ 0 -1 0 1 $x_1$ 2 0 -3 7 $x_6$ 0 $\frac{5}{2}$ -1 $\frac{1}{2}$ $x_7$ 0 0 -1 2 $x_8$ 0 0 -1 1 $x_{10}$ 2 0 -3 1 $\bar{d}^1$ -1 $-\frac{1}{2}$ $-\frac{7}{2}$ 18 $\bar{d}^2$ 0 1 0 1 $\bar{c}^1$ -2 -1 5 0 $\bar{c}^2$ 0 $-\frac{1}{2}$ -2 $\frac{11}{2}$ $\bar{c}^3$ -2 -1 3 6
Optimal simplex table for the node 10
 $\mathcal{B}_{10}$ $x_6$ $x_{10}$ $x_{13}$ RHS $x_5$ $-\frac{3}{2}$ $-\frac{1}{2}$ $-\frac{15}{4}$ 4 $x_4$ 1 $-\frac{1}{2}$ $\frac{3}{2}$ 4 $x_3$ 0 0 -1 2 $x_7$ -1 0 $-\frac{5}{2}$ 4 $x_8$ -1 1 $-\frac{5}{2}$ 3 $x_9$ 0 0 -1 1 $x_2$ 1 0 $\frac{5}{2}$ 1 $x_1$ 0 1 0 5 $\bar{d}^1$ -5 $-\frac{1}{2}$ -13 $\frac{13}{2}$ $\bar{d}^2$ 0 0 1 2 $\bar{c}^1$ 2 -1 4 1 $\bar{c}^2$ -2 0 $-\frac{11}{2}$ 1 $\bar{c}^3$ 0 -1 -1 3
 $\mathcal{B}_{10}$ $x_6$ $x_{10}$ $x_{13}$ RHS $x_5$ $-\frac{3}{2}$ $-\frac{1}{2}$ $-\frac{15}{4}$ 4 $x_4$ 1 $-\frac{1}{2}$ $\frac{3}{2}$ 4 $x_3$ 0 0 -1 2 $x_7$ -1 0 $-\frac{5}{2}$ 4 $x_8$ -1 1 $-\frac{5}{2}$ 3 $x_9$ 0 0 -1 1 $x_2$ 1 0 $\frac{5}{2}$ 1 $x_1$ 0 1 0 5 $\bar{d}^1$ -5 $-\frac{1}{2}$ -13 $\frac{13}{2}$ $\bar{d}^2$ 0 0 1 2 $\bar{c}^1$ 2 -1 4 1 $\bar{c}^2$ -2 0 $-\frac{11}{2}$ 1 $\bar{c}^3$ 0 -1 -1 3
Optimal simplex table for node 11
 $\mathcal{B}_{11}$ $x_4$ $x_6$ $x_{13}$ RHS $x_5$ -1 $-\frac{5}{2}$ $-\frac{21}{4}$ 0 $x_3$ 0 0 -1 2 $x_7$ 0 -1 $-\frac{5}{2}$ 4 $x_8$ 0 -1 $-\frac{5}{2}$ 3 $x_{10}$ 2 2 3 7 $x_{11}$ 0 -1 $-\frac{5}{2}$ 2 $x_{12}$ 0 -1 $-\frac{5}{2}$ 1 $x_9$ 0 0 -1 1 $x_2$ 1 0 $\frac{5}{2}$ 1 $x_1$ 2 2 3 13 $\bar{d}^1$ -1 -6 $-\frac{29}{2}$ $\frac{21}{2}$ $\bar{d}^2$ 0 0 3 6 $\bar{c}^1$ -2 0 1 9 $\bar{c}^2$ 0 -2 $-\frac{11}{2}$ 1 $\bar{c}^3$ -2 -2 -4 11
 $\mathcal{B}_{11}$ $x_4$ $x_6$ $x_{13}$ RHS $x_5$ -1 $-\frac{5}{2}$ $-\frac{21}{4}$ 0 $x_3$ 0 0 -1 2 $x_7$ 0 -1 $-\frac{5}{2}$ 4 $x_8$ 0 -1 $-\frac{5}{2}$ 3 $x_{10}$ 2 2 3 7 $x_{11}$ 0 -1 $-\frac{5}{2}$ 2 $x_{12}$ 0 -1 $-\frac{5}{2}$ 1 $x_9$ 0 0 -1 1 $x_2$ 1 0 $\frac{5}{2}$ 1 $x_1$ 2 2 3 13 $\bar{d}^1$ -1 -6 $-\frac{29}{2}$ $\frac{21}{2}$ $\bar{d}^2$ 0 0 3 6 $\bar{c}^1$ -2 0 1 9 $\bar{c}^2$ 0 -2 $-\frac{11}{2}$ 1 $\bar{c}^3$ -2 -2 -4 11
Random instances execution times
 [1] 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 [2] 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 [3] Mohammed Abdelghany, Amr B. Eltawil, Zakaria Yahia, Kazuhide Nakata. A hybrid variable neighbourhood search and dynamic programming approach for the nurse rostering problem. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2051-2072. doi: 10.3934/jimo.2020058 [4] Vladimir Gaitsgory, Ilya Shvartsman. Linear programming estimates for Cesàro and Abel limits of optimal values in optimal control problems. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021102 [5] Qing Liu, Bingo Wing-Kuen Ling, Qingyun Dai, Qing Miao, Caixia Liu. Optimal maximally decimated M-channel mirrored paraunitary linear phase FIR filter bank design via norm relaxed sequential quadratic programming. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1993-2011. doi: 10.3934/jimo.2020055 [6] Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006 [7] Melis Alpaslan Takan, Refail Kasimbeyli. Multiobjective mathematical models and solution approaches for heterogeneous fixed fleet vehicle routing problems. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2073-2095. doi: 10.3934/jimo.2020059

2019 Impact Factor: 1.366