An L1-norm method for generating all of efficient solutions of multi-objective integer linear programming problem

Multiple criteria decision making suggests, including multiple (two or more) objective functions, a mathematical programming framework. Since most real-life problems include conflicting objectives, multiple objective optimization provides a means for obtaining more realistic models. Multi-objective integer linear programming (MOILP) problem is an important research area as many practical situations require discrete representations by integer variables, and many decision makers have to deal with several objectives (Ulungu and Teghem 1994). Some note-worthy practical environments, where the MOILP problems find their applications, are supply chain design, logistics planning, scheduling, and financial planning. The MOILP problems are theoretically challenging as well, as most of them, even their single objective versions, fall into the class of computationally intractable problems.

Numerous algorithms have been designed to solve an MOILP (Climaco et al. 1997; Rasmussen 1986; Teghem and Kunsch 1986; Ulungu and Teghem 1994) and multiple objective mixed integer linear programs (Mavrotas and Diakoulaki 1998; Sylva and Crema 2007). Klamroth et al. (2004) and Ehrgott (2006) study the general MOIP problem. Klamroth (2004) defined composite functions to obtain upper bounds on the objective function values of the efficient solutions and discussed the use of the upper bounds in generating the efficient set. To form the composite functions, they proposed some classical optimization methods such as cutting plane method and branch and bound algorithm. However, the MOILP have not received the algorithmic attention that continuous problems have. The literature available on this topic is limited.

Using a straightforward theoretical approach, Sylva and Crema's (2004) algorithm enumerates all efficient solutions of MOILP models with bounded feasible regions. Sylva and Crema's (2004) approach solves the problem using a sequence of progressively more constrained integer linear programs and generates a new solution at each step. Starting from an initial efficient solution, Sylva and Crema's (2007) algorithm finds at each iteration a new one that maximizes the infinity-norm distance from the set dominated by the previously found solutions. When all variables are integer and feasible region is bounded, their approach generates the whole set of efficient solutions; and it would be expensive using the method for enumerating the whole set of efficient solutions except for small problems.

However, in some cases, the feasible region of an MOILP problem is unbounded. Therefore, an MOILP problem can have infinite objective values. These cases have not been considered in Sylva and Crema (2004) and (2007). This paper considers the recession direction to the MOILP problem and provides necessary and sufficient conditions to have unbounded feasible region and infinite values of MOILP problem and then extends Jahanshahloo et al. (2004) method to solve an MOILP problem. When the number of efficient solutions of an MOILP problem is finite, the proposed algorithm finds all of the efficient solutions without generating all of the feasible solutions of an MOILP. Using a straightforward theoretical approach, the efficient solutions are found using a sequence of progressively more constrained integer linear programs generating new efficient solutions in any iteration. We prove that all of the optimal solutions of this single objective integer linear programming problem are efficient solutions of an MOILP problem. Therefore, the proposed method reduces the number of constrained problems which are solved.

The paper is organized as follows: Section 2 presents a brief background about MOILP problem. Section 3 introduces modified algorithm for finding all of the efficient solutions of an MOILP problem with bounded or unbounded feasible region. Illustration with some numerical examples is given in Section 4. Finally, the concluding results are presented.

An MOILP problem is a special case of multi-objective program. An MOILP problem with s-objectives is defined as:

where,$C_r=(c_{r1},c_{r2},\cdots ,c_{\mathit{rn}})(r=1,2,\cdots ,s),·A_i=(a_{i1},a_{i2},\cdots ,a_{\mathit{in}})(i=1,2,\cdots ,m),·Z_n^{+}=\left\{(e_1,\cdots ,e_n)|e_j\in Z^{+}=\{0,1,2,\cdots \},j=1,\cdots ,n\right\}andW={(w_1,w_2,\cdots ,w_n)}^T$

The set X, which is defined as follows:

is called the set of feasible solutions of the problem (1). Corresponding to each$W\in X$, the vector Y is defined as follows (Jahanshahloo et al. 2004):

Definition The vector$Y={(y_1,\cdots ,y_s)}^T$ dominates the vector$Y^o={(y_1^o,\cdots ,y_s^o)}^T$ if for each$r\left(r=1,2,\dots ,s\right)\text{,}{y}_r\ge y_r^o$, and there is at least one l such that$y_l>y_l^o$.

Definition Let

$F=\left\{Y|Y={(C_{1}W,C_{2}W,\cdots ,C_{s}W)}^T\text{,}{A}_{i}W\le b_i\text{,}i=1,\cdots ,m\text{,}W\in Z_n^{+}\right\}$. F is called the values space of objective functions in problem (1).

Let$g_r=C_r{W}_r^{*}(r=1,\cdots ,s)$, where$W_r^{*}$ is the optimal solution of$r$^th problem from the following problems (Jahanshahloo et al. 2004):

Definition Let$g={(g_1,g_2,\cdots ,g_s)}^T={(C_1{W}_1^{*},C_2{W}_2^{*},\cdots ,C_s{W}_s^{*})}^T$. The g is called the ideal vector of problem (1) (Jahanshahloo et al. (2004)).

Efficient solutions of MOILP problem

Feasible region of a 0–1 MOILP is bounded. However, an MOILP problem has bounded or unbounded feasible region, which are discussed as follows.

MOILP problem with unbounded feasible region

In some cases, feasible region of an MOILP problem is unbounded. For instance, consider the following MOILP problem.

To explain the unbounded case, we define recession direction for MOILP problems similar to recession direction for linear programming problem (Bazaraa et al. 2007).

Definition: Let$d\ne 0$ and$d\in Z_n^{+}$, then d is a recession direction of the MOILP problem if and only if for all$W\in X$, and for all$\lambda \in Z^{+}$, we have$W+\lambda d\in X$.

Theorem Let$d(\ne 0)$, then d is a recession direction of problem (1) if and only if$\lambda \in Z^{+}$and$W+\lambda d\in X$.

Proof The proof is evident.

Theorem If there is $d(\ne 0)$ such that

with at least one$p(p\in \{1,\cdots ,s\left\}\right)$such that$C_{r}d>0$and$d\in Z_n^{+}$, then the optimal values of the objective functions is infinite, i.e., problem (1) has no efficient solution.

Proof The proof is evident.

Theorem Suppose that for each recession direction of model (1), say$\tilde{d}$, there is$p(p\in \{1,\dots ,s\left\}\right)$such that$C_p\tilde{d}<0$, then model (1) has an efficient solution.

Proof The proof is evident.

MOILP problem with bounded feasible region

This section extends the proposed method in (Jahanshahloo et al. 2004) to find all efficient solutions of MOILP with bounded feasible region. To specify some efficient solutions of model (1), we consider the following theorem for an MOILP problem, which is a modification of Theorem 2.1 in (Jahanshahloo et al. 2004)

Theorem Let $O_l=\{W_{1l}^{*},W_{2l}^{*},\cdots ,W_{\mathit{fl}}^{*}\}$ be the set of optimal solutions of l ^th problem from problems (4), then at least one of these solutions is an efficient solution of problem (1).

Proof The proof is similar to that of Theorem 2.1 in (Jahanshahloo et al. 2004) and is omitted.

Theorem For each$W\in X$as a feasible solution of an MOILP problem with bounded feasible region, the vector$g={(g_1,g_2,\cdots ,g_s)}^T$dominates the vector$Y={(C_{1}W,C_{2}W,\cdots ,C_{s}W)}^T\ne g$.

Proof: See the proof of the Theorem 2.2 in (Jahanshahloo et al. 2004).

As noted in (Jahanshahloo et al. 2004) about a 0–1 MOLP, to find the other efficient solutions of problem (1) with bounded feasible region, we can specify a feasible solution, say$W\in X$, such that$g-Y={(g_1-C_{1}W,g_2-C_{2}W,\cdots ,g_s-C_{s}W)}^T$ is minimized. Therefore, we can solve the following MOILP problem.

where X is a bounded feasible solution of an MOILP problem. Since$\forall W\in X\text{,}$$g_r\ge C_{r}W,(r=1,2,\cdots ,s)$ using L1-norm we have:

To find some other efficient solutions of the MOILP problem, we solve the following linear integer programming problem:

Theorem Each optimal solution of problem (6) is an efficient solution for an MOILP problem.

Proof The proof is similar to that of Theorem 2.3 in (Jahanshahloo et al. 2004) and is omitted. □

As noted about a 0–1 MOILP in (Jahanshahloo et al. 2004), let for each$q\in L_o=\{i_1,i_2,\cdots ,i_{\alpha }\}\subseteq \{1,2,\cdots ,s\}$, the following problem has a unique optimal solution,

Suppose that$G_o=\{W_{i_1}^{*},W_{i_2}^{*},\cdots ,W_{i_{\alpha }}^{*}\}$ is the set of optimal solutions of problem (7). When$G_o$ is empty, we solve problem (6). In this case, let$G_o=\{W_{i_1}^{*},W_{i_2}^{*},\cdots ,W_{i_{\beta }}^{*}\}$ be the set of optimal solutions of problems (6), and$L_o=\{i_1,i_2,\cdots ,i_{\beta }\}$. To find the other efficient solutions of the MOILP problem, for each$q\in L_o$, we add the constraints

to problem (6), where M is a large positive integer number. Therefore, we have

As can be seen, if$t_{\mathit{rq}}=1$, then constraint$C_{r}W>C_r{W}_q^{*}-M{t}_{\mathit{rq}}$is redundant. The constraint${\sum }_{r=1}^s{t}_{\mathit{rq}}\le s-1\text{,}q\in L_o$ implies that at least one of the constraints$C_{r}W>C_r{W}_q^{*}-M{t}_{\mathit{rq}}\text{,}r=1,2,\cdots ,s$ is not redundant (Jahanshahloo et al. 2004). To solve problem (9), the inequalities

should be converted to$\ge$ form. For all$W\in Z_n^{+}$, the values of$C_{r}W\text{,}{C}_r{W}_q^{*}$ and$M{t}_{\mathit{rq}}$ are integers. Therefore,$C_{r}W-(C_r{W}_q^{*}+M{t}_{\mathit{rq}})$ is an integer, and we can add the positive continuous variable, say${\delta }_{\mathit{rq}}$, to the right hand side of the constraint (10). By introducing positive variables${\delta }_{\mathit{rq}}(r=1,\dots ,s\text{,}q\in L_o)$, problem (9) is converted to the following problem:

where$\epsilon$ is a small positive real number.

Theorem Models (9) and (11) are equivalent.

Proof For each$j,r(j=1,\dots ,n\text{,}r=1,\dots ,s)w_j\in Z^{+}$ and$c_{\mathit{rj}}$ is an integer number. Therefore, for each$W\in X\text{,}{\sum }_{r=1}^s{C}_{r}W={\sum }_{r=1}^s{\sum }_{j=1}^n{c}_{\mathit{jr}}{w}_j$ is an integer number. Therefore, difference of the sides of the strictly constraints are integer numbers. Thus, adding${\delta }_{\mathit{rq}}$ (with${\delta }_{\mathit{rq}}\ge \epsilon ,r=1,\dots ,s\text{,}q\in L_o$) to the lower sides of the strictly constraints does not alter the feasible region of model (6). Therefore, models (9) and (11) are equivalent.

Let$A=\{W_{i_{k+1}}^{*},W_{i_{k+2}}^{*},\cdots ,W_{i_{k+l}}^{*}\}$ be the set of optimal solutions of problem (11) where$k=\alpha$ or$k=\beta$. We set$G_1=G_o\cup A$ (Jahanshahloo et al. 2004). To find the other efficient solution of problem (1), for each$W_q^{*}\in A$, we add the following constraints to problem (11):

Finally, problem (11) can be written as follows,

This process is continued until problem (12) became infeasible. As noted in (Jahanshahloo et al. (2004)), if problem (9) or (11) or (12) has an alternative optimal solutions, we have to determine all of them. All of them are efficient solutions of problem (1).

Theorem Each optimal solution of problem (12) is an efficient solution for MOILP problem.

Proof The proof is similar to that of Theorem 2.4 in (Jahanshahloo et al. 2004) and is omitted.

Using the discussions of the previous sections, in the following cases, an MOILP problem has efficient an solution.

1. 1.

   X is nonempty and bounded.

2. 2.

   X is unbounded, and there is no $d\ne 0$ such that $A_{i}d\le 0,i=1,\cdots ,m\text{,}{C}_{r}d\ge 0,r=1,\cdots ,s$ with at least one $p(p\in \{1,\cdots ,s\left\}\right)$ such that $C_{p}d>0$ and $d\in Z_n^{+}\text{.}$

We can modify the proposed algorithm to solve a 0–1 MOILP in Jahanshahloo et al. (2004) to find all of the efficient solutions of MOILP problems with bounded and unbounded feasible regions as follows. When the numbers of efficient solutions are infinite, we can find their subset (for instance see example 3).

The modified algorithm

Stage 0: Solve the system$A_{i}d\le 0\text{,}i=1,\dots ,m\text{,}{C}_r\text{d}\ge 0,\text{r=1,}\dots ,s\text{,}$ with at least one$p(p\in \{1,2,\dots ,s\left\}\right)$ such that$C_{p}d>0$ and$d\in Z_n^{+}\text{.}$ If this system has a solution, then there is no efficient solution for problem (1) and go to stage 3. Otherwise, go to stage 1.

Stage 1:

Step 1.1 Set$k=0$ and solve problem (4) and specify$G_o=\{W_{i_1}^{*},W_{i_2}^{*},\cdots ,W_{i_{\alpha }}^{*}\}\text{.}$ If$G_o$ is empty go to step 1.2, otherwise go to step 1.3,

Step 1.2 Determine all optimal solutions of problem (6) and set$G_o=\{W_{i_1}^{*},W_{i_2}^{*},\cdots ,W_{i_{\beta }}^{*}\}$,

Step 1.3 Determine all optimal solutions of problem (11) and set$A=\{W_{i_{k+1}}^{*},W_{i_{k+2}}^{*},\cdots ,W_{i_{k+l}}^{*}\}$,

Step 1.4 If$A$ is not empty, set$G_1=G_o\cup A$ and go to stage 2. Otherwise, stop; the set$G_o$ is all of the efficient solutions of problem (3),

Stage 2

Step 2.1 Determine all optimal solutions of problem (12), and suppose B is the set of optimal solutions of problem (12),

Step 1.4 If$A$ is not empty, set$G_1=G_o\cup A$ and go to stage 2. Otherwise, stop; the set$G_o$ is all of the efficient solutions of problem (3),

Stage 2:

Step 2.1 Determine all optimal solutions of problem (12), and suppose B is the set of optimal solutions of problem (12),

Step 2.2 If B is not empty, set$G_{k+1}=G_k\cup B$ and go to stage 2.

Otherwise, stop; the set$G_k$ is all of the efficient solutions of problem (1),

Stage 3: End.

Theorem : there is no recession directionLet the number of efficient solutions of an MOILP problem be finite. Then, the modified algorithm generates all of them with bounded or unbounded feasible region.

Proof The feasible region of MOILP problem is bounded or unbounded. Therefore, we can consider the following cases:

1. 1.

   If there is a d such that $A_{i}d\le 0\text{,}i=1,\dots ,m\text{,}{C}_{r}d\ge 0,r=1,\dots ,s\text{,}$ with at least one $p(p\in \{1,2,\dots ,s\left\}\right)$ such that $C_{p}d>0$ and $d\in Z_n^{+}\text{,}$ then feasible region of the MOILP is unbounded, and objective function values can become infinite together. In this case, the algorithm is stopped.

2. 2.

   If X is nonempty and bounded. The proof is similar to that of Theorem 2.5 in (Jahanshahloo et al. 2004).

3. 3.

   If feasible region is unbounded and there is no d such that $A_{i}d\le 0\text{,}i=1,\dots ,m\text{,}{C}_{r}d\ge 0,r=1,\dots ,s\text{,}$ with at least one $p(p\in \{1,2,\dots ,s\left\}\right)$ such that $C_{p}d>0$ and $d\in Z_n^{+}\text{,}$ then objective functions values of the MOILP cannot become infinite together. In this case, in order to prove the theorem by adding the constraint $w_1+w_2+\cdots +w_n\le M$ to problem (11), its feasible region is converted to a bounded feasible region where M is a large positive number. Also, the rest of the proof for this case is similar to that of Theorem 2.5 in (Jahanshahloo et al. 2004) and is omitted.

Theorem Let the number of efficient solutions be finite. Then, the modified algorithm is convergent.

Proof Let the number of efficient solutions be finite. In any iteration, at least one efficient solution is found, and the found efficient solutions are not the same. Therefore, the modified algorithm is convergent.

Examples

This section illustrates the proposed algorithm for the four MOILP problems with bounded or unbounded feasible regions.

Example 1

Consider the following MOILP problem with two objective functions.

As can be seen, there is$d=\left(\begin{array}{l}{d}_1\hfill \\ d_2\hfill \end{array}\right)$ such that$A_{i}d\le 0\text{,}i=1,2\text{,}{C}_{r}d\ge 0,r=1,2$ and$d\in Z_2^{+}\text{,}$ where$A_1=\left(-3,2\right)\text{,}$$A_2=\left(-6,10\right)\text{,}$$C_1=\left(1,1\right)$ and$C_2=\left(4,3\right)$. That is, feasible region is unbounded and objective functions can become infinite together. Therefore, there is no any efficient solution for this problem.

Example 2

The feasible region of the following MOILP problem is unbounded.

As can be seen,$d=\left(\begin{array}{l}{d}_1\hfill \\ d_2\hfill \end{array}\right)=\left(\begin{array}{l}1\hfill \\ 0\hfill \end{array}\right)$ is a solution of the following system,

where$A_1=\left(-1,1\right)\text{,}$$A_2=\left(-4,6\right)\text{,}$$C_1=\left(1,1\right)$ and$C_2=\left(0,-2\right)$. Similar to Example 1, there is no efficient solution for this problem.

Example 3

Consider the following MOILP problem

It is evident that there is d say$d=\left(\begin{array}{l}{d}_1\hfill \\ d_2\hfill \end{array}\right)=\left(\begin{array}{l}1\hfill \\ 1\hfill \end{array}\right)$, such that$A_{i}d\le 0\text{,}i=1,2\text{,}d\in Z_2^{+}$ where$A_1=\left(-4,1\right)\text{,}$$A_2=\left(-9,5\right)\text{.}$ That is, the feasible region of this problem is unbounded. But, there is no recession direction such that,

where$A_1=\left(-1,1\right)\text{,}$$A_2=\left(-4,6\right)\text{,}$$C_1=\left(-2,1\right)$, and$C_2=\left(1,-3\right)\text{.}$ Therefore, this problem has an efficient solution.

Stage 1, Step 1.1: Consider the following single objective integer programming problems:

and

$W_1^{*}=(5,18)$ is the optimal solution of problem (14), and$Y^1={(8,-49)}^T$ is its objective value vector. However, the optimal value of problem (15) is infinite, and this problem does not have an optimal solution. Therefore,$G_o=\left\{1\right\}$.

Step 1.2: The corresponding problem of$G_o=\left\{1\right\}$ is as follows:

$W_2^{*}=(0,0)$ is the optimal solution of problem (16), and$Y^2={(0,0)}^T$ is its objective value vector. Therefore,$A=\left\{\right(0,0\left)\right\}$.

Step 1.3: $G_1=A\cup G_o=\left\{\right(5,18),(0,0\left)\right\}$

Stage 2, Iteration 1

Step 2.1: The corresponding problem of$G_1$ is as follows:

$W_2^{*}=(0,0)$ is the optimal solution of problem (17), and$Y^3={(-2,1)}^T$ is its objective value vector. Thus,$B=\left\{{(1,0)}^T\right\}$.

Iteration 2

Step 2.1: The corresponding problem of$G_1$ is as follows:

$W_4^{*}={(0,1)}^T$ and$W_5^{*}={(2,0)}^T$ are optimal solutions of problem (18). Therefore,$Y^4={(1,-3)}^T$ and$Y^5={(-4,2)}^T$ are its objective value vectors, respectively. Hence,$B=\left\{\right(0,1),(2,0\left)\right\}$.

Using the other single objective integer problems, we find that for each$n\in Z^{+}\text{,}$$W^{*}=(0,n)$ is an efficient solution of problem (13). Hence, the number of the efficient solution of this problem is infinite, and the proposed approach finds at least one of them in any iteration.

Example 4

Consider the following MOILP problem with$s=m=2$ and$n=3$:

As can be seen, there is no$d={\left(d_1,d_2,d_3\right)}^T$ such that$A_{i}d\le 0\text{,}i=1,2$ and$d\in Z_3^{+}\text{,}$ where$A_1=(1,1,1)$ and$A_2=(2,1,-1)$. Therefore, the feasible region is bounded, and the problem has an efficient solution.

Step 1.1: By solving the following problems, the members of$G_o$ are specified.

and

$W_1^{*}={(0,2,0)}^T$ and$W_2^{*}={(0,0,3)}^T$ are the optimal solutions of the above single objective integer problems, respectively, and their objective value vectors are$Y^1={(4,2)}^T$ and$Y^2={(-3,9)}^T$(Figure1). Hence,$G_o=\{{(0,2,0)}^T,{(0,0,3)}^T\}$.

The first two efficient solutions of the MOLP example.

Full size image

Step 1.2: The corresponding problem of$G_o$ is as follows:

By solving the above problem, we have$W_3^{*}={(0,2,1)}^T\text{,}$$W_4^{*}={(1,1,1)}^T$and$A=\{{(0,2,1)}^T,{(1,1,1)}^T\}$. Therefore, the corresponding objective value vectors are$Y^3={(3,5)}^T$ and$Y^4={(2,6)}^T$ (Figure2).

The first two efficient solutions of the MOLP example.

Full size image

Step 1.3:$G_1=A\cup G_o=\{{(0,2,0)}^T,{(0,0,3)}^T,{(0,2,1)}^T,{(1,1,1)}^T\}$

Stage 2, Iteration 1

Step 2.1: The corresponding problem of$G_1$ is as follows:

By solving the above problem, we will have

$W_5^{*}={(0,1,2)}^T$,$W_6^{*}={(1,0,2)}^T\text{,}$$Y^5={(0,7)}^T$,$Y^6={(-1,8)}^T$ (Figure3), and$B=\left\{\right(0,1,2),(1,0,2\left)\right\}$.

The all of efficient solutions of the MOLP example.

Full size image

Step2.2:$G_2=B\cup G_1=\{{(0,2,0)}^T,{(0,0,3)}^T,{(0,2,1)}^T,{(1,1,1)}^T,{(0,1,2)}^T,{(1,0,2)}^T\}$.

Iteration 2

Step 1.1: The corresponding problem of$G_2$ is infeasible. Hence, the members of$G_2$ are efficient solutions for the MOILP example.

This paper considered MOILP problems with bounded and unbounded feasible regions. Then, the proposed method in (Jahanshahloo et al. 2004) has been modified to find all of the efficient solutions of an MOILP problem when the number of efficient solutions is finite. In any iteration of the modified algorithm, at least one efficient solution of an MOILP problem is found. If$W_p^{*}$ and$W_{p+1}^{*}$ are two efficient solutions of an MOILP which have been obtained in$p^{\mathit{th}}$ and${(p+1)}^{\mathit{th}}$ iterations, respectively, then the distance of$Y_p$ is less than$Y_{p+1}$ from$g$ using the$L1$ norm, and the rank of$W_p^{*}$ is higher than$W_{p+1}^{*}$. Therefore, the efficient solutions of the MOILP problem are ranked using the proposed algorithm.

Ghasem Tohidi is currently an Assistance Professor in the Department of Mathematics of Islamic Azad University, Central Tehran Branch. His research interests include Data Envelopment Analysis (DEA), Fuzzy and Multi Objective Programming (MOP). He has published many articles in a number of peer reviewed academic journals and conferences.

Shabnam Razavyan is currently an Assistance Professor in the Department of Mathematics of Islamic Azad University, South Tehran Branch. Her research interests include Data Envelopment Analysis (DEA) and Multi Objective Programming (MOP). She has published many articles in a number of peer reviewed academic journals and conferences. She is a member of the Iranian Operations Research Society.