Finding all maximal efficient faces in multiobjective linear programming

An algorithm for finding the whole efficient set of a multiobjective linear program is proposed. From the set of efficient edges incident to a vertex, a characterization of maximal efficient faces containing the vertex is given. By means of the lexicographic selection rule of Dantzig, Orden and Wolfe, a connectedness property of the set of dual optimal bases associated to a degenerate vertex is proved. An application of this to the problem of enumerating all the efficient edges incident to a degenerate vertex is proposed. Our method is illustrated with numerical examples and comparisons with Armand—Malivert's algorithm show that this new algorithm uses less computer time.     

Determining maximal efficient faces in multiobjective linear programming problem

Finding an efficient or weakly efficient solution in a multiobjective linear programming (MOLP) problem is not a difficult task. The difficulty lies in finding all these solutions and representing their structures. Since there are many convenient approaches that obtain all of the (weakly) efficient extreme points and (weakly) efficient extreme rays in an MOLP, this paper develops an algorithm which effectively finds all of the (weakly) efficient maximal faces in an MOLP using all of the (weakly) efficient extreme points and extreme rays. The proposed algorithm avoids the degeneration problem, which is the major problem of the most of previous algorithms and gives an explicit structure for maximal efficient (weak efficient) faces. Consequently, it gives a convenient representation of efficient (weak efficient) set using maximal efficient (weak efficient) faces. The proposed algorithm is based on two facts. Firstly, the efficiency and weak efficiency property of a face is determined using a relative interior point of it. Secondly, the relative interior point is achieved using some affine independent points. Indeed, the affine independent property enable us to obtain an efficient relative interior point rapidly.     

Constructing efficient solutions structure of multiobjective linear programming

It is not a difficult task to find a weak Pareto or Pareto solution in a multiobjective linear programming (MOLP) problem. The difficulty lies in finding all these solutions and representing their structure. This paper develops an algorithm for solving this problem. We investigate the solutions and their relationships in the objective space. The algorithm determines finite number of weights, each of which corresponds to a weighted sum problems. By solving these problems, we further obtain all weak Pareto and Pareto solutions of the MOLP and their structure in the constraint space. The algorithm avoids the degeneration problem, which is a major hurdle of previous works, and presents an easy and clear solution structure.     

Determination of the efficient set in multiobjective linear programming

This paper develops a method for finding the whole set of efficient points of a multiobjective linear problem. Two algorithms are presented; the first one describes the set of all efficient vertices and all efficient rays of the constraint polyhedron, while the second one generates the set of all efficient faces. The method has been tested on several examples for which numerical results are reported.The authors are grateful to Professor W. Stadler and an anonymous referee for their helpful comments and corrections.     

Bilevel programming for generating discrete representations in multiobjective optimization

Mathematical Programming - The solution to a multiobjective optimization problem consists of the nondominated set that portrays all relevant trade-off information. The ultimate goal is to identify...     

A new complexity result on multiobjective linear integer programming using short rational generating functions

This paper presents a new complexity result for solving multiobjective integer programming problems. We prove that encoding the entire set of nondominated solutions of the problem in a short sum of rational functions is polynomially doable, when the dimension of the decision space is fixed. This result extends a previous result presented in De Loera et al. (INFORMS J. Comput. 21(1):39–48, 2009) in that there the number of the objective functions is assumed to be fixed whereas ours allows this number to vary.     

An efficient method for solving linear goal programming problems

This note proposes a solution algorithm for linear goal programming problems. The proposed method simplifies the traditional solution methods. Also, the proposed method is computationally efficient.     

Complexity of necessary efficiency in interval linear programming and multiobjective linear programming

We present some complexity results on checking necessary efficiency in interval multiobjective linear programming. Supposing that objective function coefficients perturb within prescribed intervals, a feasible point x* is called necessarily efficient if it is efficient for all instances of interval data. We show that the problem of checking necessary efficiency is co-NP-complete even for the case of only one objective. Provided that x* is a non-degenerate basic solution, the problem is polynomially solvable for one objective, but remains co-NP-hard in the general case. Some open problems are mentioned at the end of the paper.     

Hierarchical generating method for large-scale multiobjective systems

This paper investigates large-scale multiobjective systems in the context of a general hierarchical generating method which considers the problem of how to find the set of all noninferior solutions by decomposition and coordination. A new, unified framework of the hierarchical generating method is developed by integrating the envelope analysis approach and the duality theory that is used in multiobjective programming. In this scheme, the vector-valued Lagrangian and the duality theorem provide the basis of a decomposition of the overall multiobjective system into several multiobjective subsystems, and the envelope analysis gives an efficient approach to deal with the coordination at a high level. The following decomposition-coordination schemes for different problems are developed: (i) a spatial decomposition and envelope coordination algorithm for large-scale multiobjective static systems; (ii) a temporal decomposition and envelope coordination algorithm for multiobjective dynamic systems; and (iii) a three-level structure algorithm for large-scale multiobjective dynamic systems.This work was supported by NSF Grant No. CEE-82-11606.     

Relations among efficient solutions in uncertain multiobjective programming

Based on uncertainty theory, this work deals with the relations among concepts of efficient solutions for uncertain multiobjective programming (UMOP) problems. Firstly, the UMOP model with uncertain vectors in objective functions is presented. Secondly, seven types of concepts of efficient solutions for the UMOP model, such as expected-value standard-deviation efficiency, expected-value properly efficiency, efficiency with belief degrees etc., are defined. Finally, the relations of these different efficiency concepts, especially the expected-value standard-deviation efficiency and efficiency with belief degrees, are established under certain conditions, and two numerical examples are given to illustrate these theoretical results. Our work helps to determine what types of efficient solutions are obtained by each of these concepts and also provides theoretical foundation for multiple attribute decision-making in uncertain systems.     

Additive and multiplicative tolerance in multiobjective linear programming

We consider a multiobjective linear program. We propose a procedure for computing an additive and multiplicative (percentage) tolerance in which all the objective function coefficients may simultaneously and independently vary while preserving the efficiency of a given solution. For a nondegenerate basic solution, the procedure runs in polynomial time.     

The tolerance approach in multiobjective linear fractional programming

When solving a multiobjective programming problem by the weighted sum approach, weights represent the relative importance associated to the objectives. As these values are usually imprecise, it is important to analyze the sensitivity of the solution under possible deviations on the estimated values. In this sense, the tolerance approach provides a direct measure of how weights may vary simultaneously and independently from their estimated values while still retaining the same efficient solution. This paper provides an explicit expression to the maximum tolerance on weights in a multiobjective linear fractional programming problem when all the denominators are equal. An application is also presented to illustrate how the results may help the decision maker to choose a most satisfactory solution in a production problem.     

Maximal and supremal tolerances in multiobjective linear programming

Let a multiobjective linear programming problem and any efficient solution be given. Tolerance analysis aims to compute interval tolerances for (possibly all) objective function coefficients such that the efficient solution remains efficient for any perturbation of the coefficients within the computed intervals. The known methods either yield tolerances that are not the maximal possible ones, or they consider perturbations of weights of the weighted sum scalarization only. We focus directly on perturbations of the objective function coefficients, which makes the approach independent on a scalarization technique used. In this paper, we propose a method for calculating the supremal tolerance (the maximal one need not exist). The main disadvantage of the method is the exponential running time in the worst case. Nevertheless, we show that the problem of determining the maximal/supremal tolerance is NP-hard, so an efficient (polynomial time) procedure is not likely to exist. We illustrate our approach on examples and present an application in transportation problems. Since the maximal tolerance may be small, we extend the notion to individual lower and upper tolerances for each objective function coefficient. An algorithm for computing maximal individual tolerances is proposed.     

Solving the multiobjective possibilistic linear programming problem

In conventional multiobjective decision making problems, the estimation of the parameters of the model is often a problematic task. Normally they are either given by the decision maker (DM), who has imprecise information and/or expresses his considerations subjectively, or by statistical inference from past data and their stability is doubtful. Therefore, it is reasonable to construct a model reflecting imprecise data or ambiguity in terms of fuzzy sets for which a lot of fuzzy approaches to multiobjective programming have been developed. In this paper we propose a method to solve a multiobjective linear programming problem involving fuzzy parameters (FP-MOLP), whose possibility distributions are given by fuzzy numbers, estimated from the information provided by the DM. As the parameters, intervening in the model, are fuzzy the solutions will be also fuzzy. We propose a new Pareto Optimal Solution concept for fuzzy multiobjective programming problems. It is based on the extension principle and the joint possibility distribution of the fuzzy parameters of the problem. The method relies on α-cuts of the fuzzy solution to generate its possibility distributions. These ideas are illustrated with a numerical example.     

An efficient algorithm for linear programming

A simple but efficient algorithm is presented for linear programming. The algorithm computes the projection matrix exactly once throughout the computation unlike that of Karmarkar’s algorithm where in the projection matrix is computed at each and every iteration. The algorithm is best suitable to be implemented on a parallel architecture. Complexity of the algorithm is being studied.     

A new efficient short-step projective interior point method for linear programming

In this paper, we are interested in the performance of Karmarkar’s projective algorithm for linear programming. We propose a new displacement step to accelerate and improve the convergence of this algorithm. This purpose is confirmed by numerical experimentations showing the efficiency and the robustness of the obtained algorithm over Schrijver’s one for small problem dimensions.     

A combined scalarizing method for multiobjective programming problems

In this paper, a new general scalarization technique for solving multiobjective optimization problems is presented. After studying the properties of this formulation, two problems as special cases of this general formula are considered. It is shown that some well-known methods such as the weighted sum method, the ?$?$-constraint method, the Benson method, the hybrid method and the elastic ?$?$-constraint method can be subsumed under these two problems. Then, considering approximate solutions, some relationships between ε$\epsilon$-(weakly, properly) efficient points of a general (without any convexity assumption) multiobjective optimization problem and ?$?$-optimal solutions of the introduced scalarized problem are achieved.