• Previous Article
    Global convergence of a modified Broyden family method for nonconvex functions
  • JIMO Home
  • This Issue
  • Next Article
    A dynamic analysis of a monopolist's product and process innovation with nonlinear demand and expected quality effects
doi: 10.3934/jimo.2022059
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

Solving discrete linear fractional bilevel programs with multiple objectives at the upper level

USTHB, Department of Operations Research, BP 32 El Alia, 16111 Algiers, Algeria

*Corresponding author: Fatima Fali

Received  August 2021 Revised  January 2022 Early access April 2022

This paper proposes an exact method to solve an integer linear fractional bilevel problem with multiple objectives at the upper level, designated by $ IFMOBP $. The proposed algorithm generates a set of efficient solutions using a branch and cut algorithm based on a continuous upper level linear fractional problem. Then, the integer optimal solution obtained is tested for optimality of the lower level problem. First, the integer optimal solution of the bilevel problem is sought with a single objective function at each level. After that, an efficient cut is added and new integer solutions are determined. The efficient set is updated each time a candidate bilevel feasible solution non dominated is got and the process ends when there are no unexplored parts of the original domain. The proposed method is based on a dantzig cut to find the next best integer solution of the first objective function of the upper level, an efficient cut to get the set of efficient solutions for the main problem, and the classical branch and bound technique for integer decision variables. After the presentation of the algorithm, a numerical example and computational experiments are provided.

Citation: Fatima Fali, Mustapha Moulaï. Solving discrete linear fractional bilevel programs with multiple objectives at the upper level. Journal of Industrial and Management Optimization, doi: 10.3934/jimo.2022059
References:
[1]

M. Abo-Sinna, A bilevel nonlinear multiobjective decision making under fuzziness, Opsearch, 38 (2001), 484-495.  doi: 10.1007/BF03398652.

[2]

M. J. AlvesS. Dempe and J. Judice, Computing the Pareto frontier of a bi-objective bi-level linear problem using a multiobjective mixed-integer programming algorithm, Optimization: A Journal of Mathematical Programming and Operations Research, 61 (2012), 335-358.  doi: 10.1080/02331934.2010.511674.

[3]

Z. Ankhili and A. Mansouri, An exact penalty on bilevel programs with linear vector optimization lower level, European J. Oper. Res., 197 (2009), 36-41.  doi: 10.1016/j.ejor.2008.06.026.

[4]

J. F. Bard, Practical Bilevel Optimization. Algorithms and Applications, Kluwer Academic Publishers, Dordrecht, 1998. doi: 10.1007/978-1-4757-2836-1.

[5]

H. Bonnel and J. Morgan, Semivectorial bilevel optimization problem: Penalty approach, J. Optim. Theory Appl., 131 (2006), 365-382.  doi: 10.1007/s10957-006-9150-4.

[6]

H. Calvete and C. Gal, Local optimality in quasiconcave bilevel programming, Monogr. Semin. Mat. García Galdeano, 27 (2003), 153-160. 

[7]

H. I. Calvete and C. Gale, Linear bilevel programs with multiple objectives at the upper level, J. Comput. Appl. Math., 234 (2010), 950-959.  doi: 10.1016/j.cam.2008.12.010.

[8]

A. Cambini and L. Martein, Equivalence in linear fractional programming, Optimization, 23 (1992), 41-51.  doi: 10.1080/02331939208843743.

[9]

M. E. -A. Chergui and M. Moulaï, An exact method for a discrete multiobjective linear fractional optimization, J. Appl. Math. Decis. Sci., 2008 (2008), Art. ID 760191, 12 pp. doi: 10.1155/2008/760191.

[10]

B. ColsonP. Marcotte and G. Savard, An overview of bilevel optimization, Ann. Oper. Res., 153 (2007), 235-256.  doi: 10.1007/s10479-007-0176-2.

[11]

K. Deb and A. Sinha, Solving bilevel multi-objective optimization problems using evolutionary algorithms, Lecture Notes in Computer Science: Evolutionary Multi-criterion Optimization, 5467 (2009), 110-124.  doi: 10.1007/978-3-642-01020-0_13.

[12]

S. Dempe, Foundations of Bilevel Programming, Kluwer Academic Publishers, Dordrecht, 2002.

[13]

S. Dempe, Annotated bibliography on bilevel programming and mathematical programs with equilibrium constraints, Optimization, 52 (2003), 333-359.  doi: 10.1080/0233193031000149894.

[14]

O. E. Emam, Interactive approach to bi-level integer multiobjective fractional programming problem, Appl. Math. Comput., 223 (2013), 17-24.  doi: 10.1016/j.amc.2013.07.085.

[15]

Y. B. Lv, An exact penalty function approach for solving the linear bilevel multiobjective programming problem, Filomat, 29 (2015), 773-779.  doi: 10.2298/FIL1504773L.

[16]

Y. B. Lv and Z. P. Wan, Solving linear bilevel multiobjective programming problem via exact penalty function approach, J. Inequal. Appl., 2015 (2015), 258, 12 pp. doi: 10.1186/s13660-015-0780-7.

[17]

Y. Lv and Z. Wan, Linear bilevel multiobjective optimization problem: Penalty approch, J. Ind. Manag. Optim., 15 (2019), 1213-1223.  doi: 10.3934/jimo.2018092.

[18]

B. Martos, Nonlinear Programming, Theory and Methods, Amsterdam: North-Holland, Publishing Co., Amsterdam-Oxford; American Elsevier Publishing Co., Inc., New York, 1975.

[19]

I. NishizakiM. SakawaL. Yibing and W. Zhongping, Stackelberg solutions to multiobjective two-level linear programming problem, J. Optimization Theory and Appl., 103 (1999), 161-182. 

[20]

M. S. OsmanM. A. Abo-SinnaA. H. Amer and O. E. Emam, A multilevel nonlinear multiob- jective decision making under fuzziness, Appl. Math. Comput., 153 (2004), 239-252.  doi: 10.1016/S0096-3003(03)00628-3.

[21]

A. Osyczka and S. Kundu, A new methode to solve generalized multicriteria optimization problems using the simple genetic algorithm, Structural Optimization, 10 (1995), 94-99. 

[22]

C. O. PieumeP. MarcotteL. P. Fotso and P. Siarry, Generating efficient solutions in bilevel multi-objective programming problems, American J. Oper. Res., 3 (2013), 289-298.  doi: 10.4236/ajor.2013.32026.

[23]

O. M. Saad and M. S. Hafez, An algorithm for solving bi-level integer linear fractional programming problem based on fuzzy approach, General Math. Notes, 3 (2011), 86-99. 

[24]

X. Shi and H. Xia, Interactive bilevel multi-objective decision making, J. Ope. Res. Society, 48 (1997), 943-949. 

[25]

X. Shi and H. Xia, Model and interactive algorithm of bi-level multi-objective decision-making with multiple interconnected decision makers, J. Multi-Criteria Decision Analysis, 10 (2001), 27-34. 

[26]

C. TengL. Li and H. Li, A class of genetic algorithms on bilevel multiobjective decision making problem, J. Systems Science and Systems Engineering, 9 (2000), 290-296. 

[27]

D. Thirwani and S. R. Arora, An algorithm for the integer linear fractional bilevel programming problem, Optimization, 39 (1997), 53-67.  doi: 10.1080/02331939708844271.

[28]

V. VermaH. C. Bakhshi and M. C. Puri, Ranking in integer linear fractional programming problems, Z. Oper. Res., 34 (1990), 325-334.  doi: 10.1007/BF01416224.

[29]

L. Vicente and P. Calamai, Bilevel and multilevel programming, J. Global Optim., 5 (1994), 291-306.  doi: 10.1007/BF01096458.

[30]

Y. Yin, Multiobjective bilevel optimization for transportation planning and management problems, J. Advanced Transportation, 36 (2002), 93-105.  doi: 10.1002/atr.5670360106.

[31]

Y. F. Yin, Genetic algorithmes based approch for bilevel programming models, J. Transportation Engineering, 126 (2000), 115-120. 

[32]

E. A. YounessO. E. Emam and M. S. Hafez, Simplex method for solving bi-level linear fractional integer programming problem with fuzzy number, Inter. J. Math. Sci. Engineering Appl., 7 (2013), 351-363. 

[33]

E. A. YounessO. E. Emam and M. S. Hafez, Fuzzy bi-level multiobjective fractional integer programming, Appl. Math. Inf. Sci., 8 (2014), 2857-2863.  doi: 10.12785/amis/080622.

[34]

Y. Zheng and Z. Wan, A solution method for semivectorial bilevel programming problem via penalty method, J. Appl. Math. Comput., 37 (2011), 207-219.  doi: 10.1007/s12190-010-0430-7.

show all references

References:
[1]

M. Abo-Sinna, A bilevel nonlinear multiobjective decision making under fuzziness, Opsearch, 38 (2001), 484-495.  doi: 10.1007/BF03398652.

[2]

M. J. AlvesS. Dempe and J. Judice, Computing the Pareto frontier of a bi-objective bi-level linear problem using a multiobjective mixed-integer programming algorithm, Optimization: A Journal of Mathematical Programming and Operations Research, 61 (2012), 335-358.  doi: 10.1080/02331934.2010.511674.

[3]

Z. Ankhili and A. Mansouri, An exact penalty on bilevel programs with linear vector optimization lower level, European J. Oper. Res., 197 (2009), 36-41.  doi: 10.1016/j.ejor.2008.06.026.

[4]

J. F. Bard, Practical Bilevel Optimization. Algorithms and Applications, Kluwer Academic Publishers, Dordrecht, 1998. doi: 10.1007/978-1-4757-2836-1.

[5]

H. Bonnel and J. Morgan, Semivectorial bilevel optimization problem: Penalty approach, J. Optim. Theory Appl., 131 (2006), 365-382.  doi: 10.1007/s10957-006-9150-4.

[6]

H. Calvete and C. Gal, Local optimality in quasiconcave bilevel programming, Monogr. Semin. Mat. García Galdeano, 27 (2003), 153-160. 

[7]

H. I. Calvete and C. Gale, Linear bilevel programs with multiple objectives at the upper level, J. Comput. Appl. Math., 234 (2010), 950-959.  doi: 10.1016/j.cam.2008.12.010.

[8]

A. Cambini and L. Martein, Equivalence in linear fractional programming, Optimization, 23 (1992), 41-51.  doi: 10.1080/02331939208843743.

[9]

M. E. -A. Chergui and M. Moulaï, An exact method for a discrete multiobjective linear fractional optimization, J. Appl. Math. Decis. Sci., 2008 (2008), Art. ID 760191, 12 pp. doi: 10.1155/2008/760191.

[10]

B. ColsonP. Marcotte and G. Savard, An overview of bilevel optimization, Ann. Oper. Res., 153 (2007), 235-256.  doi: 10.1007/s10479-007-0176-2.

[11]

K. Deb and A. Sinha, Solving bilevel multi-objective optimization problems using evolutionary algorithms, Lecture Notes in Computer Science: Evolutionary Multi-criterion Optimization, 5467 (2009), 110-124.  doi: 10.1007/978-3-642-01020-0_13.

[12]

S. Dempe, Foundations of Bilevel Programming, Kluwer Academic Publishers, Dordrecht, 2002.

[13]

S. Dempe, Annotated bibliography on bilevel programming and mathematical programs with equilibrium constraints, Optimization, 52 (2003), 333-359.  doi: 10.1080/0233193031000149894.

[14]

O. E. Emam, Interactive approach to bi-level integer multiobjective fractional programming problem, Appl. Math. Comput., 223 (2013), 17-24.  doi: 10.1016/j.amc.2013.07.085.

[15]

Y. B. Lv, An exact penalty function approach for solving the linear bilevel multiobjective programming problem, Filomat, 29 (2015), 773-779.  doi: 10.2298/FIL1504773L.

[16]

Y. B. Lv and Z. P. Wan, Solving linear bilevel multiobjective programming problem via exact penalty function approach, J. Inequal. Appl., 2015 (2015), 258, 12 pp. doi: 10.1186/s13660-015-0780-7.

[17]

Y. Lv and Z. Wan, Linear bilevel multiobjective optimization problem: Penalty approch, J. Ind. Manag. Optim., 15 (2019), 1213-1223.  doi: 10.3934/jimo.2018092.

[18]

B. Martos, Nonlinear Programming, Theory and Methods, Amsterdam: North-Holland, Publishing Co., Amsterdam-Oxford; American Elsevier Publishing Co., Inc., New York, 1975.

[19]

I. NishizakiM. SakawaL. Yibing and W. Zhongping, Stackelberg solutions to multiobjective two-level linear programming problem, J. Optimization Theory and Appl., 103 (1999), 161-182. 

[20]

M. S. OsmanM. A. Abo-SinnaA. H. Amer and O. E. Emam, A multilevel nonlinear multiob- jective decision making under fuzziness, Appl. Math. Comput., 153 (2004), 239-252.  doi: 10.1016/S0096-3003(03)00628-3.

[21]

A. Osyczka and S. Kundu, A new methode to solve generalized multicriteria optimization problems using the simple genetic algorithm, Structural Optimization, 10 (1995), 94-99. 

[22]

C. O. PieumeP. MarcotteL. P. Fotso and P. Siarry, Generating efficient solutions in bilevel multi-objective programming problems, American J. Oper. Res., 3 (2013), 289-298.  doi: 10.4236/ajor.2013.32026.

[23]

O. M. Saad and M. S. Hafez, An algorithm for solving bi-level integer linear fractional programming problem based on fuzzy approach, General Math. Notes, 3 (2011), 86-99. 

[24]

X. Shi and H. Xia, Interactive bilevel multi-objective decision making, J. Ope. Res. Society, 48 (1997), 943-949. 

[25]

X. Shi and H. Xia, Model and interactive algorithm of bi-level multi-objective decision-making with multiple interconnected decision makers, J. Multi-Criteria Decision Analysis, 10 (2001), 27-34. 

[26]

C. TengL. Li and H. Li, A class of genetic algorithms on bilevel multiobjective decision making problem, J. Systems Science and Systems Engineering, 9 (2000), 290-296. 

[27]

D. Thirwani and S. R. Arora, An algorithm for the integer linear fractional bilevel programming problem, Optimization, 39 (1997), 53-67.  doi: 10.1080/02331939708844271.

[28]

V. VermaH. C. Bakhshi and M. C. Puri, Ranking in integer linear fractional programming problems, Z. Oper. Res., 34 (1990), 325-334.  doi: 10.1007/BF01416224.

[29]

L. Vicente and P. Calamai, Bilevel and multilevel programming, J. Global Optim., 5 (1994), 291-306.  doi: 10.1007/BF01096458.

[30]

Y. Yin, Multiobjective bilevel optimization for transportation planning and management problems, J. Advanced Transportation, 36 (2002), 93-105.  doi: 10.1002/atr.5670360106.

[31]

Y. F. Yin, Genetic algorithmes based approch for bilevel programming models, J. Transportation Engineering, 126 (2000), 115-120. 

[32]

E. A. YounessO. E. Emam and M. S. Hafez, Simplex method for solving bi-level linear fractional integer programming problem with fuzzy number, Inter. J. Math. Sci. Engineering Appl., 7 (2013), 351-363. 

[33]

E. A. YounessO. E. Emam and M. S. Hafez, Fuzzy bi-level multiobjective fractional integer programming, Appl. Math. Inf. Sci., 8 (2014), 2857-2863.  doi: 10.12785/amis/080622.

[34]

Y. Zheng and Z. Wan, A solution method for semivectorial bilevel programming problem via penalty method, J. Appl. Math. Comput., 37 (2011), 207-219.  doi: 10.1007/s12190-010-0430-7.

Figure 1.  Tree representing states of nodes during Branch & Cut algorithm
Table 1.  Simplex table for node 0
B0 x1 x2 x6 Rhs
x4 1 -3 -2 1
x5 -1 -1 -1 1
x3 1 2 1 2
x7 -2 -1 -2 2
$c_{j}^1-z_j^{1(1)}$ -1 -4 -2 -7
$d_{j}^1-z_j^{1(2)}$ 0 3 0 -2
$\gamma_j^1$ -2 -29 -4 7/2
$c_{j}^2-z_j^{2(1)}$ 1 2 0 -2
$d_{j}^2-z_j^{2(2)}$ -1 -2 -1 -3
$\gamma_j^2$ 5 10 2 2/3
B0 x1 x2 x6 Rhs
x4 1 -3 -2 1
x5 -1 -1 -1 1
x3 1 2 1 2
x7 -2 -1 -2 2
$c_{j}^1-z_j^{1(1)}$ -1 -4 -2 -7
$d_{j}^1-z_j^{1(2)}$ 0 3 0 -2
$\gamma_j^1$ -2 -29 -4 7/2
$c_{j}^2-z_j^{2(1)}$ 1 2 0 -2
$d_{j}^2-z_j^{2(2)}$ -1 -2 -1 -3
$\gamma_j^2$ 5 10 2 2/3
Table 2.  Simplex table for node 1
B1 x2 x6 x8 Rhs
x4 -4 -3 1 0
x5 0 0 -1 2
x3 1 0 1 1
x7 1 0 -2 4
x1 1 1 -1 1
$c_{j}^1-z_j^{1(1)}$ -3 -1 -1 -6
$d_{j}^1-z_j^{1(2)}$ 3 0 0 -2
$\gamma_j^1$ -24 -2 -2 3
$c_{j}^2-z_j^{2(1)}$ 1 -1 1 -3
$d_{j}^2-z_j^{2(2)} $ -1 0 -1 -2
$\gamma_j^2$ 5 -2 5 3/2
B1 x2 x6 x8 Rhs
x4 -4 -3 1 0
x5 0 0 -1 2
x3 1 0 1 1
x7 1 0 -2 4
x1 1 1 -1 1
$c_{j}^1-z_j^{1(1)}$ -3 -1 -1 -6
$d_{j}^1-z_j^{1(2)}$ 3 0 0 -2
$\gamma_j^1$ -24 -2 -2 3
$c_{j}^2-z_j^{2(1)}$ 1 -1 1 -3
$d_{j}^2-z_j^{2(2)} $ -1 0 -1 -2
$\gamma_j^2$ 5 -2 5 3/2
Table 3.  Simplex table of the lower level problem
B y2 y3 Rhs
y1 1/2 1/2 1
y4 1/2 -3/2 3
$p_{j}-z_j^{(1)}$ 1/2 -1/2 -2
$q_{j}-z_j^{(2)}$ 1 0 -3
$\gamma_j $ -1/2 -3/2 2/3
B y2 y3 Rhs
y1 1/2 1/2 1
y4 1/2 -3/2 3
$p_{j}-z_j^{(1)}$ 1/2 -1/2 -2
$q_{j}-z_j^{(2)}$ 1 0 -3
$\gamma_j $ -1/2 -3/2 2/3
Table 4.  Simplex table of the lower level problem
$b_1$ $y_3$ $y_5$ Rhs
y1 0 1 0
y4 -2 1 4
y2 1 -2 1
$p_{j}-z_j^{(1)}$ -1 1 -3
$q_{j}-z_j^{(2)}$ -1 2 -5
$\gamma_j$ -2 -1 3/5
$b_1$ $y_3$ $y_5$ Rhs
y1 0 1 0
y4 -2 1 4
y2 1 -2 1
$p_{j}-z_j^{(1)}$ -1 1 -3
$q_{j}-z_j^{(2)}$ -1 2 -5
$\gamma_j$ -2 -1 3/5
Table 5.  Simplex table for node 4
B1 x2 x9 x10 Rhs
x6 2 -1 -1 1
x5 1 -1 0 3
x3 0 1 0 0
x7 3 -2 0 6
x1 0 0 1 1
x8 1 -1 0 1
x4 1 -2 -3 2
$c_{j}^1-z_j^{1(1)}$ 0 -2 -1 -4
$d_{j}^1-z_j^{1(2)}$ 3 0 0 -2
$\gamma_j^1$ -12 -4 -2 2
$c_{j}^2-z_j^{2(1)}$ 2 0 -1 -3
$d_{j}^2-z_j^{2(2)}$ 0 -1 0 -1
$\gamma_j^2$ 2 3 -1 3
B1 x2 x9 x10 Rhs
x6 2 -1 -1 1
x5 1 -1 0 3
x3 0 1 0 0
x7 3 -2 0 6
x1 0 0 1 1
x8 1 -1 0 1
x4 1 -2 -3 2
$c_{j}^1-z_j^{1(1)}$ 0 -2 -1 -4
$d_{j}^1-z_j^{1(2)}$ 3 0 0 -2
$\gamma_j^1$ -12 -4 -2 2
$c_{j}^2-z_j^{2(1)}$ 2 0 -1 -3
$d_{j}^2-z_j^{2(2)}$ 0 -1 0 -1
$\gamma_j^2$ 2 3 -1 3
Table 6.  Simplex table for node 5
B1 x3 x6 x11 Rhs
x10 -3 -1 -2 1
x5 2 0 1 2
x2 -1 0 -1 1
x7 5 0 3 3
x1 3 1 2 0
x8 2 -0 1 0
x4 -6 -3 -5 4
x9 1 0 0 0
$c_{j}^1-z_j^{1(1)}$ -1 -1 -2 -3
$d_{j}^1-z_j^{1(2)}$ 3 0 3 -5
$\gamma_j^1$ -14 -5 -19 3/5
$c_{j}^2-z_j^{2(1)}$ -1 -1 0 -4
$d_{j}^2-z_j^{2(2)}$ 1 0 0 -1
$\gamma_j^2$ -5 -1 0 4
B1 x3 x6 x11 Rhs
x10 -3 -1 -2 1
x5 2 0 1 2
x2 -1 0 -1 1
x7 5 0 3 3
x1 3 1 2 0
x8 2 -0 1 0
x4 -6 -3 -5 4
x9 1 0 0 0
$c_{j}^1-z_j^{1(1)}$ -1 -1 -2 -3
$d_{j}^1-z_j^{1(2)}$ 3 0 3 -5
$\gamma_j^1$ -14 -5 -19 3/5
$c_{j}^2-z_j^{2(1)}$ -1 -1 0 -4
$d_{j}^2-z_j^{2(2)}$ 1 0 0 -1
$\gamma_j^2$ -5 -1 0 4
Table 7.  Computational results
CPU (second) Number of efficient solutions
$ r $ $ n_1+n_2 $ $ m_1+m_2 $ $ n_2 $ $ m_2 $ $ \gamma $ Average [Min; Max] Average [Min; max]
5 10 10 5 5 25 0.016 [0.014; 0.02] 5 [3; 10]
15 10 10 5 25 0.27 [0.15; 0.78] 15.8 [6; 32]
20 10 10 5 25 5.23 [3.4; 8.29] 104.9 [71; 239]
30 20 20 10 15 18.77 [8.33, 40.46] 83.4 [55, 146]
40 30 20 10 11 27.58 [17.97; 52.6] 104.4 [63; 134]
50 40 20 10 9 71.08 [50.35; 98.64] 110.8 [59; 223]
60 50 30 20 7 126.98 [93.53; 269.48] 105.5 [72; 227]
80 70 30 20 5 209.7 [128.76; 331.06] 180.66 [65; 334]
80 70 50 40 5 792.63 [329.1; 2168.79] 137.11 [54; 242]
100 90 10 10 5 2104.15 [1229.6; 3057.79] 491.5 [305; 724]
100 90 50 40 5 3489.28 [2302.11; 6451.55] 187.83 [113; 298]
7 10 10 5 5 25 0.015 [0.012; 0.018] 4.9 [3; 6]
15 10 10 5 25 0.23 [0.14; 0.4] 15.4 [6; 31]
20 10 10 5 25 6.9 [3.88; 15.41] 194.8 [75; 333]
30 20 20 10 15 18.48 [10.13; 32.02] 138.3 [59; 222]
40 30 20 10 11 32.9 [23.57; 53.93] 237.8 [195; 344]
50 40 20 10 9 82.9 [67.17; 107.73] 307.5 [214; 433]
60 50 30 20 7 134.78 [77.19; 216.75] 247.83 [212; 329]
80 70 30 20 5 181.77 [135.29; 296.17] 350.4 [160; 558]
80 70 50 40 5 499.97 [354.92; 1870.7] 251.2 [113; 418]
100 90 10 10 5 2620.26 [2249.86; 3541.75] 1735.16 [1224; 2397]
100 90 50 40 5 3411.6 [2377.67; 4353.41] 820.16 [396; 1575]
10 10 10 5 5 25 0.017 [0.015; 0.021] 5.1 [2; 9]
15 10 10 5 25 0.3 [0.16; 0.5] 23.2 [12; 40]
20 10 10 5 25 4.93 [3.72; 8.34] 234.2 [98; 387]
30 20 20 10 15 19.99 [8.84; 37.86] 184.8 [67; 302]
40 30 20 10 11 36.23 [27.71; 53.93] 299.4 [199; 521]
50 40 20 10 9 88.89 [71.16; 119.92] 430.1 [316; 670]
60 50 30 20 7 126.72 [102.6; 208.27] 337.33 [207; 490]
80 70 30 20 5 188.77 [120.93; 242.56] 609.3 [364; 785]
80 70 50 40 5 1337.65 [389.68; 2891] 409.5 [196; 585]
100 90 10 10 5 2740.08 [1946.76; 3285.76] 2672.16 [1967; 3219]
100 90 50 40 5 4797.08 [2603.65; 6292.14] 1453.5 [933; 1749]
CPU (second) Number of efficient solutions
$ r $ $ n_1+n_2 $ $ m_1+m_2 $ $ n_2 $ $ m_2 $ $ \gamma $ Average [Min; Max] Average [Min; max]
5 10 10 5 5 25 0.016 [0.014; 0.02] 5 [3; 10]
15 10 10 5 25 0.27 [0.15; 0.78] 15.8 [6; 32]
20 10 10 5 25 5.23 [3.4; 8.29] 104.9 [71; 239]
30 20 20 10 15 18.77 [8.33, 40.46] 83.4 [55, 146]
40 30 20 10 11 27.58 [17.97; 52.6] 104.4 [63; 134]
50 40 20 10 9 71.08 [50.35; 98.64] 110.8 [59; 223]
60 50 30 20 7 126.98 [93.53; 269.48] 105.5 [72; 227]
80 70 30 20 5 209.7 [128.76; 331.06] 180.66 [65; 334]
80 70 50 40 5 792.63 [329.1; 2168.79] 137.11 [54; 242]
100 90 10 10 5 2104.15 [1229.6; 3057.79] 491.5 [305; 724]
100 90 50 40 5 3489.28 [2302.11; 6451.55] 187.83 [113; 298]
7 10 10 5 5 25 0.015 [0.012; 0.018] 4.9 [3; 6]
15 10 10 5 25 0.23 [0.14; 0.4] 15.4 [6; 31]
20 10 10 5 25 6.9 [3.88; 15.41] 194.8 [75; 333]
30 20 20 10 15 18.48 [10.13; 32.02] 138.3 [59; 222]
40 30 20 10 11 32.9 [23.57; 53.93] 237.8 [195; 344]
50 40 20 10 9 82.9 [67.17; 107.73] 307.5 [214; 433]
60 50 30 20 7 134.78 [77.19; 216.75] 247.83 [212; 329]
80 70 30 20 5 181.77 [135.29; 296.17] 350.4 [160; 558]
80 70 50 40 5 499.97 [354.92; 1870.7] 251.2 [113; 418]
100 90 10 10 5 2620.26 [2249.86; 3541.75] 1735.16 [1224; 2397]
100 90 50 40 5 3411.6 [2377.67; 4353.41] 820.16 [396; 1575]
10 10 10 5 5 25 0.017 [0.015; 0.021] 5.1 [2; 9]
15 10 10 5 25 0.3 [0.16; 0.5] 23.2 [12; 40]
20 10 10 5 25 4.93 [3.72; 8.34] 234.2 [98; 387]
30 20 20 10 15 19.99 [8.84; 37.86] 184.8 [67; 302]
40 30 20 10 11 36.23 [27.71; 53.93] 299.4 [199; 521]
50 40 20 10 9 88.89 [71.16; 119.92] 430.1 [316; 670]
60 50 30 20 7 126.72 [102.6; 208.27] 337.33 [207; 490]
80 70 30 20 5 188.77 [120.93; 242.56] 609.3 [364; 785]
80 70 50 40 5 1337.65 [389.68; 2891] 409.5 [196; 585]
100 90 10 10 5 2740.08 [1946.76; 3285.76] 2672.16 [1967; 3219]
100 90 50 40 5 4797.08 [2603.65; 6292.14] 1453.5 [933; 1749]
[1]

Tone-Yau Huang, Tamaki Tanaka. Optimality and duality for complex multi-objective programming. Numerical Algebra, Control and Optimization, 2022, 12 (1) : 121-134. doi: 10.3934/naco.2021055

[2]

Zhiguo Feng, Ka-Fai Cedric Yiu. Manifold relaxations for integer programming. Journal of Industrial and Management Optimization, 2014, 10 (2) : 557-566. doi: 10.3934/jimo.2014.10.557

[3]

Tien-Fu Liang, Hung-Wen Cheng. Multi-objective aggregate production planning decisions using two-phase fuzzy goal programming method. Journal of Industrial and Management Optimization, 2011, 7 (2) : 365-383. doi: 10.3934/jimo.2011.7.365

[4]

Ya Liu, Zhaojin Li. Dynamic-programming-based heuristic for multi-objective operating theater planning. Journal of Industrial and Management Optimization, 2022, 18 (1) : 111-135. doi: 10.3934/jimo.2020145

[5]

Behrouz Kheirfam, Kamal mirnia. Multi-parametric sensitivity analysis in piecewise linear fractional programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 343-351. doi: 10.3934/jimo.2008.4.343

[6]

Zhenbo Wang, Shu-Cherng Fang, David Y. Gao, Wenxun Xing. Global extremal conditions for multi-integer quadratic programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 213-225. doi: 10.3934/jimo.2008.4.213

[7]

Yue Zheng, Zhongping Wan, Shihui Jia, Guangmin Wang. A new method for strong-weak linear bilevel programming problem. Journal of Industrial and Management Optimization, 2015, 11 (2) : 529-547. doi: 10.3934/jimo.2015.11.529

[8]

Azam Moradi, Jafar Razmi, Reza Babazadeh, Ali Sabbaghnia. An integrated Principal Component Analysis and multi-objective mathematical programming approach to agile supply chain network design under uncertainty. Journal of Industrial and Management Optimization, 2019, 15 (2) : 855-879. doi: 10.3934/jimo.2018074

[9]

Charles Fefferman. Interpolation by linear programming I. Discrete and Continuous Dynamical Systems, 2011, 30 (2) : 477-492. doi: 10.3934/dcds.2011.30.477

[10]

Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353

[11]

Behrouz Kheirfam. Multi-parametric sensitivity analysis of the constraint matrix in piecewise linear fractional programming. Journal of Industrial and Management Optimization, 2010, 6 (2) : 347-361. doi: 10.3934/jimo.2010.6.347

[12]

Jean Creignou, Hervé Diet. Linear programming bounds for unitary codes. Advances in Mathematics of Communications, 2010, 4 (3) : 323-344. doi: 10.3934/amc.2010.4.323

[13]

Yi Xu, Wenyu Sun. A filter successive linear programming method for nonlinear semidefinite programming problems. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 193-206. doi: 10.3934/naco.2012.2.193

[14]

Rui Qian, Rong Hu, Ya-Ping Fang. Local smooth representation of solution sets in parametric linear fractional programming problems. Numerical Algebra, Control and Optimization, 2019, 9 (1) : 45-52. doi: 10.3934/naco.2019004

[15]

Yibing Lv, Tiesong Hu, Jianlin Jiang. Penalty method-based equilibrium point approach for solving the linear bilevel multiobjective programming problem. Discrete and Continuous Dynamical Systems - S, 2020, 13 (6) : 1743-1755. doi: 10.3934/dcdss.2020102

[16]

Le Thi Hoai An, Tran Duc Quynh, Pham Dinh Tao. A DC programming approach for a class of bilevel programming problems and its application in Portfolio Selection. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 167-185. doi: 10.3934/naco.2012.2.167

[17]

Mahmoud Ameri, Armin Jarrahi. An executive model for network-level pavement maintenance and rehabilitation planning based on linear integer programming. Journal of Industrial and Management Optimization, 2020, 16 (2) : 795-811. doi: 10.3934/jimo.2018179

[18]

Elham Mardaneh, Ryan Loxton, Qun Lin, Phil Schmidli. A mixed-integer linear programming model for optimal vessel scheduling in offshore oil and gas operations. Journal of Industrial and Management Optimization, 2017, 13 (4) : 1601-1623. doi: 10.3934/jimo.2017009

[19]

Edward S. Canepa, Alexandre M. Bayen, Christian G. Claudel. Spoofing cyber attack detection in probe-based traffic monitoring systems using mixed integer linear programming. Networks and Heterogeneous Media, 2013, 8 (3) : 783-802. doi: 10.3934/nhm.2013.8.783

[20]

Mahdi Roozbeh, Saman Babaie–Kafaki, Zohre Aminifard. Two penalized mixed–integer nonlinear programming approaches to tackle multicollinearity and outliers effects in linear regression models. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3475-3491. doi: 10.3934/jimo.2020128

2021 Impact Factor: 1.411

Metrics

  • PDF downloads (131)
  • HTML views (106)
  • Cited by (0)

Other articles
by authors

[Back to Top]