ABSTRACT

In this paper we discuss about infeasibility diagnosis and infeasibility resolution, when the constraint method is used for solving multi objective linear programming problems. We propose an algorithm for resolution of infeasibility, which is a combination of interactive, weighting and constraint methods. Numerical examples are provided to illustrate the techniques developed.

1. Introduction

Almost every important real world problem involves more than one objective. The multi objective linear programming (MOLP) problem can be formulated as follows:

(1)

where are n-dimensional vectors, x is an n-dimensional vector, b is an m-dimensional vector and A is an m × n matrix.

Excluding the trivial case in which a point exists in the feasible region which maximizes all objectives simultaneously, we must often propose a compromise solution to decision maker (DM). In the special case, the point that simultaneously maximizes all objectives is called complete optimal solution. In general, such point rarely exists. Thus, instead of complete optimal solution, Pareto optimal solution (POS) is introduced. x^* is a POS for Problem (1.1) if there does not exist another x such that for all i and for at least one.

There are several methods for solving the MOLP Problem (1). By the utility function method [1] we obtain a compromise solution. The weighting method proposed by Kuhn and tucker [2], the constraint method proposed by Haimes et al. [3] and the weighted minimax method proposed by Bowman [4], characterize POSs. Since then, many different approaches are developed for obtaining POSs and for improving the previous methods [5-7]. Also, there are several fuzzy approaches for solving MOLP problems such as [7-9].

In all of the methods and approaches decision maker (DM) has an essential role. However, choosing unsuitable bounds in the constraint method by DM may be occur infeasibility in the problem.

Many published researches have discussed diagnosis of infeasibility, [1,10-13], however, there are few papers deal with infeasibility resolution [14-16]. One of the useful references is [17].

In this paper we use the deletion filter and the elastic filter algorithms for isolating IIS (irreducible infeasible subsystems) in order to diagnose infeasibility. For resolution of infeasibility and obtaining a POS, we propose analgorithm which is a combination of interactive, weighting and constraint methods. Also we recall the fuzzy method of Leon and Liern [14] for repairing the constraint, in order to attain a feasible space.

Section 2 recalls the constraint method for obtaining a POS for the multi objective linear programming problem. Section 3 discuses about infeasibility analysis and recall two useful filters for isolating IIS. The resolution of infeasibility is discussed in Section 4. When the smallest cardinality set of constraints to cover all IISs is singleton, we have a special case of infeasibility. An interactive approach for this case is proposed in Section 4. For the other cases we propose a combination of the weighting method and the constraint method. Finally we recall the approach of Leon and Liern for repairing infeasibility. Numerical examples are provided to illustrate the technique developed in this chapter.

2. Solving MOLP Problems

There are several methods for solving MOLP problems and obtaining the POSs [1]. Among the many possible ways of scalarizing the MOLP, the weighting and the constraint methods are the most famous methods. In  these methods DM should determine the weights and the bounds for every objective, respectively.

In this section we recall the constraint method. However, determining good weights and suitable bounds is a problem for DM. Therefore, we propose a combination method of the weighting and the constraint method.

2.1. The Constraint Method

The constraint method for characterizing POS is to solve the constraint problem formulated by taking one objective as the objective function and letting all the other objective functions be inequality constraints. The constraint problem is defined by

(2)

where ε_i, i = 1, ···, k;; are chosen by DM.

If is a unique optimal solution to Problem (2) for some ε_i, i = 1, ···, k; then x^* is a POS to Problem (1). Conversely, If is a POS of Problem (1), then x^* is an optimal solution of the Problem (2) for some ε_i, i = 1, ···, k;.

Set. Choosing unsuitable ε_i by DM may occur some inconsistency in the constraints and its consequent is or even though and. This inconsistency follows the infeasibility in the problem.

Here for focus on the objectives, we discuss only the case, and suppose that, after repairing S and attaining we have.

2.2. A Combination Method

Sometimes, DM has suitable bounds for some objectives, tentatively, but for the other objectives he or she hasn’t any assessment. Similarly, in weighting method, it’s possible, DM has some weights for comparison of some objectives together, but he or she doesn’t know how to appropriate some weights for the other objectives. In this case the combination of the two methods may be useful.

Consider Problem (1). Suppose DM has some good weights for comparison of and some suitable lower bounds for, where is a partition for. We solve the following problem in order to obtain a POS:

. (3)

Theorem 2.1. If Problem (3) has a unique optimal solution x^*, then x^* is a POS for Problem (1).

Proof: Let (contrary) x^* be inefficient, then there exist, such that for all; , for all;, for some or for some. Thus

contradiction to unique optimality of x^*.

3. Diagnosis of the Infeasibility

All infeasible systems have one or more irreducible infeasible subsystems (IISs) of constraints [18]. An IIS has the property that it is itself infeasible, but any proper subsystem is feasible. An infeasible set of constraints can be rendered feasible by deleting or repairing at least one member of every IIS it contains. Finding the smallest cardinality set of constraints to cover all IISs is known as the minimum-cardinality IIS set-covering problem (MIN IIS COVER) [19].

There are several practical issues related to IIS isolation. An excellent summary of the recently developed algorithmic methods has appeared in [17]. Here we recall the deletion filter and the elastic filter. The deletion filter guarantees the identification of exactly one IIS, but the exiting of the elastic filter is a small infeasible set that is not necessarily an IIS, but it has at least one IIS.

If the number of objectives in Problem (1) is small, it’s better we use deletion filter. Else, we use elastic filter and then use deletion filter on the exiting of elastic filter for obtaining an IIS.

It may be that there are multiple infeasibilities in the model, hence IIS isolation typically is used in a cyclic manner

1) Isolate an IIS;

2) Determine a repair for this IIS;

3) If the model is still infeasible, go to step 1).

3.1. The Deletion Filter

The deletion filter proposed by Chinneck and Dravnieks [18] guarantees the identification of exactly one IIS after a single pass through the set of constraints. This is an essential property possessed by very few of the IIS isolation methods. In the following algorithm, for diagnosis infeasibility of the problems, we use the phase I of the simplex method.

INPUT: an infeasible set of constraints.

For each constraint in the set:

1) Temporarily drop the constraint from the set.

2) Test the feasibility of the reduced set:

IF feasible THEN return dropped constraint to the set.

ELSE (infeasible) drop the constraint permanently.

OUTPUT: constraints constituting a single IIS.

Theorem 3.1: The deletion filter returns exactly one IIS.

Proof: See [18].

3.2. The Elastic Filter

The method originally described by Brown and Graves [20]. A fully elastic program adds nonnegative elastic variables e_i to every constraint and minimizes the summation of these variables as an elastic objective function. This allows finding a feasible solution for the original infeasible model. Namely we solve the following problem:

, (4)

.

The details of the algorithm are shown in the following:

INPUT: an infeasible set of constraints.

1) Make all constraints elastic by incorporating nonnegative elastic variables e_i.

2) Solve the model using the elastic objective function.

3) IF feasible THEN enforce the constraints in which any e_i > 0 by permanently removing, Go to step 2.

ELSE (infeasible) Exit.

OUTPUT: the set of de-elasticized enforced constraints contains at least one IIS.

4. Resolution of the Infeasibility

The second major aspect of infeasibility analysis is the infeasibility resolution to repair the problem to make it feasible. However, most published researches and practice results in recent years have focused on the diagnosis side. Little investigation has been made in infeasibility resolution [13,14,16].

4.1. Resolution of Infeasibility in the Constraint Method

The smallest cardinality set of constraints to cover all IISs is known as the minimum-cardinality IIS set-covering problem (MIN IIS COVER). There are several algorithms for finding MIN IIS COVER [17].

In this paper we concentrate on infeasibility in constraint objectives. In almost all of real problems, the number of objectives is very less than the number of constraints. It is usual that in many problems, MIN IIS COVER for the set of constraint objectives be singleton. For this special case our algorithm proposes an interactive method, and for the other cases we use the combination method mentioned in Section 2.2 or the approach of Leon and Liern (Section 4.2) in order to repair the constraints and resolve infeasibility. Besides, a POS is obtained.

The Combination Algorithm

Consider Problem (2):

1) Solve the Problem, (4):

2) Set,

3) If, there is no infeasibility, solve Problem (2) and STOP.

4) If for some, and t = w, then, however, MIN IIS COVER is singleton, but there is a cycling in the algorithm. Use Leon and Liern method for solving Problem (2).

Else, If for some, and t ≠ w, then MIN IIS COVER is singleton, set w: = t, replace   by in Problem (2), take ε_j from DM, change the role of j and t in Problem (4) and go to Step 1.

5) If and then take from DM and solve Problem (3), STOP.

6) If, then use Leon and Liern method for solving Problem (2).

Example 4.1 Consider the following problem:

Let DM chooses the first objective as the main and ε₂ = 18, ε₃ = 6, ε₄ = 14 as the upper bound of the other objectives. So the problem of finding a POS changes to solving the following problem:

The last problem is infeasible. By solving Problem (4) we obtain, but. Namely MIN IIS COVER is singleton. Thus we take 4x₁ + 4x₂ + 2x₃ ≤ 14 as the main objective. Suppose that DM chooses ε₁ = 14. The new problem is

The last problem has the optimal solution that is a POS for the main problem.

Example 4.2 Consider the following problem:

Let DM choose the first objective as the main and ε₂ = 6, ε₃ = 6, ε₄ = 8, ε₅ = 9 as the bounds of the other objectives.

Solving Problem (3.1) leads to = and. Thus, and i.e. and according to our algorithm, we must solve Problem (2.2). Let DM choose w₁ = 0.5, w₂ = 0.2, w₄ = 0.3. Therefore, we have the following numerical form of Problem (2.2):

.

The optimal solution is again = .

4.2. Resolution of Infeasibility by Fuzzy Approach

In this section we recall the fuzzy method proposed by Leon and Liern [14] for repairing the constraints in order to resolve infeasibility.

The main idea is that the fuzzy membership function expresses the degree to which a particular point satisfies a given constraint. The membership function makes use of Roodman’s limits [13]. The method is stated as follows:

So as to obtain a feasible solution, let us reformulate the system

, (5)

As the fuzzy case

(6)

Assume that denote the fuzzy constraints by and their membership functions by, respectively. The construction of the membership function by Roodman’s approach is based on Phase I problem (PI) associated System (5) and its dual (DPI). These problems can be stated as follows:

(PI)

, where s and r are surplus and artificial vectors, respectively.

(DPI)

where are the elements of.

Let z^* be the optimal value of (PI) and , be the optimal solution of (DPI). Since system (5) is infeasible, then. For

set

if and p_i = 0 if. The values of p_i s are called the Rood man lower bounds. Consider the following membership function:

(7)

for.

Define the fuzzy set of feasible solutions of system (4.1) as where

.

The solution with the highest degree of membership is given by

.

So we solve the auxiliary crisp problem:

(AP)

The next theorem proves that (AP) has feasible solution and provides a lower bound for objective function value.

Theorem 4.1. (AP) is feasible and its optimal value α^* verifies that, where k is the number of nonnull shadow prices of (PI).

Proof: see [14].

In fact β^* = 1 – α^* is the degree of feasibility.

Example 4.3. Consider Problem 4.2. Let DM choose the first objective as the main with the same value for the bounds of the other objectives. As mentioned in Example 4.2, the problem is infeasible.

Solving (PI) and (DPI) lead to z^* = 4.25, =1, = 0, = 1, = 0.25. Therefore, p₂ = 4.25, p₃ = 0, p₄ = 4.25, p₅ = 17. So we must solve the following problem:

The optimal solution is with α^* = 0.5647.

In order to compare the obtained solutions by two methods described in Examples 4.2 and 4.3, we compute the satisfaction degree of the objectives with the membership functions in equations (4.3). The results are summarized in the following Table 1.

According to Table 1, the summation of satisfaction degree in our algorithm is better than the Leon and Liern method, however, the minimum degree in the Leon and Liern method is better.

5. Conclusion

In this paper we discussed about infeasibility, diagnosis

and resolution, when we used the constraint method for solving multi objective linear programming. We used elastic filter and deletion filter for finding IIS. We proposed a combination method for obtaining POSs. In the interest of repairing the constraint objectives, and for resolution of infeasibility, we proposed an algorithm, which was a combination of interactive, weighting sum and constraint method. We solved some numerical examples and compared our method with Leon and Liern method.

REFERENCES