A linear programming approach to test efficiency in multi-objective linear fractional programming problems

In a multi-objective linear fractional programming problem (MOLFPP), it is often useful to check the efficiency of a given feasible solution, and if the solution is efficient, it is useful to check strong or weak efficiency. In this paper, by applying a geometrical interpretation, a linear programming approach is achieved to test weak efficiency. Also, in order to test strong efficiency for a given weakly efficient point, a linear programming approach is constructed.     

Solving multi-level multi-objective linear programming problems through fuzzy goal programming approach

In this paper, two new algorithms are presented to solve multi-level multi-objective linear programming (ML-MOLP) problems through the fuzzy goal programming (FGP) approach. The membership functions for the defined fuzzy goals of all objective functions at all levels are developed in the model formulation of the problem; so also are the membership functions for vectors of fuzzy goals of the decision variables, controlled by decision makers at the top levels. Then the fuzzy goal programming approach is used to achieve the highest degree of each of the membership goals by minimizing their deviational variables and thereby obtain the most satisfactory solution for all decision makers.     

Isolated efficiency in nonsmooth semi-infinite multi-objective programming

ABSTRACT

In this paper, isolated efficient solutions of a given nonsmooth Multi-Objective Semi-Infinite Programming problem (MOSIP) are studied. Two new Data Qualifications (DQs) are introduced and it is shown that these DQs are, to a large extent, weaker than already known Constraint Qualifications (CQs). The relationships between isolated efficiency and some relevant notions existing in the literature, including robustness, are established. Various necessary and sufficient conditions for characterizing isolated efficient solutions of a general problem are derived. It is done invoking the tangent cones, the normal cones, the generalized directional derivatives, and some gap functions. Using these characterizations, the (strongly) perturbed Karush-Kuhn-Tucker (KKT) optimality conditions for MOSIP are analyzed. Furthermore, it is shown that each isolated efficient solution is a Geoffrion properly efficient solution under appropriate assumptions. Moreover, Kuhn-Tucker (KT) and Klinger properly efficient solutions for a nonsmooth MOSIP are defined and it is proved that each isolated efficient solution is a KT properly efficient solution in general, and a Klinger properly efficient solution under a DQ. Finally, in the last section, the largest isolated efficiency constant for a given isolated efficient solution is determined.     

Possibility linear programming with trapezoidal fuzzy numbers

Fuzzy linear programming with trapezoidal fuzzy numbers (TrFNs) is considered and a new method is developed to solve it. In this method, TrFNs are used to capture imprecise or uncertain information for the imprecise objective coefficients and/or the imprecise technological coefficients and/or available resources. The auxiliary multi-objective programming is constructed to solve the corresponding possibility linear programming with TrFNs. The auxiliary multi-objective programming involves four objectives: minimizing the left spread, maximizing the right spread, maximizing the left endpoint of the mode and maximizing the middle point of the mode. Three approaches are proposed to solve the constructed auxiliary multi-objective programming, including optimistic approach, pessimistic approach and linear sum approach based on membership function. An investment example and a transportation problem are presented to demonstrate the implementation process of this method. The comparison analysis shows that the fuzzy linear programming with TrFNs developed in this paper generalizes the possibility linear programming with triangular fuzzy numbers.     

Supplier selection and order allocation problem using a two-phase fuzzy multi-objective linear programming

The aim of this paper is to solve a supplier selection problem under multi-price level and multi-product using interactive two-phase fuzzy multi-objective linear programming (FMOLP) model. The proposed model attempts to simultaneously minimize total purchasing and ordering costs, a number of defective units, and late delivered units ordered from suppliers. The piecewise linear membership functions are applied to represent the decision maker’s fuzzy goals for the supplier selection and order allocation problem, and can be resulted in more flexibility via an interactive decision-making process. To demonstrate effectiveness of the proposed model, results of applying the proposed model are shown by a numerical example. The analytical results show that the proposed approach is effective in uncertain environments and provide a reliable decision tool for integrated multi-objective supplier selection problems.     

Robust aspects of solutions in deterministic multiple objective linear programming

We study questions of robustness of linear multiple objective problems in the sense of post-optimal analysis, that is, we study conditions under which a given efficient solution remains efficient when the criteria/objective matrix undergoes some alterations. We consider addition or removal of certain criteria, convex combination with another criteria matrix, or small perturbations of its entries. We provide a necessary and sufficient condition for robustness in a verifiable form and give two formulae to compute the radius of robustness.     

An active-set strategy in an interior point method for linear programming

We will present a potential reduction method for linear programming where only the constraints with relatively small dual slacks—termed active constraints—will be taken into account to form the ellipsoid constraint at each iteration of the process. The algorithm converges to the optimal feasible solution in O( L) iterations with the same polynomial bound as in the full constraints case, wheren is the number of variables andL is the data length. If a small portion of the constraints is active near the optimal solution, the computational cost to find the next direction of movement in one iteration may be considerably reduced by the proposed strategy.This research was partially done in June 1990 while the author was visiting the Department of Mathematics, University of Pisa.     

A multi-objective programming approach to 1.5-dimensional assortment problem

In this paper we study a 1.5-dimensional cutting stock and assortment problem which includes determination of the number of different widths of roll stocks to be maintained as inventory and determination of how these roll stocks should be cut by choosing the optimal cutting pattern combinations. We propose a new multi-objective mixed integer linear programming (MILP) model in the form of simultaneously minimization two contradicting objectives related to the trim loss cost and the combined inventory cost in order to fulfill a given set of cutting orders. An equivalent nonlinear version and a particular case related to the situation when a producer is interested in choosing only a few number of types among all possible roll sizes, have also been considered. A new method called the conic scalarization is proposed for scalarizing non-convex multi-objective problems and several experimental tests are reported in order to demonstrate the validity of the developed modeling and solving approaches.     

Primal and dual multi-objective linear programming algorithms for linear multiplicative programmes

Multiplicative programming problems (MPPs) are global optimization problems known to be NP-hard. In this paper, we employ algorithms developed to compute the entire set of nondominated points of multi-objective linear programmes (MOLPs) to solve linear MPPs. First, we improve our own objective space cut and bound algorithm for convex MPPs in the special case of linear MPPs by only solving one linear programme in each iteration, instead of two as the previous version indicates. We call this algorithm, which is based on Benson’s outer approximation algorithm for MOLPs, the primal objective space algorithm. Then, based on the dual variant of Benson’s algorithm, we propose a dual objective space algorithm for solving linear MPPs. The dual algorithm also requires solving only one linear programme in each iteration. We prove the correctness of the dual algorithm and use computational experiments comparing our algorithms to a recent global optimization algorithm for linear MPPs from the literature as well as two general global optimization solvers to demonstrate the superiority of the new algorithms in terms of computation time. Thus, we demonstrate that the use of multi-objective optimization techniques can be beneficial to solve difficult single objective global optimization problems.     

A primal interior point method for the linear semidefinite programming problem

The linear semidefinite programming problem is examined. A primal interior point method is proposed to solve this problem. It extends the barrier-projection method used for linear programs. The basic properties of the proposed method are discussed, and its local convergence is proved.     

A fuzzy goal programming approach to multi-objective optimization problem with priorities

In goal programming problem, the general equilibrium and optimization are often two conflicting factors. This paper proposes a generalized varying-domain optimization method for fuzzy goal programming (FGP) incorporating multiple priorities. According to the three possible styles of the objective function, the varying-domain optimization method and its generalization are proposed. This method can generate the results consistent with the decision-maker (DM)’s expectation, that the goal with higher priority may have higher level of satisfaction. Using this new method, it is a simple process to balance between the equilibrium and optimization, and the result is the consequence of a synthetic decision between them. In contrast to the previous method, the proposed method can make that the higher priority achieving the higher satisfactory degree. To get the global solution of the nonlinear nonconvex programming problem resulting from the original problem and the varying-domain optimization method, the co-evolutionary genetic algorithms (GAs), called GENOCOPIII, is used instead of the SQP method. In this way the DM can get the optimum of the optimization problem. We demonstrate the power of this proposed method by illustrative examples.     

Improving the rate of convergence of interior point methods for linear programming

This paper proposes a procedure for improving the rate of convergence of interior point methods for linear programming. If (x ^k ) is the sequence generated by an interior point method, the procedure derives an auxiliary sequence ( ). Under the suitable assumptions it is shown that the sequence ( ) converges superlinearly faster to the solution than (x ^k ). Application of the procedure to the projective and afflne scaling algorithms is discussed and some computational illustration is provided.     

Interior point algorithms for linear programming with inequality constraints

Interior methods for linear programming were designed mainly for problems formulated with equality constraints and non-negative variables. The formulation with inequality constraints has shown to be very convenient for practical implementations, and the translation of methods designed for one formulation into the other is not trivial. This paper relates the geometric features of both representations, shows how to transport data and procedures between them and shows how cones and conical projections can be associated with inequality constraints.     

On the number of iterations of Karmarkar's algorithm for linear programming

Karmarkar's algorithm for linear programming was published in 1984, and it is highly important to both theory and practice. On the practical side some of its variants have been found to be far more efficient than the simplex method on a wide range of very large calculations, while its polynomial time properties are fundamental to research on complexity. These properties depend on the fact that each iteration reduces a potential function by an amount that is bounded away from zero, the bound being independent of all the coefficients that occur. It follows that, under mild conditions on the initial vector of variables, the number of iterations that are needed to achieve a prescribed accuracy in the final value of the linear objective function is at most a multiple ofn, wheren is the number of inequality constraints. By considering a simple example that allowsn to be arbitrarily large, we deduce analytically that the magnitude of this complexity bound is correct. Specifically, we prove that the solution of the example by Karmarkar's original algorithm can require aboutn/20 iterations. Further, we find that the algorithm makes changes to the variables that are closely related to the steps of the simplex method.This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.     

On the finite convergence of interior-point algorithms for linear programming

It has been shown [8] that numerous interior-point algorithms for linear programming (LP) generate solution sequences that converge to strict complementarity solutions, or interior solutions on the optimal face. In this note we further establish a theoretical base for Gay's test (Gay, 1989) to identify the optimal face, and develop a new termination procedure to obtain an exact solution on the optimal face. We also report some numerical results for solving a set of LP test problems, each of which has a highly degenerate and unbounded optimal face.Research supported in part by NSF Grant DDM-8922636, The Iowa Business School Summer Grant, and the Interdisciplinary Research Grant of the University of Iowa Center for Advanced Studies.     

Multiple centrality corrections in a primal-dual method for linear programming

A modification of the (infeasible) primal-dual interior point method is developed. The method uses multiple corrections to improve the centrality of the current iterate. The maximum number of corrections the algorithm is encouraged to make depends on the ratio of the efforts to solve and to factorize the KKT systems. For any LP problem, this ratio is determined right after preprocessing the KKT system and prior to the optimization process. The harder the factorization, the more advantageous the higher-order corrections might prove to be.The computational performance of the method is studied on more difficult Netlib problems as well as on tougher and larger real-life LP models arising from applications. The use of multiple centrality corrections gives on the average a 25% to 40% reduction in the number of iterations compared with the widely used second-order predictor-corrector method. This translates into 20% to 30% savings in CPU time.Supported by the Fonds National de la Recherche Scientifique Suisse, Grant #12-34002.92.     

Convex programming with set-inclusive constraints and its applications to generalized linear and fractional programming

Duality results are established in convex programming with the set-inclusive constraints studied by Soyster. The recently developed duality theory for generalized linear programs by Thuente is further generalized and also brought into the framework of Soyster's theory. Convex programming with set-inclusive constraints is further extended to fractional programming.     

On the computation of all supported efficient solutions in multi-objective integer network flow problems

This paper presents a new algorithm for identifying all supported non-dominated vectors (or outcomes) in the objective space, as well as the corresponding efficient solutions in the decision space, for multi-objective integer network flow problems. Identifying the set of supported non-dominated vectors is of the utmost importance for obtaining a first approximation of the whole set of non-dominated vectors. This approximation is crucial, for example, in two-phase methods that first compute the supported non-dominated vectors and then the unsupported non-dominated ones. Our approach is based on a negative-cycle algorithm used in single objective minimum cost flow problems, applied to a sequence of parametric problems. The proposed approach uses the connectedness property of the set of supported non-dominated vectors/efficient solutions to find all integer solutions in maximal non-dominated/efficient facets.     

Deepest point of a polyhedron and linear programming

Abstract

The problem of finding a deepest point (a ball centre) of a polyhedron is studied. A finite combinatorial interior point method is presented for this problem which yields an algorithm for linear programming. We conjecture that this is a strongly polynomial algorithm. Meanwhile developing the algorithm, several auxiliary results were found; among others, Gorokh and Werner’s algorithm for linear inequalities is slightly extended. Our numerical experiments with the problem detected bugs in a linear interior point solver used in MATLAB 6 Optimization Toolbox.