Solving the bi-objective multi-dimensional knapsack problem exploiting the concept of core

This paper deals with the bi-objective multi-dimensional knapsack problem. We propose the adaptation of the core concept that is effectively used in single-objective multi-dimensional knapsack problems. The main idea of the core concept 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). The quality of the obtained solution can be adjusted according to the size of the core and there is always a trade off between the solution time and the quality of solution. In the specific study we define the core problem for the multi-objective multi-dimensional knapsack problem. After defining the core we solve the bi-objective integer programming that comprises only the core variables using the Multicriteria Branch and Bound algorithm that can generate the complete Pareto set in small and medium size multi-objective integer programming problems. A small example is used to illustrate the method while computational and economy issues are also discussed. Computational experiments are also presented using available or appropriately modified benchmarks in order to examine the quality of Pareto set approximation with respect to the solution time. Extensions to the general multi-objective case as well as to the computation of the exact solution are also mentioned.     

Convergence of stochastic search algorithms to finite size pareto set approximations

In this work we investigate the convergence of stochastic search algorithms toward the Pareto set of continuous multi-objective optimization problems. The focus is on obtaining a finite approximation that should capture the entire solution set in a suitable sense, which will be defined using the concept of ε-dominance. Under mild assumptions about the process to generate new candidate solutions, the limit approximation set will be determined entirely by the archiving strategy. We propose and analyse two different archiving strategies which lead to a different limit behavior of the algorithms, yielding bounds on the obtained approximation quality as well as on the cardinality of the resulting Pareto set approximation.      

Cone contraction and reference point methods for multi-criteria mixed integer optimization

Interactive approaches employing cone contraction for multi-criteria mixed integer optimization are introduced. In each iteration, the decision maker (DM) is asked to give a reference point (new aspiration levels). The subsequent Pareto optimal point is the reference point projected on the set of admissible objective vectors using a suitable scalarizing function. Thereby, the procedures solve a sequence of optimization problems with integer variables. In such a process, the DM provides additional preference information via pair-wise comparisons of Pareto optimal points identified. Using such preference information and assuming a quasiconcave and non-decreasing value function of the DM we restrict the set of admissible objective vectors by excluding subsets, which cannot improve over the solutions already found. The procedures terminate if all Pareto optimal solutions have been either generated or excluded. In this case, the best Pareto point found is an optimal solution. Such convergence is expected in the special case of pure integer optimization; indeed, numerical simulation tests with multi-criteria facility location models and knapsack problems indicate reasonably fast convergence, in particular, under a linear value function. We also propose a procedure to test whether or not a solution is a supported Pareto point (optimal under some linear value function).     

Decomposition methods for polyhedral approximation of the Edgeworth–Pareto hull

In the framework of multiobjective optimization (MOO) techniques, there is a group of methods that attract growing attention. These methods are based on the approximation of the Edgeworth–Pareto hull (EPH), that is, the largest set (in the sense of inclusion) that has the same Pareto frontier as the feasible objective set [1, 2]. The block separable structure of MOO problems is used in this paper to improve the efficiency of EPH approximation methods in the case when EPH is convex. In this case, polyhedral approximation can be applied to EPH. Its practical importance was shown, for example, in [3, 4]. In this paper, a two-level system is considered that consists of an upper (coordinating) level and a finite number of blocks interacting through the upper level. It is assumed that the optimization objectives are related only to the variables of the upper level. The approximation method is based on the polyhedral approximation of EPH for single blocks, followed by the application of these results for approximating the EPH for the whole MOO problem.     

Two-Sided Pareto Front Approximations

A new approach to derive Pareto front approximations with evolutionary computations is proposed here. At present, evolutionary multiobjective optimization algorithms derive a discrete approximation of the Pareto front (the set of objective maps of efficient solutions) by selecting feasible solutions such that their objective maps are close to the Pareto front. However, accuracy of such approximations is known only if the Pareto front is known, which makes their usefulness questionable. Here we propose to exploit also elements outside feasible sets to derive pairs of such Pareto front approximations that for each approximation pair the corresponding Pareto front lies, in a certain sense, in-between. Accuracies of Pareto front approximations by such pairs can be measured and controlled with respect to distance between elements of a pair. A rudimentary algorithm to derive pairs of Pareto front approximations is presented and the viability of the idea is verified on a limited number of test 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.     

Pareto Solutions of Polyhedral-valued Vector Optimization Problems in Banach Spaces

In general Banach spaces, we consider a vector optimization problem (SVOP) in which the objective is a set-valued mapping whose graph is the union of finitely many polyhedra. We establish some results on structure and connectedness of the weak Pareto solution set, Pareto solution set, weak Pareto optimal value set and Pareto optimal value set of (SVOP). In particular, we improve and generalize Arrow, Barankin and Blackwell’s classical results on linear vector optimization problems in Euclidean spaces.     

双目标规划问题的像集与求解

经济管理的决策目标往往与成本、收益相关,双目标规划在经济管理中具有广泛应用.然而,尚缺乏成熟的算法确定双目标规划问题的全部解.给出双目标规划问题像集的一般性确定法,以求其解,为研究目的所在.具体而言,构造一个带等式约束的单目标规划问题,以确定双目标规划问题像集之部分边界,并借助拉格朗日乘子符号判断其单调性,据此确定原问题的帕累托解与弱帕累托解.这相当于提供了一个求解双目标规划问题的一般性框架.     

A variational approach to define robustness for parametric multiobjective optimization problems

In contrast to classical optimization problems, in multiobjective optimization several objective functions are considered at the same time. For these problems, the solution is not a single optimum but a set of optimal compromises, the so-called Pareto set. In this work, we consider multiobjective optimization problems that additionally depend on an external parameter ${\lambda \in \mathbb{R}}$ , so-called parametric multiobjective optimization problems. The solution of such a problem is given by the λ-dependent Pareto set. In this work we give a new definition that allows to characterize λ-robust Pareto points, meaning points which hardly vary under the variation of the parameter λ. To describe this task mathematically, we make use of the classical calculus of variations. A system of differential algebraic equations will turn out to describe λ-robust solutions. For the numerical solution of these equations concepts of the discrete calculus of variations are used. The new robustness concept is illustrated by numerical examples.     

ɛ-Subdifferentials of Set-valued Maps and ɛ-Weak Pareto Optimality for Multiobjective Optimization

In this paper we consider vector optimization problems where objective and constraints are set-valued maps. Optimality conditions in terms of Lagrange-multipliers for an ɛ-weak Pareto minimal point are established in the general case and in the case with nearly subconvexlike data. A comparison with existing results is also given. Our method used a special scalarization function, introduced in optimization by Hiriart-Urruty. Necessary and sufficient conditions for the existence of an ɛ-weak Pareto minimal point are obtained. The relation between the set of all ɛ-weak Pareto minimal points and the set of all weak Pareto minimal points is established. The ɛ-subdifferential formula of the sum of two convex functions is also extended to set-valued maps via well known results of scalar optimization. This result is applied to obtain the Karush–Kuhn–Tucker necessary conditions, for ɛ-weak Pareto minimal points     

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.     

Necessary Optimality Conditions and a New Approach to Multiobjective Bilevel Optimization Problems

Multiobjective optimization problems typically have conflicting objectives, and a gain in one objective very often is an expense in another. Using the concept of Pareto optimality, we investigate a multiobjective bilevel optimization problem (say, P). Our approach consists of proving that P is locally equivalent to a single level optimization problem, where the nonsmooth Mangasarian–Fromovitz constraint qualification may hold at any feasible solution. With the help of a special scalarization function introduced in optimization by Hiriart–Urruty, we convert our single level optimization problem into another problem and give necessary optimality conditions for the initial multiobjective bilevel optimization problem P.     

Multiobjective optimal control of fluid mixing

In this contribution an efficient numerical method to solve multiobjective optimal control problems of fluid flow mixing governed by the advection equation is presented. To obtain well-mixed behavior for non-diffusive processes, the multi-scale mixing of measure introduced in [1] is used in the formulation of the multiobjective optimal control problem. For the approximation of the Pareto set we combine reference point methods with an adjoint based optimization approach. (© 2015 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Obtaining an outer approximation of the efficient set of nonlinear biobjective problems

A new method for obtaining an outer approximation of the efficient set of nonlinear biobjective optimization problems is presented. It is based on the well known ‘constraint method’, and obtains a superset of the efficient set by computing the regions of δ-optimality of a finite number of single objective constraint problems. An actual implementation, which makes use of interval tools, shows the applicability of the method and the computational studies on a set of competitive location problems demonstrate its efficiency. An extended version of this paper, with more comments, details, examples, and references, can be found in Fernández and Tóth [5]. This paper has been supported by the Ministry of Education and Science of Spain under the research project SEJ2005-06273/ECON, in part financed by the European Regional Development Fund (ERDF). Boglárka Tóth—On leave from the Research Group on Artificial Intelligence of the Hungarian Academy of Sciences and the University of Szeged, H-6720 Szeged, Aradi vértanúk tere 1., Hungary.     

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.     

NAUTILUS method: An interactive technique in multiobjective optimization based on the nadir point

Most interactive methods developed for solving multiobjective optimization problems sequentially generate Pareto optimal or nondominated vectors and the decision maker must always allow impairment in at least one objective function to get a new solution. The NAUTILUS method proposed is based on the assumptions that past experiences affect decision makers’ hopes and that people do not react symmetrically to gains and losses. Therefore, some decision makers may prefer to start from the worst possible objective values and to improve every objective step by step according to their preferences. In NAUTILUS, starting from the nadir point, a solution is obtained at each iteration which dominates the previous one. Although only the last solution will be Pareto optimal, the decision maker never looses sight of the Pareto optimal set, and the search is oriented so that (s)he progressively focusses on the preferred part of the Pareto optimal set. Each new solution is obtained by minimizing an achievement scalarizing function including preferences about desired improvements in objective function values. NAUTILUS is specially suitable for avoiding undesired anchoring effects, for example in negotiation support problems, or just as a means of finding an initial Pareto optimal solution for any interactive procedure. An illustrative example demonstrates how this new method iterates.     

Some iterative methods for the solution of a symmetric indefinite KKT system

This paper is concerned with the numerical solution of a Karush–Kuhn–Tucker system. Such symmetric indefinite system arises when we solve a nonlinear programming problem by an Interior-Point (IP) approach. In this framework, we discuss the effectiveness of two inner iterative solvers: the method of multipliers and the preconditioned conjugate gradient method. We discuss the implementation details of these algorithms in an IP scheme and we report the results of a numerical comparison on a set of large scale test-problems arising from the discretization of elliptic control problems. This research was supported by the Italian Ministry for Education, University and Research (MIUR), FIRB Project RBAU01JYPN.     

Constructing a Pareto front approximation for decision making

An approach to constructing a Pareto front approximation to computationally expensive multiobjective optimization problems is developed. The approximation is constructed as a sub-complex of a Delaunay triangulation of a finite set of Pareto optimal outcomes to the problem. The approach is based on the concept of inherent nondominance. Rules for checking the inherent nondominance of complexes are developed and applying the rules is demonstrated with examples. The quality of the approximation is quantified with error estimates. Due to its properties, the Pareto front approximation works as a surrogate to the original problem for decision making with interactive methods.     

Composite Nonsmooth Optimization Using Approximate Generalized Gradient Vectors

A new approximation method is presented for directly minimizing a composite nonsmooth function that is locally Lipschitzian. This method approximates only the generalized gradient vector, enabling us to use directly well-developed smooth optimization algorithms for solving composite nonsmooth optimization problems. This generalized gradient vector is approximated on each design variable coordinate by using only the active components of the subgradient vectors; then, its usability is validated numerically by the Pareto optimum concept. In order to show the performance of the proposed method, we solve four academic composite nonsmooth optimization problems and two dynamic response optimization problems with multicriteria. Specifically, the optimization results of the two dynamic response optimization problems are compared with those obtained by three typical multicriteria optimization strategies such as the weighting method, distance method, and min–max method, which introduces an artificial design variable in order to replace the max-value cost function with additional inequality constraints. The comparisons show that the proposed approximation method gives more accurate and efficient results than the other methods.