A reference direction approach to multiple objective quadratic-linear programming

In this paper, we propose an interactive procedure for solving multiple criteria problems with one quadratic objective, several linear objectives, and a set of linear constraints. The procedure is based on the use of reference directions and weighted sums. Reference directions for the linear functions, and weighted sums for combining the quadratic function with the linear ones are used as parameters to implement the free search of nondominated solutions. The idea leads to the parametric linear complementarity problem formulation. An approach to deal with this type of problems is given as well. The approach is illustrated with a numerical example.     

An exact method for computing the nadir values in multiple objective linear programming

In this paper we propose a new method to determine the exact nadir (minimum) criterion values over the efficient set in multiple objective linear programming (MOLP). The basic idea of the method is to determine, for each criterion, the region of the weight space associated with the efficient solutions that have a value in that criterion below the minimum already known (by default, the minimum in the payoff table). If this region is empty, the nadir value has been found. Otherwise, a new efficient solution is computed using a weight vector picked from the delimited region and a new iteration is performed. The method is able to find the nadir values in MOLP problems with any number of objective functions, although the computational effort increases significantly with the number of objectives. Computational experiments are described and discussed, comparing two slightly different versions of the method.     

Using objective values to start multiple objective linear programming algorithms

We introduce in this paper a new starting mechanism for multiple-objective linear programming (MOLP) algorithms. This makes it possible to start an algorithm from any solution in objective space. The original problem is first augmented in such a way that a given starting solution is feasible. The augmentation is explicitly or implicitly controlled by one parameter during the search process, which verifies the feasibility (efficiency) of the final solution. This starting mechanism can be applied either to traditional algorithms, which search the exterior of the constraint polytope, or to algorithms moving through the interior of the constraints. We provide recommendations on the suitability of an algorithm for the various locations of a starting point in objective space. Numerical considerations illustrate these ideas.     

On duality in multiple objective linear programming

In this paper we present two approaches to duality in multiple objective linear programming. The first approach is based on a duality relation between maximal elements of a set and minimal elements of its complement. It offers a general duality scheme which unifies a number of known dual constructions and improves several existing duality relations. The second approach utilizes polarity between a convex polyhedral set and the epigraph of its support function. It leads to a parametric dual problem and yields strong duality relations, including those of geometric duality.     

On multiple objective programming problems with set functions

The convexity of a subset of a σ-algebra and the convexity of a set function on a convex subset are defined. Related properties are also examined. A Farkas-Minkowski theorem for set functions is then proved. These results are used to characterize properly efficient solutions for multiple objective programming problems with set functions by associated scalar problems.     

Analysis of the objective space in multiple objective linear programming

A multiple objective linear program is defined by a matrix C consisting of the coefficients of the linear objectives and a convex polytope X defined by the linear constraints. An analysis of the objective space Y = C[X] for this problem is presented. A characterization between a face of Y and the corresponding faces of X is obtained. This result gives a necessary and sufficient condition for a face to be efficient. The theory and examples demonstrate the collapsing (simplification) that occurs in mapping X to Y. These results form a basis for a new approach to analyzing multiple objective linear programs.     

Constrained optimization using multiple objective programming

In practical applications of mathematical programming it is frequently observed that the decision maker prefers apparently suboptimal solutions. A natural explanation for this phenomenon is that the applied mathematical model was not sufficiently realistic and did not fully represent all the decision makers criteria and constraints. Since multicriteria optimization approaches are specifically designed to incorporate such complex preference structures, they gain more and more importance in application areas as, for example, engineering design and capital budgeting. The aim of this paper is to analyze optimization problems both from a constrained programming and a multicriteria programming perspective. It is shown that both formulations share important properties, and that many classical solution approaches have correspondences in the respective models. The analysis naturally leads to a discussion of the applicability of some recent approximation techniques for multicriteria programming problems for the approximation of optimal solutions and of Lagrange multipliers in convex constrained programming. Convergence results are proven for convex and nonconvex problems.     

Local search in a quadratic-linear bilevel programming problem

A quadratic-linear bilevel programming problem is considered. Its optimistic statement is reduced to a nonconvex mathematical programming problem with a quadratic-bilinear structure. An approximate algorithm of a local search in the problem obtained is proposed, proved, and tested.     

On nonlinear multiple objective fractional programming involving semilocally type-I univex functions

The aim of this paper is to obtain sufficient optimality conditions for a nonlinear multiple objective fractional programming problem involving semilocally type-I univex and related functions. Furthermore, a general dual is formulated and duality results are proved under the assumptions of generalized semilocally type-I univex and related functions. Our results generalize several known results in the literature.     

A converse duality theorem in multiple objective programming

Recently the author has given a duality theorem in multiple objective programming relating properly efficient solutions of the primal and dual problems. In this note the converse of that theorem is given showing that, under certain assumptions, a properly efficient solution of the dual is also a properly efficient solution of the primal.     

Comparative studies in interactive multiple objective mathematical programming

In the past two decades, there has been a significant increase in the number of interactive algorithms proposed for solving multiple objective mathematical programming (MOMP) problems. Most of these procedures have neither been tested in real decision making situations, nor compared to each other. In this study, we emphasize the importance of comparative studies of interactive MOMP procedures and present a state of the art review. Our scope is limited to the comparisons of interactive procedures for solving deterministic, linear, integer or nonlinear constrained multiple objective optimization problems involving a single decision maker.     

Optimality for nonsmooth fractional multiple objective programming

In this study the necessary and sufficient optimality conditions for nonsmooth fractional multiple objective optimization problems are provided. Our idea is based on using the properties of limiting subdifferential vectors in nonsmooth analysis and a separation theorem in convex analysis.     

Goal programming using multiple objective tabu search

Goal programming (GP) is one of the most commonly used mathematical programming tools to model multiple objective optimisation (MOO) problems. There are numerous MOO problems of various complexity modelled using GP in the literature. One of the main difficulties in the GP is to solve their mathematical formulations optimally. Due to difficulties imposed by the classical solution techniques there is a trend in the literature to solve mathematical programming formulations including goal programmes, using the modern heuristics optimisation techniques, namely genetic algorithms (GA), tabu search (TS) and simulated annealing (SA). This paper uses the multiple objective tabu search (MOTS) algorithm, which was proposed previously by the author to solve GP models. In the proposed approach, GP models are first converted to their classical MOO equivalent by using some simple conversion procedures. Then the problem is solved using the MOTS algorithm. The results obtained from the computational experiment show that MOTS can be considered as a promising candidate tool for solving GP models.     

Linear complementarity problems and multiple objective programming

An equivalence is demonstrated between solving a linear complementarity problem with general data and finding a certain subset of the efficient points of a multiple objective programming problem. A new multiple objective programming based approach to solving linear complementarity problems is presented. Results on existence, uniqueness and computational complexity are included.     

Selecting tolerances in chance-constrained programming: A multiple objective linear programming approach

An importance issue concerning the practical application of chance-constrained programming is the lack of a rational method for choosing risk levels or tolerances on the chance constraints. While there has also been much recent debate on the relationship, equivalence, usefulness, and other characteristics of chance-constrained programming relative to stochastic programming with recourse, this paper focuses on the problem of improving the selection of tolerances within the chance-constrained framework. An approach is presented, based on multiple objective linear programming, which allows the decision maker to be more involved in the tolerance selection process, but does not demand a priori decisions on appropriate tolerances. An example is presented which illustrates the approach.     

Linear programming with a possibilistic objective function

This paper proposes some ways for dealing with a linear program when the coefficients of the objective function are subject to possibilistic imprecision, i.e. they are characterized by fuzzy restrictions. Emphasis is placed upon a passive approach that yields a satisfying solution via an appropriate semi-infinite program, and an active one that allows to reach a solution with a high possibility level of optimality. Extensions to the possibilistic constraints case and to the case of multiple-objective programming problems with possibilistic coefficients are also hinted. We end up with some concluding remarks and indicate axes for further developments.     

Steepest ascent algorithms for nonconical multiple objective programming

A steepest ascent family of algorithms suitable for the direct solution of continuous variable unconstrained nonconical multiple objective programming problems is introduced. Nonconical multiple objective problems, unlike standard (conical) vector optimization problems, cannot be easily solved by examining related single objective problems. The concept of a direction of steepest ascent is generalized to the multiple objective context and the question of algorithmic convergence is treated. A computational example involving a nonconical unanimity order is given.     

Interactive multiple objective programming subject to flexible constraints

An interactive decision support system is introduced which aids in solving multiple objective programming problems subject to strict and flexible constraints. Integral part is an extension of a well-known fuzzy sets approach evaluating possible solutions by their degrees of membership to objectives and constraints. This approach is linked to classical multiple objective programming models. If the decision maker cannot determine membership functions a priori the system suggests functions dependent on the given information and interactive modifications are allowed.     

Goal programming using multiple objective hybrid metaheuristic algorithm

In this paper, a Goal Programming (GP) model is converted into a multi-objective optimization problem (MOO) of minimizing deviations from fixed goals. To solve the resulting MOO problem, a hybrid metaheuristic with two steps is proposed to find the Pareto set's solutions. First, a Record-to-Record Travel with an adaptive memory is used to find first non-dominated Pareto frontier solutions preemptively. Second, a Variable Neighbour Search technique with three transformation types is used to intensify every non dominated solution found in the first Pareto frontier to produce the final Pareto frontier solutions. The efficiency of the proposed approach is demonstrated by solving two nonlinear GP test problems and three engineering design problems. In all problems, multiple solutions to the GP problem are found in one single simulation run. The results prove that the proposed algorithm is robust, fast and simply structured, and manages to find high-quality solutions in short computational times by efficiently alternating search diversification and intensification using very few user-defined parameters.     

On degeneracy and collapsing in the construction of the set of objective values in a multiple objective linear program

In this paper an algorithm is developed to generate all nondominated extreme points and edges of the set of objective values of a multiple objective linear program. The approach uses simplex tableaux but avoids generating unnecessary extreme points or bases of extreme points. The procedure is based on, and improves, an algorithm Dauer and Liu developed for this problem. Essential to this approach is the work of Gal and Kruse on the neighborhood problem of determining all extreme points of a convex polytope that are adjacent to a given (degenerate) extreme point of the set. The algorithm will incorporate Gal's degeneracy graph approach to the neighborhood problem with Dauer's objective space analysis of multiple objective linear programs.