American Institute of Mathematical Sciences

• Previous Article
Modeling and computation of mean field game with compound carbon abatement mechanisms
• JIMO Home
• This Issue
• Next Article
Dynamic discrete-time portfolio selection for defined contribution pension funds with inflation risk
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, doi: 10.3934/jimo.2019102
References:

show all references

References:
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] Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020054

2019 Impact Factor: 1.366

Tools

Article outline

Figures and Tables