Search

A new exact algorithm for bi-objective linear integer problems is presented, based on the classic - constraint method and algebraic test sets for single-objective linear integer problems. Our method pro- vides the complete Pareto frontier N of non-dominated points and, for this purpose, it considers exactly |N | single-objective problems by using reduction with test sets instead of solving with an optimizer. Al- though we use Gröbner bases for the computation of test sets, which may provoke a bottleneck in princi- ple, the computational results are shown to be promising, especially for unbounded knapsack problems,for which any usual branch-and-cut strategy could be much more expensive. Nevertheless, this algorithmcan be considered as a potentially faster alternative to IP-based methods when test sets are available. Ministerio de Economía y Competitividad MTM2016-74983-C2-1-R Ministerio de Economía y Competitividad MTM2016-75024-P Junta de Andalucía P12-FQM-2696

The article focuses on the description of the method of constructing a set of admissible routes in transport networks in the cases when there are given constraints on the individual tracks of transported objects. The constraints have a form of upper bounds on two weights and on the lengths of searched paths. We analyze and estimate the computational complexity of the proposed algorithm and consider the case when the weights are independently drawn from a given continuous distribution with independent components., Статья посвящена описанию метода построения множества допустимых маршрутов в транспортной сети в ситуации, когда заданы ограничения на длины и веса рассматриваемых маршрутов. Обосновывается корректность и оценивается сложность предложенного алгоритма. Анализируется случай, когда веса ребер в рассматриваемом графе можно рассматривать как результат процедуры независимого случайного выбора из непрерывного распределения с независимыми компонентами.

International audience; This paper presents a novel trade-off chart to support the design of multilayer acoustic packages. In this multi-objective problem, a designer has to specify a combination of layers from a set of available acoustic materials and thicknesses. Material types may include porous, mass-weighted, facing, among others. The combination must meet requirements in terms of sound absorption, sound transmission loss, cluttering, mass, etc. While predictions and analyses can be made on predetermined multilayer acoustic packages using the transfer matrix method, statistical energy analysis, finite elements methods or modal analysis, comparing a large number of possible combinations is cumbersome. On the other hand, optimization methods can be used to identify optimal thicknesses or material properties for a given layer combination, but the obtained solution may not be industrially relevant since, in general, only a limited set of acoustic materials and layer thicknesses exist commercially. In this paper, a new design methodology is proposed, which takes into account only the feasible combinations and provides guidelines for compromises between different performance parameters. The three-step methodology is demonstrated through a case study inspired by the automotive industry. First, relevant categories of layer configurations are defined, and following these patterns, all possible combinations of materials from a given inventory are calculated and stored in a database. Then, for selected performance parameters, the Pareto set of "better combinations" is identified. Finally, the "better solutions" are displayed on a trade-off chart through utility functions that allow weighing the different performance parameters. The tool developed for doing so is applied to the case study, and two example situations are presented. For each situation, the trade-off chart provides several suitable solutions, which are discussed. The use of this new tool effectively induces gains of time at the early stage of design, when it is most crucial.; Ce papier présente une nouvelle carte de compromis pour aider à la conception de solutions acoustiques multicouches. Dans ce problème multi-objectif, un concepteur doit spécifier une combinaison de couches à partir d'un jeu de matériaux et d'épaisseurs disponibles. Les types de matériaux peuvent inclure des matériaux poreux ou lestés, ou des couches de protections, par exemple. La combinaison doit répondre à des exigences d'absorption acoustique, de perte par transmission, d'encombrement, de masse, etc. Bien que des prédictions et des analyses puissent être réalisées pour une solution acoustique multicouche donnée en utilisant la méthode des matrices de transfert, l'analyse statistique énergétique, la méthode des éléments finis ou l'analyse modale, comparer un grand nombre de combinaisons possibles est complexe et coûteux. D'autre part, les méthodes d'optimisation peuvent être utilisées pour identifier les épaisseurs et les propriétés matériau optimales pour une combinaison de couches données, mais la solution obtenue peut ne pas être pertinente d'un point de vue industriel puisque, de manière générale, les matériaux acoustiques et les épaisseurs disponibles commercialement sont limités. Dans ce papier, une nouvelle méthodologie de conception est proposée, qui prend en compte uniquement les combinaisons réalisables et qui fournit des lignes directrices pour des compromis entre différents critères de performance. La méthodologie, composée de trois étapes, est présentée à travers un cas d'application inspiré par l'industrie automobile. Dans un premier temps, des catégories de configurations multicouches pertinentes sont définies, et toutes les combinaisons possibles respectant ces configurations avec un inventaire de matériaux donné sont calculées et stockées dans une base de données. Puis, pour des critères de performance choisis, le front de Pareto des « meilleures combinaisons » est identifié. Finalement, les « meilleures solutions » sont représentées sur une carte de compromis à l'aide de fonctions d'utilité qui permettent de pondérer différents critères de performance. L'outil développé est appliqué au cas d’application, et deux situations types sont présentées. Pour chaque situation, la carte de compromis fournit plusieurs solutions pertinentes, qui sont discutées. L'utilisation de ce nouvel outil permet un gain de temps aux étapes initiales de la conception, là où cela est le plus crucial.

Climate policy is changing fast in the EU, with country leaders raising the bloc's ambition to reduce greenhouse gas emissions by 2030 and 2050. However, there is uncertainty about the allocation of decarbonisation effort between EU member states. This paper develops a multi-objective optimisation framework to provide insights to decision-makers in this policy context by exploring trade-offs between stronger decarbonisation goals and higher costs. Applying this approach for Cyprus, we find that the maximum achievable abatement for the EU Effort Sharing sectors corresponds to a 35% target. The current 24% ambition can be achieved with net social benefits, but the transition to higher abatement results in positive costs with a gradual rate of increase. The picture changes when decision-making explicitly accounts for external costs of emissions of greenhouse gases and air pollutants in the optimisation procedure. In this case, the least-cost solution delivers an abatement of about 32% and can yield social benefits of more than one billion Euros'2020. Regarding public expenditures, it requires about 3% of national GDP each year. This indicates that the socially optimal policy mix for attaining decarbonisation of the Cypriot economy is feasible but requires a consistent allocation of public funds to build infrastructure, overcome investment barriers and mobilise capital to enable the uptake of clean technologies across the economy. Although the modelling framework has been developed for a specific country and is tailored to the specific EU policy circumstances, the proposed methodology is entirely suitable for other world regions with a demanding decarbonisation roadmap.

Generative computation has the potential to enhance the accuracy, effectiveness, and creativity of spatial layout in design and planning. The paper proposes a methodology to separate the knowledge about objects, spatial relationships, and constraints from the generative process. The separation between the knowledge in a domain and its possible practical uses is an important achievement of semantic technologies, because it grants access to a large body of knowledge, spanning various aspects and processes across buildings and cities, which is being codified into formal ontologies. The present study has reused existing knowledge from two established ontologies. An illustrative case-project demonstrates the suitability of the methodology for a complex layout planning problem, involving a large number of decision-makers, with multiple competing objectives and criteria. The system implements multidimensional visual interactive tools to assist designers, planners, and decision-makers in exploring the layouts and the criteria, to develop their confidence in what qualifies as a good and effective solution.

International audience; In this paper we address the problem of computing suitable representations of the set of approximate solutions of a given multi-objective optimization problem via stochastic search algorithms. For this, we will propose different archiving strategies for the selection of the candidate solutions maintained by the generation process of the stochastic search process, and investigate them further on analytically and empirically. For all archivers we will provide upper bounds on the approximation quality as well as on the cardinality of the limit solution set. We conclude this work by a comparative study on some test problems in order to visualize the effect of all novel archiving strategies.

International audience; Multi-criteria decision making (MCDM) methods have evolved for various types of applications. In the past, even small variations to existing methods have led to the creation of new avenues for research. Thus, in this study, we review the MCDM methods in investment management and examine the advantages and disadvantages of these methods in a risk environment. In addition, we study the effectiveness of investment projects using these methods. The analysis of MCDM methods performed in this study provides a guide for the use of these methods, especially the ones based on interval data, in investment project analysis. Furthermore, we propose a combination of multi-criterial selection and interval preferences to evaluate investment projects. Our method improves on the method of calculating economic efficiency based on a one-dimensional criterion and sensitivity analysis, though our proposal involves complicated calculations.

In this paper, we are interested in producing discrete and tractable representations of the set of non-dominated points for multi-objective optimization problems, both in the continuous and discrete cases. These representations must satisfy some conditions of coverage , i.e. providing a good approximation of the non-dominated set, spacing , i.e. without redundancies, and cardinality , i.e. with the smallest possible number of points. This leads us to introduce the new concept of (e, e′)- kernels , or e- kernels when ɛ ′ = ɛ is possible, which correspond to e-Pareto sets satisfying an additional condition of e′- stability . Among these, the kernels of small, or possibly optimal, cardinality are claimed to be good representations of the non-dominated set. We first establish some general properties on e-kernels. Then, for the bi-objective case, we propose some generic algorithms computing in polynomial time either an e-kernel of small size or, for a fixed size k , an e-kernel with a nearly optimal approximation ratio 1 + ɛ . For more than two objectives, we show that e-kernels do not necessarily exist but that (e, e′)-kernels with ɛ ′ ≤ 1 + ɛ − 1 always exist. Nevertheless, we show that the size of a smallest (e, e′)-kernel can be very far from the size of a smallest e-Pareto set.

A methodology of multiobjective design optimization of laminated composite plates with piezoelectric layers is presented in this paper. Constrained optimization is conducted for different behaviour objectives, like the maximization of buckling load or natural frequencies of specific vibration modes or prescribed displacements for example. Weight minimization can also be considered or the minimization of the electric voltages applied in the piezoelectric actuators. The optimization problems are constrained by stress based failure criteria and other structural response constraints like limits imposed on certain displacements, buckling characteristics and natural frequency constraints. The design variables considered in the present work are the fiber reinforcement orientations in the composite layers, thicknesses of individual layers and the electric potentials applied to the actuators. The optimization problems are solved with two direct search derivative-free algorithms: GLODS (Global and Local Optimization using Direct Search) and DMS (Direct MultiSearch). DMS, the multiobjective optimization solver, is started from a set of local minimizers which are initially determined by the global optimizer algorithm GLODS for each one of the objective functions.

Building on a class of transcendental preferences for luxury, explicit solutions for price taking behavior and exchange equilibrium are discussed, which share the analytical tractability of Cobb-Douglas models. Such economies display fundamental positive properties, among which uniqueness and price tâtonnement stability of equilibrium. The monotone comparative statics of the luxury effect is discussed. Pareto sets admit a simple characterization, which generalizes the one set forth by Afriat (1987) so that a richer phenomenology is embraced. Potential lines of progress are envisaged.

Water resources systems are often characterized by multiple objectives. Typically, there is no single optimal solution which can simultaneously satisfy all the objectives but rather a set of technologically efficient non-inferior or Pareto optimal solutions exists. Another point regarding multi-objective optimization is that interdependence and contradictions are common among one or more objectives. Therefore, understanding the competition mechanism of the multiple objectives plays a significant role in achieving an optimal solution. This study examines cascade reservoirs in the Heihe River Basin of China, with a focus on exploring the multi-objective competition mechanism among irrigation water shortage, ecological water shortage and the power generation of cascade hydropower stations. Our results can be summarized as follows: (1) the three-dimensional and two-dimensional spatial distributions of a Pareto set reveal that these three objectives, that is, irrigation water shortage, ecological water shortage and power generation of cascade hydropower stations cannot reach the theoretical optimal solution at the same time, implying the existence of mutual restrictions, (2) to avoid subjectivity in choosing limited representative solutions from the Pareto set, the long series of non-inferior solutions are adopted to study the competition mechanism. The premise of sufficient optimization suggests a macro-rule of &lsquo, one falls and another rises,&rsquo, that is, when one objective value is inferior, the other two objectives show stronger and superior correlation, (3) the joint copula function of two variables is firstly employed to explore the multi-objective competition mechanism in this study. It is found that the competition between power generation and the other objectives is minimal. Furthermore, the recommended annual average water shortage are 1492 &times, 104 m3 for irrigation and 4951 &times, 104 m3 for ecological, respectively. This study is expected to provide a foundation for selective preference of a Pareto set and insights for other multi-objective research.

The Pareto set of a multiobjective optimization problem consists of the solutions for which one or more objectives can not be improved without deteriorating one or more other objectives. We consider problems with linear objectives and linear constraints and use Adjustable Robust Optimization and Polynomial Optimization as tools to approximate the Pareto set with polynomials of arbitrarily large degree. The main difference with existing techniques is that we optimize a single (extended) optimization problem that provides a polynomial approximation whereas existing methods iteratively construct a piecewise linear approximation. The proposed method has several advantages, e.g. it is more useful for visualizing the Pareto set, it can give a local approximation of the Pareto set, and it can be used for determining the shape of the Pareto set.

In many fields, we come across problems where we want to optimize several conflicting objectives simultaneously. To find a good solution for such multi-objective optimization problems, an approximation of the Pareto set is often generated. In this paper, we con- sider the approximation of Pareto sets for problems with three or more convex objectives and with convex constraints. For these problems, sandwich algorithms can be used to de- termine an inner and outer approximation between which the Pareto set is 'sandwiched'. Using these two approximations, we can calculate an upper bound on the approximation error. This upper bound can be used to determine which parts of the approximations must be improved and to provide a quality guarantee to the decision maker. In this paper, we extend higher dimensional sandwich algorithms in three different ways. Firstly, we introduce the new concept of adding dummy points to the inner approx- imation of a Pareto set. By using these dummy points, we can determine accurate inner and outer approximations more e±ciently, i.e., using less time-consuming optimizations. Secondly, we introduce a new method for the calculation of an error measure which is easy to interpret. The combination of easy calculation and easy interpretation makes this measure very suitable for sandwich algorithms. Thirdly, we show how transforming cer- tain objective functions can improve the results of sandwich algorithms and extend their applicability to certain non-convex problems. The calculation of the introduced error measure when using transformations will also be discussed. To show the effect of these enhancements, we make a numerical comparison using four test cases, including a four-dimensional case from the field of intensity-modulated radiation therapy (IMRT). The results of the different cases show that we can indeed achieve an accurate approximation using significantly fewer optimizations by using the enhancements.

We study the interaction between the MIMD (Multiplicative Increase Multiplicative Decrease) congestion control and a bottleneck router with Drop Tail buffer. We consider the problem in the framework of deterministic hybrid models. We study conditions under which the system trajectories converge to limiting cycles with a single jump. Following that, we consider the problem of the optimal buffer sizing in the framework of multi-criteria optimization in which the Lagrange function corresponds to a linear combination of the average throughput and the average delay in the queue. As case studies, we consider the Slow Start phase of TCP New Reno and Scalable TCP for high speed networks. © 2009 Elsevier B.V. All rights reserved.

This paper analyzes more than 40 papers with a restricted area of application of Multi-Objective Genetic Algorithm, Non-Dominated Sorting Genetic Algorithm-II and Multi-Objective Differential Evolution (MODE) to solve the multi-objective problem in agricultural water management. The paper focused on different application aspects which include water allocation, irrigation planning, crop pattern and allocation of available land. The performance and results of these techniques are discussed. The review finds that there is a potential to use MODE to analyzed the multi-objective problem, the application is more significance due to its advantage of being simple and powerful technique than any Evolutionary Algorithm. The paper concludes with the hopeful new trend of research that demand effective use of MODE; inclusion of benefits derived from farm byproducts and production costs into the model.

A method is presented for generating a well-distributed Pareto set in nonlinear multiobjective optimization. The approach shares conceptual similarity with the Physical Programming-based method, the Normal-Boundary Intersection and the Normal Constraint methods, in its systematic approach investigating the objective space in order to obtain a well-distributed Pareto set. The proposed approach is based on the generalization of the class functions which allows the orientation of the search domain to be conducted in the objective space. It is shown that the proposed modification allows the method to generate an even representation of the entire Pareto surface. The generation is performed for both convex and nonconvex Pareto frontiers. A simple algorithm has been proposed to remove local Pareto solutions. The suggested approach has been verified by several test cases, including the generation of both convex and concave Pareto frontiers.

Trade-off (aka Pareto) curves are typically used to represent the trade-off among different objectives in multiobjective optimization problems. Although trade-off curves are exponentially large for typical combinatorial optimization problems (and infinite for continuous problems), it was observed in Papadimitriou and Yannakakis [On the approximability of trade-offs and optimal access of web sources, in: Proc. 41st IEEE Symp. on Foundations of Computer Science, 2000] that there exist polynomial size e approximations for any e > 0, and that under certain general conditions, such approximate e-Pareto curves can be constructed in polynomial time. In this paper we seek general-purpose algorithms for the efficient approximation of trade-off curves using as few points as possible. In the case of two objectives, we present a general algorithm that efficiently computes an e-Pareto curve that uses at most 3 times the number of points of the smallest such curve; we show that no algorithm can be better than 3-competitive in this setting. If we relax e to any e' > e, then we can efficiently construct an e'-curve that uses no more points than the smallest e-curve. With three objectives we show that no algorithm can be c-competitive for any constant c unless it is allowed to use a larger e value. We present an algorithm that is 4-competitive for any e' > (1 + e)2 - 1. We explore the problem in high dimensions and give hardness proofs showing that (unless P=NP) no constant approximation factor can be achieved efficiently even if we relax e by an arbitrary constant.

We consider the task to assess the quality of Pareto set (front) numerical approximation in a multi-criteria optimization (MOC) problem. We mean that Pareto-approximation is obtained by means of this or that population e.g. genetic algorithm.Eventually, the purpose of work is a comparative assessment of the efficiency of population algorithms of Pareto-approximation. The great number of characteristics (indicators) of the Pareto-approximation quality is developed. Therefore an assessment problem of the Paretoapproximation quality is also considered as multi-criteria (multi-indicator). There are a number of well-known software systems to solve an assessment problem of the Pareto-approximation quality in different degree. Common drawback of these systems is a lack of both the WEB INTERFACE and the support of a multi-indicator assessment of Pareto-approximation quality (though there is a support to calculate the values of a large number of these indicators). The PARETO RATING software system is urged to eliminate the specified shortcomings of known systems. As population algorithms of Pareto-approximation are, as a rule, stochastic, we consider statistical methods to assess the quality of two and more Pareto-approximations (and thereby the estimates of algorithms used to obtain these approximations as well) as follows: methods based on the ranging of the specified approximations; methods based on the quality indicators; methods based on the so-called empirical functions of approachability. We give formal statement of the MOC-problem and general scheme of the population algorithms of its solution, present reviews of known indicators of Pareto-approximation quality and statistical methods for assessment of Pareto-approximation quality. We describe the system architecture and main features of its software implementation and illustrate efficiency of made algorithmic and software solutions.

An assembly supply chain (SC) is composed of stages that provide the components, assemble both sub-assemblies and final products, and deliver products to the customer. The activities carried out in each stage could be performed by one or more options, thus the decision-maker must select the set of options that minimises the cost of goods sold (CoGS) and the lead time (LT), simultaneously. In this paper, an ant colony-based algorithm is proposed to generate a set of SC configurations using the concept of Pareto optimality. The pheromones are updated using an equation that is a function of the CoGS and LT. The algorithm is tested using a notebook SC problem, widely used in literature. The results show that the ratio between the size of the Pareto Front computed by the proposed algorithm and the size of the one computed by exhaustive enumeration is 90%. Other metrics regarding error ratio and generational distance are provided as well as the CPU time to measure the performance of the proposed algorithm. This work was partially supported by the Spanish Ministerio de Ciencia e Innovación, under the project “Gestión de movilidad eficiente y sostenible, MOVES” with grant reference TIN2011-28336.

The Pareto set of a multiobjective optimization problem consists of the solutions for which one or more objectives can not be improved without deteriorating one or more other objectives. We consider problems with linear objectives and linear constraints and use Adjustable Robust Optimization and Polynomial Optimization as tools to approximate the Pareto set with polynomials of arbitrarily large degree. The main difference with existing techniques is that we optimize a single (extended) optimization problem that provides a polynomial approximation whereas existing methods iteratively construct a piecewise linear approximation. The proposed method has several advantages, e.g. it is more useful for visualizing the Pareto set, it can give a local approximation of the Pareto set, and it can be used for determining the shape of the Pareto set.

ISBN 978-1-4471-2206-7; Reliability-based design, operation and maintenance of multi-state systems lead to multiobjective (multicriteria) optimization problems whose solutions are represented in terms of Pareto Fronts and Sets. Among these solutions, the decision maker must choose the ones which best satisfy his\her preferences on the objectives of the problem. Visualization and analysis of the Pareto Fronts and Sets can help decision makers in this task. In this view, a recently introduced graphical representation, called Level Diagrams, is here used in support of the analysis of Pareto Fronts and Sets aimed at reducing the number of non-dominated solutions to be considered by the decision maker. Each objective and design parameter is represented on separate "synchronized" diagrams which position the Pareto front points according to their proximity to ideal preference points and on the basis of this representation a two-step front reduction procedure is proposed. An application to a redundancy allocation problem of literature concerning a multi-state system is used to illustrate the analysis.

Во многих практически значимых случаях при решении задачи многокритериальной оптимизации предварительно целесообразно построить аппроксимацию множества Парето этой задачи. Рассматривается комбинация известного метода приближенного построения множества Парето «недоминируемая сортировка» и метода глобальной оптимизации роем частиц. Целью работы является исследование эффективности указанной комбинации методов при их реализации на графических процессорных устройствах с архитектурой CUDA. There are a lot of practical cases that requires Pareto set construction to solve multi-objective optimization task. This article is devoted to observe a combination of well-known non-dominated sorting method with particle swarm optimization algorithm. Authors set a goal to research efficiency of the new combined method on graphical computational unit with CUDA architecture. Анатолий Павлович Карпенко, доктор физико-математических наук, профессор, кафедра «Системы автоматизированного проектирования», МГТУ имени Н.Э. Баумана (Россия, г. Москва), apkarpenko@mail.ru. Anatoliy Pavlovich Karpenko, Doctor of Physico-mathematical Sciences, Full Professor, CAD/CAM/CAE department, Bauman Moscow State Technical University (Russia, Moscow), apkarpenko@mail.ru. Артем Сергеевич Семенихин, аспирант, кафедра «Системы автоматизированного проектирования», МГТУ имени Н.Э. Баумана (Россия, г. Москва), saspost@yandex.ru. Artyom Sergeevich Semenikhin, Postgraduate Student, CAD/CAM/CAE department, Bauman Moscow State Technical University (Russia, Moscow), saspost@yandex.ru. Александр Эдуардович Антух, студент, кафедра «Системы автоматизированного проектирования», МГТУ имени Н.Э. Баумана (Россия, г. Москва), alexander.antukh@gmail.com. Alexander Eduardovich Antukh, student, CAD/CAM/CAE department, Bauman Moscow State Technical University (Russia, Moscow), alexander.antukh@gmail.com. МГТУ имени Н.Э. Баумана

What-if analysis is a data-intensive exploration to inspect how changes in a set of input parameters of a model influence some outcomes. It is motivated by a user trying to understand the sensitivity of a model to a certain parameter in order to reach a set of goals that are defined over the outcomes. To avoid an exploration of all possible combinations of parameter values, efficient what-if analysis calls for a partitioning of parameter values into data ranges and a unified representation of the obtained outcomes per range. Traditional techniques to capture data ranges, such as histograms, are limited to one outcome dimension. Yet, in practice, what-if analysis often involves conflicting goals that are defined over different dimensions of the outcome. Working on each of those goals independently cannot capture the inherent trade-off between them. In this paper, we propose techniques to recommend data ranges for what-if analysis, which capture not only data regularities, but also the trade-off between conflicting goals. Specifically, we formulate a parametric data partitioning problem and propose a method to find an optimal solution for it. Targeting scalability to large datasets, we further provide a heuristic solution to this problem. By theoretical and empirical analyses, we establish performance guarantees in terms of runtime and result quality.