Biobjective optimization over the efficient set of multiobjective integer programming problem

Yasmine Cherfaoui; Mustapha Moulaï

doi:10.3934/jimo.2019102

Article Contents

2021, Volume 17, Issue 1: 117-131. Doi: 10.3934/jimo.2019102

This issue Previous Article A diagonal PRP-type projection method for convex constrained nonlinear monotone equations Next Article Pricing power exchange options with hawkes jump diffusion processes

Biobjective optimization over the efficient set of multiobjective integer programming problem

Yasmine Cherfaoui^1, and
Mustapha Moulaï^2,

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: April 30, 2018

Revised: March 31, 2019

Early access: September 2019

Published: January 2021

Abstract Full Text(HTML) Figure(1) / Table(10) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 90C29, 90C10; Secondary: 90C57.

Citation:

Full Text(HTML)

Figure 1. Search tree of the example

Download: Full-size image PowerPoint slide

Table 1. 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 $

| Show Table

DownLoad: CSV

Table 2. 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 $

| Show Table

DownLoad: CSV

Table 3. 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} $

| Show Table

DownLoad: CSV

Table 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} $

| Show Table

DownLoad: CSV

Table 5. 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} $

| Show Table

DownLoad: CSV

Table 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

| Show Table

DownLoad: CSV

Table 7. 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

| Show Table

DownLoad: CSV

Table 8. 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

| Show Table

DownLoad: CSV

Table 9. 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

| Show Table

DownLoad: CSV

Table 10. Random instances execution times

| Show Table

DownLoad: CSV

Related Papers

Cited by

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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[13]	Y. Yamamoto, Optimization over the efficient set: Overview, J. Global Optim., 22 (2002), 285-317. doi: 10.1023/A:1013875600711.