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.     

An interactive satisficing method based on alternative tolerance for fuzzy multiple objective optimization

An interactive satisficing method based on alternative tolerance is proposed for fuzzy multiple objective optimization. The new tolerances of the dissatisficing objectives are generated using an auxiliary programming problem. According to the alternative tolerant limits, either the membership functions are changed, or the objective constraints are added. The lexicographic two-phase programming is implemented to find the final solution. The results of the dissatisficing objectives are iteratively improved. The presented method not only acquires the efficient or weak efficient solution of all the objectives, but also satisfies the progressive preference of decision maker. Numerical examples show its power.     

A practical weight sensitivity algorithm for goal and multiple objective programming

This paper presents a weight sensitivity algorithm that can be used to investigate a portion of weight space of interest to the decision maker in a goal or multiple objective programme. The preferential information required from the decision maker is an initial estimate of their starting solution, with an equal weights solution being used as a default if this is not available, and preference information that will define the portion of weight space on which the sensitivity analysis is to be conducted. The different types of preferential information and how they are incorporated by the algorithm are discussed. The output of the algorithm is a set of distinct solutions that characterise the portion of weight space searched. The possible different output requirements of decision makers are detailed in the context of the algorithm.The methodology is demonstrated on two examples, one hypothetical and the other relating to predicting cinema-going behaviour. Conclusions and avenues for future research are given.     

Solving multiple criteria problems by interactive decomposition

An interactive decomposition method is developed for solving the multiple criteria (MC) problem. Based on nonlinear programming duality theory, the MC problem is decomposed into a series of subproblems and relaxed master problems. Each subproblem is a bicriterion problem, and each relaxed master problem is a standard linear program. The prime objective of the decomposition is to simplify and facilitate the process of making preference assessments and tradeoffs across many conflicting objectives. Therefore, the decision-maker's preference function is not assumed to be known explicitly; rather, the decision maker is required to make only limited local preference assessments in the context of feasible and nondominated alternatives. Also, the preference assessments are of the form of ordinal paired comparisons, and in most of them only two criteria are allowed to change their values simultaneously, while the remaining (l–2) criteria are held fixed at certain levels.     

An inexact algorithm for composite nondifferentiable optimization

We describe an inexact version of Fletcher's QL algorithm with second-order corrections for minimizing composite nonsmooth functions. The method is shown to retain the global and local convergence properties of the original version, if the parameters are chosen appropriately. It is shown how the inexact method can be implemented, for the case in which the function to be minimized is an exact penalty function arising from the standard nonlinear programming problem. The method can also be applied to the problems of nonlinearl ₁ - andl -approximation.This research supported in part by the National Science Foundation under Grant DMS-8619903, and by the Air Force Office of Scientific Research under Grant AFOSR-ISSA-870092.     

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.     

Satisfying optimization method based on goal programming for fuzzy multiple objective optimization problem

This paper proposes a satisfying optimization method based on goal programming for fuzzy multiple objective optimization problem. The aim of this presented approach is to make the more important objective achieving the higher desirable satisfying degree. For different fuzzy relations and fuzzy importance, the reformulated optimization models based on goal programming is proposed. Not only the satisfying results of all the objectives can be acquired, but also the fuzzy importance requirement can be simultaneously actualized. The balance between optimization and relative importance is realized. We demonstrate the efficiency, flexibility and sensitivity of the proposed method by numerical examples.     

An algorithm for solving a multiple criteria optimal control problem

An algorithm for finding agood solution for a multiple criteria optimal control problem is given. The criteria are assumed to be ordered according to their importance to the decision-maker. The algorithm consists of successive solutions of single criterion optimal control problems. Other criteria are taken into account by adding constraints to the problem in a systematic manner.     

Pareto memetic algorithm for multiple objective optimization with an industrial application

Multiple objective combinatorial optimization problems are difficult to solve and often, exact algorithms are unable to produce optimal solutions. The development of multiple objective heuristics was inspired by the need to quickly produce acceptable solutions. In this paper, we present a new multiple objective Pareto memetic algorithm called PMS^MO. The PMS^MO algorithm incorporates an enhanced fine-grained fitness assignment, a double level archiving process and a local search procedure to improve performance. The performance of PMS^MO is benchmarked against state-of-the-art algorithms using 0–1 multi-dimensional multiple objective knapsack problem from the literature and an industrial scheduling problem from the aluminum industry.     

A modification of the Geoffrion/Dyer/Feinberg algorithm for finite multi-objective systems

This paper extends the work of Geoffrion et al. from a compact convex action set X to a finite set X. The essential difference is that the line search step in their algorithm is no longer applicable and has to be replaced by a different search procedure. Finite convergence to an optimal solution is guaranteed. Termination decisions and error analysis is also included.     

An interactive evolutionary multi-objective optimization algorithm with a limited number of decision maker calls

This paper presents a preference-based method to handle optimization problems with multiple objectives. With an increase in the number of objectives the computational cost in solving a multi-objective optimization problem rises exponentially, and it becomes increasingly difficult for evolutionary multi-objective techniques to produce the entire Pareto-optimal front. In this paper, an evolutionary multi-objective procedure is combined with preference information from the decision maker during the intermediate stages of the algorithm leading to the most preferred point. The proposed approach is different from the existing approaches, as it tries to find the most preferred point with a limited budget of decision maker calls. In this paper, we incorporate the idea into a progressively interactive technique based on polyhedral cones. The idea is also tested on another progressively interactive approach based on value functions. Results are provided on two to five-objective unconstrained as well as constrained test problems.     

An alternative optimization technique for interval objective constrained optimization problems via multiobjective programming

An alternative optimization technique via multiobjective programming for constrained optimization problems with interval-valued objectives has been proposed. Reduction of interval objective functions to those of noninterval (crisp) one is the main ingredient of the proposed technique. At first, the significance of interval-valued objective functions along with the meaning of interval-valued solutions of the proposed problem has been explained graphically. Generally, the proposed problems have infinitely many compromise solutions. The objective is to obtain one of such solutions with higher accuracy and lower computational effort. Adequate number of numerical examples has been solved in support of this technique.     

A computer graphics-based Decision Support System for multiple objective linear programming

In this paper we propose a computer-graphics based Decision Support System for multiple objective linear programming that builds on the VIG system (Visual Interactive Goal programming). The essential part of the VIG system is Pareto Race, a dynamic and visual approach for exploring the efficient frontier of a multiple objective linear programming problem. Our objective is to extend Pareto Race to large-scale multiple objective linear programming. The approach works with any efficient solutions that are in general not extreme point solutions. Interactive use of computer graphics plays a central role. The approach, the underlying theory, and an illustrative example are described.     

A sparse nonlinear optimization algorithm

One of the most effective numerical techniques for solving nonlinear programming problems is the sequential quadratic programming approach. Many large nonlinear programming problems arise naturally in data fitting and when discretization techniques are applied to systems described by ordinary or partial differential equations. Problems of this type are characterized by matrices which are large and sparse. This paper describes a nonlinear programming algorithm which exploits the matrix sparsity produced by these applications. Numerical experience is reported for a collection of trajectory optimization problems with nonlinear equality and inequality constraints.The authors wish to acknowledge the insightful contributions of Dr. William Huffman.     

A novel elitist multiobjective optimization algorithm: Multiobjective extremal optimization

Recently, a general-purpose local-search heuristic method called extremal optimization (EO) has been successfully applied to some NP-hard combinatorial optimization problems. This paper presents an investigation on EO with its application in numerical multiobjective optimization and proposes a new novel elitist (1 + λ) multiobjective algorithm, called multiobjective extremal optimization (MOEO). In order to extend EO to solve the multiobjective optimization problems, the Pareto dominance strategy is introduced to the fitness assignment of the proposed approach. We also present a new hybrid mutation operator that enhances the exploratory capabilities of our algorithm. The proposed approach is validated using five popular benchmark functions. The simulation results indicate that the proposed approach is highly competitive with the state-of-the-art multiobjective evolutionary algorithms. Thus MOEO can be considered a good alternative to solve numerical multiobjective optimization problems.     

Analysis and simulation of a distribution system for flowers

One of the largest flower auctions in the world is located in the Netherlands. Because of an expected expansion of the auction, the capacity of its distribution system was investigated. Discrete event simulation was applied to study the complex system. The simulation results show that the present system cannot handle the expected expansion. However, the analysis also shows ways for improving the system's efficiency, thereby enlarging its capacity.     

Nonlinear observation via global optimization methods: Measure theory approach

Nonlinear observation methods developed by Galperin (Refs. 1 and 2) and global optimization methods developed by Zheng (Refs. 3 and 4) are coupled to obtain effective procedures for solution of nonlinear observation and identification problems.The work of this author was supported by the Natural Sciences and Engineering Research Council of Canada under Grant No. A3492.     

An exact algorithm for the fixed-charge multiple knapsack problem

We formulate the fixed-charge multiple knapsack problem (FCMKP) as an extension of the multiple knapsack problem (MKP). The Lagrangian relaxation problem is easily solved, and together with a greedy heuristic we obtain a pair of upper and lower bounds quickly. We make use of these bounds in the pegging test to reduce the problem size. We also present a branch-and-bound (B&B) algorithm to solve FCMKP to optimality. This algorithm exploits the Lagrangian upper bound as well as the pegging result for pruning, and at each terminal subproblem solve MKP exactly by invoking MULKNAP code developed by Pisinger [Pisinger, D., 1999. An exact algorithm for large multiple knapsack problems. European Journal of Operational Research 114, 528–541]. As a result, we are able to solve almost all test problems with up to 32,000 items and 50 knapsacks within a few seconds on an ordinary computing environment, although the algorithm remains some weakness for small instances with relatively many knapsacks.     

An RQP algorithm using a differentiable exact penalty function for inequality constrained problems

In this paper we propose a recursive quadratic programming algorithm for nonlinear programming problems with inequality constraints that uses as merit function a differentiable exact penalty function. The algorithm incorporates an automatic adjustment rule for the selection of the penalty parameter and makes use of an Armijo-type line search procedure that avoids the need to evaluate second order derivatives of the problem functions. We prove that the algorithm possesses global and superlinear convergence properties. Numerical results are reported.