Nonlinear goal programming using multi-objective genetic algorithms

Goal programming is a technique often used in engineering design activities primarily to find a compromised solution which will simultaneously satisfy a number of design goals. In solving goal programming problems, classical methods reduce the multiple goal-attainment problem into a single objective of minimizing a weighted sum of deviations from goals. This procedure has a number of known difficulties. First, the obtained solution to the goal programming problem is sensitive to the chosen weight vector. Second, the conversion to a single-objective optimization problem involves additional constraints. Third, since most real-world goal programming problems involve nonlinear criterion functions, the resulting single-objective optimization problem becomes a nonlinear programming problem, which is difficult to solve using classical optimization methods. In tackling nonlinear goal programming problems, although successive linearization techniques have been suggested, they are found to be sensitive to the chosen starting solution. In this paper, we pose the goal programming problem as a multi-objective optimization problem of minimizing deviations from individual goals and then suggest an evolutionary optimization algorithm to find multiple Pareto-optimal solutions of the resulting multi-objective optimization problem. The proposed approach alleviates all the above difficulties. It does not need any weight vector. It eliminates the need of having extra constraints needed with the classical formulations. The proposed approach is also suitable for solving goal programming problems having nonlinear criterion functions and having a non-convex trade-off region. The efficacy of the proposed approach is demonstrated by solving a number of nonlinear goal programming test problems and an engineering design problem. In all problems, multiple solutions (each corresponding to a different weight vector) to the goal programming problem are found in one single simulation run. The results suggest that the proposed approach is an effective and practical tool for solving real-world goal programming problems.     

线性等式约束多目标规划的一个降维算法

本文提出具有线性等式约束多目标规划问题的一个降维算法．当目标函数全是二次或线性但至少有一个二次型时，用线性加权法转化原问题为单目标二次规划，再用降维方法转化为求解一个线性方程组．若目标函数非上述情形，首先用线性加权法将原问题转化为具有线性等式约束的非线性规划，然后，对这一非线性规划的目标函数二次逼近，构成线性等式约束二次规划序列，用降维法求解，直到满足精度要求为止．     

Pruned Pareto-optimal sets for the system redundancy allocation problem based on multiple prioritized objectives

In this paper, a new methodology is presented to solve different versions of multi-objective system redundancy allocation problems with prioritized objectives. Multi-objective problems are often solved by modifying them into equivalent single objective problems using pre-defined weights or utility functions. Then, a multi-objective problem is solved similar to a single objective problem returning a single solution. These methods can be problematic because assigning appropriate numerical values (i.e., weights) to an objective function can be challenging for many practitioners. On the other hand, methods such as genetic algorithms and tabu search often yield numerous non-dominated Pareto optimal solutions, which makes the selection of one single best solution very difficult. In this research, a tabu search meta-heuristic approach is used to initially find the entire Pareto-optimal front, and then, Monte-Carlo simulation provides a decision maker with a pruned and prioritized set of Pareto-optimal solutions based on user-defined objective function preferences. The purpose of this study is to create a bridge between Pareto optimality and single solution approaches.     

Two storage inventory model in a mixed environment

Multi-item inventory models with two storage facility and bulk release pattern are developed with linearly time dependent demand in a finite time horizon under crisp, stochastic and fuzzy-stochastic environments. Here different inventory parameters—holding costs, ordering costs, purchase costs, etc.—are assumed as probabilistic or fuzzy in nature. In particular cases stochastic and crisp models are derived. Models are formulated as profit maximization principle and three different approaches are proposed for solution. In the first approach, fuzzy extension principle is used to find membership function of the objective function and then it’s Graded Mean Integration Value (GMIV) for different optimistic levels are taken as equivalent stochastic objectives. Then the stochastic model is transformed to a constraint multi-objective programming problem using Stochastic Non-linear Programming (SNLP) technique. The multi-objective problems are transferred to single objective problems using Interactive Fuzzy Satisfising (IFS) technique. Finally, a Region Reducing Genetic Algorithm (RRGA) based on entropy has been developed and implemented to solve the single objective problems. In the second approach, the above GMIV (which is stochastic in nature) is optimized with some degree of probability and using SNLP technique model is transferred to an equivalent single objective crisp problem and solved using RRGA. In the third approach, objective function is optimized with some degree of possibility/necessity and following this approach model is transformed to an equivalent constrained stochastic programming problem. Then it is transformed to an equivalent single objective crisp problem using SNLP technique and solved via RRGA. The models are illustrated with some numerical examples and some sensitivity analyses have been presented.     

GOSAC: global optimization with surrogate approximation of constraints

We introduce GOSAC, a global optimization algorithm for problems with computationally expensive black-box constraints and computationally cheap objective functions. The variables may be continuous, integer, or mixed-integer. GOSAC uses a two-phase optimization approach. The first phase aims at finding a feasible point by solving a multi-objective optimization problem in which the constraints are minimized simultaneously. The second phase aims at improving the feasible solution. In both phases, we use cubic radial basis function surrogate models to approximate the computationally expensive constraints. We iteratively select sample points by minimizing the computationally cheap objective function subject to the constraint function approximations. We assess GOSAC’s efficiency on computationally cheap test problems with integer, mixed-integer, and continuous variables and two environmental applications. We compare GOSAC to NOMAD and a genetic algorithm (GA). The results of the numerical experiments show that for a given budget of allowed expensive constraint evaluations, GOSAC finds better feasible solutions more efficiently than NOMAD and GA for most benchmark problems and both applications. GOSAC finds feasible solutions with a higher probability than NOMAD and GOSAC.     

A surrogate and Lagrangian approach to constrained network problems

This paper presents the use of surrogate constraints and Lagrange multipliers to generate advanced starting solutions to constrained network problems. The surrogate constraint approach is used to generate a singly constrained network problem which is solved using the algorithm of Glover, Karney, Klingman and Russell [13]. In addition, we test the use of the Lagrangian function to generate advanced starting solutions. In the Lagrangian approach, the subproblems are capacitated network problems which can be solved using very efficient algorithms.The surrogate constraint approach is implemented using the multiplier update procedure of Held, Wolfe and Crowder [16]. The procedure is modified to include a search in a single direction to prevent periodic regression of the solution. We also introduce a reoptimization procedure which allows the solution from thekth subproblem to be used as the starting point for the next surrogate problem for which it is infeasible once the new surrogate constraint is adjoined.The algorithms are tested under a variety of conditions including: large-scale problems, number and structure of the non-network constraints, and the density of the non-network constraint coefficients.The testing clearly demonstrates that both the surrogate constraint and Langrange multipliers generate advanced starting solutions which greatly improve the computational effort required to generate an optimal solution to the constrained network problem. The testing demonstrates that the extra effort required to solve the singly constrained network subproblems of the surrogate constraints approach yields an improved advanced starting point as compared to the Lagrangian approach. It is further demonstrated that both of the relaxation approaches are much more computationally efficient than solving the problem from the beginning with a linear programming algorithm.     

Primal and dual algorithms for optimization over the efficient set

ABSTRACT

Optimization over the efficient set of a multi-objective optimization problem is a mathematical model for the problem of selecting a most preferred solution that arises in multiple criteria decision-making to account for trade-offs between objectives within the set of efficient solutions. In this paper, we consider a particular case of this problem, namely that of optimizing a linear function over the image of the efficient set in objective space of a convex multi-objective optimization problem. We present both primal and dual algorithms for this task. The algorithms are based on recent algorithms for solving convex multi-objective optimization problems in objective space with suitable modifications to exploit specific properties of the problem of optimization over the efficient set. We first present the algorithms for the case that the underlying problem is a multi-objective linear programme. We then extend them to be able to solve problems with an underlying convex multi-objective optimization problem. We compare the new algorithms with several state of the art algorithms from the literature on a set of randomly generated instances to demonstrate that they are considerably faster than the competitors.     

Computing multiobjective Markov chains handled by the extraproximal method

This paper suggests a new method for generating the Pareto front in multi-objective Markov chains, which overcomes some existing drawbacks in multi-objective methods: a fundamental issue is to find strong Pareto policies which are policies whose cost-function value is the closest in Euclidean norm to the utopian point. Each strong Pareto policy is reached when each cost-function, constrained by the strategy of others, cannot improve further its own criterion. Constraints associated to the objective function are implemented formulating the problem as a bi-level optimization approach. We convert the problem into a single level optimization approach by introducing a generalized Lagrangian function to represent the original multi-objective problem in terms of a related nonlinear programming problem. Then, we apply the Tikhonov regularization method to the objective function. The regularization method ensures that all the possible Pareto policies to be generated along the Pareto front are strong Pareto policies. For solving the problem we employ the extra-proximal method. The method effectively approximates to every optimal Pareto point, which in this case is a strong Pareto point, in the Pareto front. The experimental result, applied to the route selection for counter-kidnapping problem, validates the effectiveness and usefulness of the method.     

Multi-objective integer programming: A general approach for generating all non-dominated solutions

In this paper we develop a general approach to generate all non-dominated solutions of the multi-objective integer programming (MOIP) Problem. Our approach, which is based on the identification of objective efficiency ranges, is an improvement over classical ε-constraint method. Objective efficiency ranges are identified by solving simpler MOIP problems with fewer objectives. We first provide the classical ε-constraint method on the bi-objective integer programming problem for the sake of completeness and comment on its efficiency. Then present our method on tri-objective integer programming problem and then extend it to the general MOIP problem with k objectives. A numerical example considering tri-objective assignment problem is also provided.     

An Interactive Heuristic Approach for Multi-Objective Integer-Programming Problems

An interactive approach to solve the multi-objective integer-programming problem heuristically is described. The approach consists of two main parts. The first is an algorithm to guide the search for a set of weights to the objective functions which would produce the solution most preferred by the decision-maker given a linear utility function. The search area is successively decreased through an interaction process, with the decision-maker using a selection and contraction method. During each stage of this algorithm, a number of single integer-programming problems are solved heuristically. The motivation for this approach, along with some computational experimentation, is provided.     

A hybrid approach combining interior-point and branch-and-bound methods applied to the problem of sugar cane waste

This paper proposes a hybrid approach for solving the multi-objective model related to the minimisation of sugar cane waste collection costs and/or the maximisation of produced energy by this waste, with the aid of strategies for solving multi-objective problems, which transform the problem into a set of single-objective problems. This approach combines the predictor-corrector primal-dual interior-point and branch-and-bound methods in order to solve these single-objective problems. The model consists in identifying the sugar cane varieties with the lowest waste collection costs, while simultaneously it aims to obtain the greatest amount of produced energy by this waste. The hybrid methods are implemented in C++ programming language, and tests are performed to determine the efficient solutions in Pareto optimal sense of the multi-objective model and compare the performance of the hybrid method using the integrality test and without considering it. The mathematical results confirm that the proposed hybrid method for solving the aforementioned models presents good computational performance and reliable solutions.     

Optimization Over the Efficient Set of Multi-objective Convex Optimal Control Problems

We consider multi-objective convex optimal control problems. First we state a relationship between the (weakly or properly) efficient set of the multi-objective problem and the solution of the problem scalarized via a convex combination of objectives through a vector of parameters (or weights). Then we establish that (i) the solution of the scalarized (parametric) problem for any given parameter vector is unique and (weakly or properly) efficient and (ii) for each solution in the (weakly or properly) efficient set, there exists at least one corresponding parameter vector for the scalarized problem yielding the same solution. Therefore the set of all parametric solutions (obtained by solving the scalarized problem) is equal to the efficient set. Next we consider an additional objective over the efficient set. Based on the main result, the new objective can instead be considered over the (parametric) solution set of the scalarized problem. For the purpose of constructing numerical methods, we point to existing solution differentiability results for parametric optimal control problems. We propose numerical methods and give an example application to illustrate our approach.     

A nonlinear programming approach for the sliding mode control design

We treat the sliding mode control problem by formulating it as a two phase problem consisting of reaching and sliding phases. We show that such a problem can be formulated as bicriteria nonlinear programming problem by associating each of these phases with an appropriate objective function and constraints. We then scalarize this problem by taking weighted sum of these objective functions. We show that by solving a sequence of such formulated nonlinear programming problems it is possible to obtain sliding mode controller feedback coefficients which yield a competitive performance throughout the control. We solve the nonlinear programming problems so constructed by using the modified subgradient method which does not require any convexity and differentiability assumptions. We illustrate validity of our approach by generating a sliding mode control input function for stabilization of an inverted pendulum.     

Differential evolution framework for big data optimization

During the last two decades, dealing with big data problems has become a major issue for many industries. Although, in recent years, differential evolution has been successful in solving many complex optimization problems, there has been research gaps on using it to solve big data problems. As a real-time big data problem may not be known in advance, determining the appropriate differential evolution operators and parameters to use is a combinatorial optimization problem. Therefore, in this paper, a general differential evolution framework is proposed, in which the most suitable differential evolution algorithm for a problem on hand is adaptively configured. A local search is also employed to increase the exploitation capability of the proposed algorithm. The algorithm is tested on the 2015 big data optimization competition problems (six single objective problems and six multi-objective problems). The results show the superiority of the proposed algorithm to several state-of-the-art algorithms.     

Multi-objective tabu search using a multinomial probability mass function

A tabu search approach to solve multi-objective combinatorial optimization problems is developed in this paper. This procedure selects an objective to become active for a given iteration with a multinomial probability mass function. The selection step eliminates two major problems of simple multi-objective methods, a priori weighting and scaling of objectives. Comparison of results on an NP-hard combinatorial problem with a previously published multi-objective tabu search approach and with a deterministic version of this approach shows that the multinomial approach is effective, tractable and flexible.     

Using the idea of expanded core for the exact solution of bi-objective multi-dimensional knapsack problems

We propose a methodology for obtaining the exact Pareto set of Bi-Objective Multi-Dimensional Knapsack Problems, exploiting the concept of core expansion. The core concept is effectively used in single objective multi-dimensional knapsack problems and it is based on the “divide and conquer” principle. Namely, instead of solving one problem with n variables we solve several sub-problems with a fraction of n variables (core variables). In the multi-objective case, the general idea is that we start from an approximation of the Pareto set (produced with the Multi-Criteria Branch and Bound algorithm, using also the core concept) and we enrich this approximation iteratively. Every time an approximation is generated, we solve a series of appropriate single objective Integer Programming (IP) problems exploring the criterion space for possibly undiscovered, new Pareto Optimal Solutions (POS). If one or more new POS are found, we appropriately expand the already found cores and solve the new core problems. This process is repeated until no new POS are found from the IP problems. The paper includes an educational example and some experiments.     

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.     

Fireworks algorithm framework for Big Data optimization

This paper presents a novel optimization framework based on the Fireworks Algorithm for Big Data Optimization problems. Indeed, the proposed framework is composed of two optimization algorithms. A single objective Fireworks Algorithm and a multi-objective Fireworks Algorithm are proposed for solving the Big Optimization of Signals problem “Big-OPT” which belongs to the Big Data Optimization problems class. The single objective Fireworks Algorithm adopts a modified search mechanism to ensure rapidity and preserve the explorative capacities of the basic Fireworks Algorithm. Afterward, the algorithm is extended to handle multi-objective optimization of Big-OPT with a supplementary special sparks phase and a novel strategy for next generation selection. To validate the performance of the framework, extensive tests on six EEG datasets are performed. The framework is also compared with several approaches from recent state of the art. The study concludes the competitive performance of the proposed framework in comparison with the other techniques reported in this paper.     

Pareto Simulated Annealing for Fuzzy Multi-Objective Combinatorial Optimization

The paper presents a metaheuristic method for solving fuzzy multi-objective combinatorial optimization problems. It extends the Pareto simulated annealing (PSA) method proposed originally for the crisp multi-objective combinatorial (MOCO) problems and is called fuzzy Pareto simulated annealing (FPSA). The method does not transform the original fuzzy MOCO problem to an auxiliary deterministic problem but works in the original fuzzy objective space. Its goal is to find a set of approximately efficient solutions being a good approximation of the whole set of efficient solutions defined in the fuzzy objective space. The extension of PSA to FPSA requires the definition of the dominance in the fuzzy objective space, modification of rules for calculating probability of accepting a new solution and application of a defuzzification operator for updating the average position of a solution in the objective space. The use of the FPSA method is illustrated by its application to an agricultural multi-objective project scheduling problem.     

An objective space cut and bound algorithm for convex multiplicative programmes

Multiplicative programming problems are global optimisation problems known to be NP-hard. In this paper we propose an objective space cut and bound algorithm for approximately solving convex multiplicative programming problems. This method is based on an objective space approximation algorithm for convex multi-objective programming problems. We show that this multi-objective optimisation algorithm can be changed into a cut and bound algorithm to solve convex multiplicative programming problems. We use an illustrative example to demonstrate the working of the algorithm. Computational experiments illustrate the superior performance of our algorithm compared to other methods from the literature.