An interactive multiobjective programming approach to combinatorial data analysis

Combinatorial optimization problems in the social and behavioral sciences are frequently associated with a variety of alternative objective criteria. Multiobjective programming is an operations research methodology that enables the quantitative analyst to investigate tradeoffs among relevant objective criteria. In this paper, we describe an interactive procedure for multiobjective asymmetric unidimensional seriation problems. This procedure uses a dynamic-programming algorithm to partially generate the efficient set of sequences for small to medium-sized problems, and a multioperation heuristic to estimate the efficient set for larger problems. The interactive multiobjective procedure is applied to an empirical data set from the psychometric literature. We conclude with a discussion of other potential areas of application in combinatorial data analysis.Stephanie Stahl is a freelance writer and editor. She can be reached via e-mail at s-stahl@worldnet.att.net.     

MOSA method: a tool for solving multiobjective combinatorial optimization problems

The success of modern heuristics (Simulated Annealing (S.A.), Tabu Search, Genetic Algorithms, …) in solving classical combinatorial optimization problems has drawn the attention of the research community in multicriteria methods. In fact, for large‐scale problems, the simultaneous difficulties of 𝒩𝒫‐hard complexity and of multiobjective framework make most Multiobjective Combinatorial Optimization (MOCO) problems intractable for exact methods. This paper develops the so‐called MOSA (Multiobjective Simulated Annealing) method to approximate the set of efficient solutions of a MOCO problem. Different options for the implementation are illustrated and extensive experiments prove the efficiency of the approach. Its results are compared to exact methods on bi‐objective knapsack problems. Copyright © 1999 John Wiley & Sons, Ltd.     

A global optimization approach for generating efficient points for multiobjective concave fractional programs

In this article, we present a global optimization approach for generating efficient points for multiobjective concave fractional programming problems. The main work of the approach involves solving an instance of a concave multiplicative fractional program (W̄). Problem (W̄) is a global optimization problem for which no known algorithms are available. Therefore, to render the approach practical, we develop and validate a branch and bound algorithm for globally solving problem (W̄). To illustrate the performance of the global optimization approach, we use it to generate efficient points for a sample multiobjective concave fractional program. Copyright © 2006 John Wiley & Sons, Ltd.     

Surrogate‐assisted multicriteria optimization: Complexities,prospective solutions,and business case

Complexity in solving real‐world multicriteria optimization problems often stems from the fact that complex, expensive, and/or time‐consuming simulation tools or physical experiments are used to evaluate solutions to a problem. In such settings, it is common to use efficient computational models, often known as surrogates or metamodels, to approximate the outcome (objective or constraint function value) of a simulation or physical experiment. The presence of multiple objective functions poses an additional layer of complexity for surrogate‐assisted optimization. For example, complexities may relate to the appropriate selection of metamodels for the individual objective functions, extensive training time of surrogate models, or the optimal use of many‐core computers to approximate efficiently multiple objectives simultaneously. Thinking out of the box, complexity can also be shifted from approximating the individual objective functions to approximating the entire Pareto front. This leads to further complexities, namely, how to validate statistically and apply the techniques developed to real‐world problems. In this paper, we discuss emerging complexity‐related topics in surrogate‐assisted multicriteria optimization that may not be prevalent in nonsurrogate‐assisted single‐objective optimization. These complexities are motivated using several real‐world problems in which the authors were involved. We then discuss several promising future research directions and prospective solutions to tackle emerging complexities in surrogate‐assisted multicriteria optimization. Finally, we provide insights from an industrial point of view into how surrogate‐assisted multicriteria optimization techniques can be developed and applied within a collaborative business environment to tackle real‐world problems.     

A note on the estimation of the Pareto efficient set for multiobjective matrix permutation problems

There are a number of important problems in quantitative psychology that require the identification of a permutation of the n rows and columns of an n × n proximity matrix. These problems encompass applications such as unidimensional scaling, paired‐comparison ranking, and anti‐Robinson forms. The importance of simultaneously incorporating multiple objective criteria in matrix permutation applications is well recognized in the literature; however, to date, there has been a reliance on weighted‐sum approaches that transform the multiobjective problem into a single‐objective optimization problem. Although exact solutions to these single‐objective problems produce supported Pareto efficient solutions to the multiobjective problem, many interesting unsupported Pareto efficient solutions may be missed. We illustrate the limitation of the weighted‐sum approach with an example from the psychological literature and devise an effective heuristic algorithm for estimating both the supported and unsupported solutions of the Pareto efficient set.     

A technique based on trade‐off maps to visualise and analyse relationships between objectives in optimisation problems

Understanding the relationships between objectives in a multiobjective optimisation problem is important for developing tailored and efficient solving techniques. In particular, when tackling combinatorial optimisation problems with many objectives, that arise in real‐world logistic scenarios, better support for the decision maker can be achieved through better understanding of the often complex fitness landscape. This paper makes a contribution in this direction by presenting a technique that allows a visualisation and analysis of the local and global relationships between objectives in optimisation problems with many objectives. The proposed technique uses four steps: First, the global pairwise relationships are analysed using the Kendall correlation method; then, the ranges of the values found on the given Pareto front are estimated and assessed; next, these ranges are used to plot a map using Gray code, similar to Karnaugh maps, that has the ability to highlight the trade‐offs between multiple objectives; and finally, local relationships are identified using scatter plots. Experiments are presented for three combinatorial optimisation problems: multiobjective multidimensional knapsack problem, multiobjective nurse scheduling problem, and multiobjective vehicle routing problem with time windows . Results show that the proposed technique helps in the gaining of insights into the problem difficulty arising from the relationships between objectives.     

Relating reference points and weights in MOLP

A frequent problem for decision makers (DMs) analysing decisions involving multiple objectives is the identification and selection of the most preferred option from the set of non‐dominated solutions. Two techniques, weighted sum optimization and reference point optimization, have been developed to address this problem for multiobjective linear programming problems (MOLP). In this paper, we examine the relationship between these two techniques. We demonstrate that the values of the dual variables associate with auxiliary constraints of the reference point technique are equal to the weight values used to compute the same non‐dominated solution via the weighted sum technique. This insight will enable the development of new interactive solution procedures for MOLPs which allow the DM to readily switch from one method to the other during the search for the most preferred non‐dominated solution. The advantages of the approach are discussed in the paper. Copyright © 1999 John Wiley & Sons, Ltd.     

Multiobjective Optimization for the Asset Allocation of European Nonlife Insurance Companies

An optimal asset allocation is crucial for nonlife insurance companies. The most previous studies focused on this topic use a mono‐objective technique optimization. This technique usually allows the maximization of shareholders' expected utility. As nonlife insurance company is a complex system, it has many stakeholders other than shareholders. So, the satisfaction of the shareholders' expected utility cannot lead usually to the satisfaction of other stakeholders' objectives. Therefore, the focus on utility maximization can be a destruction source of other objectives such as productivity, competitiveness and solvency. Our developed model integrates simulation approach with a multiobjective particle swarm optimization algorithm. This model insures an optimal asset allocation that maximizes, simultaneously, shareholders expected utility and technical efficiency of European nonlife insurance companies. The empirical application conducts a comparison between the attained results with multiobjective optimization technique and mono‐objective technique to search the optimal asset allocation for nonlife insurance companies. Our results show that the investment portfolio will be more diversified between most available investment assets. In addition, any decision maker should take account of different stakeholders' objectives. Accordingly, multiobjective optimization allows us to find the best asset allocation that maximizes simultaneously expected utility and technical efficiency of nonlife insurance companies. Copyright © 2013 John Wiley & Sons, Ltd.     

Comparing graphic and symbolic classification in interactive multiobjective optimization

In interactive multiobjective optimization systems, the classification of objective functions is a convenient way to direct the solution process in order to search for new, more satisfactory, solutions in the set of Pareto optimal solutions. Classification means that the decision maker assigns the objective functions into classes depending on what kind of changes in their values (in relation to the current values) are desirable. Here we study the role of user interfaces in implementing classification in multiobjective optimization software and how classification should be realized. In this way, we want to pay attention to the usability of multiobjective optimization software. Typically, this topic has not been of interest in the multiobjective optimization literature. However, usability aspect is important because in interactive classification‐based multiobjective optimization methods, the classification is the core of the solution process. We can say that the more convenient the classification is, the more efficient the system or the method is and the better it supports the work of the decision maker. We report experiments with two classification options, graphic and symbolic ones, which are used in connection with an interactive multiobjective optimization system WWW‐NIMBUS. The ideas and conclusions given are applicable for other interactive classification‐based method, as well. Copyright © 2005 John Wiley & Sons, Ltd.     

Cross validation issues in multiobjective clustering

The implementation of multiobjective programming methods in combinatorial data analysis is an emergent area of study with a variety of pragmatic applications in the behavioural sciences. Most notably, multiobjective programming provides a tool for analysts to model trade offs among competing criteria in clustering, seriation, and unidimensional scaling tasks. Although multiobjective programming has considerable promise, the technique can produce numerically appealing results that lack empirical validity. With this issue in mind, the purpose of this paper is to briefly review viable areas of application for multiobjective programming and, more importantly, to outline the importance of cross‐validation when using this method in cluster analysis.     

Multicriteria Optimization Technique for Optimal Design of Orthotropic Bridges

The design improvement of large‐scale structures such as cable stayed and suspension bridges with large spans is one of the major engineering optimization problems faced by design engineers. In many real‐life engineering design problems, it is necessary to carry out large‐scale experimental physical models for only one prototype to construct the feasible solution set that is too expensive and not practical. For these reasons, an experimental search for optimal solutions is often not carried out at all. This paper presents a technique for multicriteria analysis, which involve the finite element analysis of the prototype in the optimization process. The improvement of the Suez Canal Bridge in Egypt is introduced as a real‐life large‐scale case study. The parameter space investigation method, the visual basic for application programming language, and Femap as finite element analysis software provide an implementation tools to construct the feasible and Pareto solution sets for the studied bridge. An efficient combination between the parameter space investigation method and the finite element programme was successfully investigated to obtain the Pareto solution set. This study shows possibility to apply the multicriteria optimization method for more applications on different large‐scale structural systems in the future. Copyright © 2013 John Wiley & Sons, Ltd.     

Constructing robust crew schedules with bicriteria optimization

Optimization‐based computer systems are used by many airlines to solve crew planning problems by constructing minimal cost tours of duty. However, today airlines do not only require cost effective solutions, but are also very interested in robust solutions. A more robust solution is understood to be one where disruptions in the schedule (due to delays) are less likely to be propagated into the future, causing delays of subsequent flights. Current scheduling systems based solely on cost do not automatically provide robust solutions. These considerations lead to a multiobjective framework, as the maximization of robustness will be in conflict with the minimization of cost. For example crew changing aircraft within a duty period is discouraged if inadequate ground time is provided. We develop a bicriteria optimization framework to generate Pareto optimal schedules for the domestic airline. A Pareto optimal schedule is one which does not allow an improvement in cost and robustness at the same time. We developed a method to solve the bicriteria problem, implemented it and tested it with actual airline data. Our results show that considerable gain in robustness can be achieved with a small increase in cost. The additional cost is mainly due to an increase in overnights, which allows for a reduction of the number of aircraft changes. Copyright © 2003 John Wiley & Sons, Ltd.     

Aspiration/reservation-based decision support—a step beyond goal programming

Real-life decision problems are usually so complex that they cannot be modelled with a single objective function, thus creating a need for clear and efficient techniques for handling multiple criteria to support the decision process. A widely used technique and one commonly taught in general OR/MS courses is goal programming, which is clear and appealing. On the other hand, goal programming is strongly criticized by multiple-criteria optimization specialists for its non-compliance with the efficiency (Pareto-optimality) principle. In this paper we show how the implementation techniques of goal programming can be used to model the reference point method and its extension, aspiration/reservation-based decision support. Thereby we show a congruence between these approaches and suggest how the GP model with relaxation of some traditional assumptions can be extended to an efficient decision support technique meeting the efficiency principle and other standards of multiobjective optimization theory.     

Navigation in multiobjective optimization methods

Building on previous work of the authors, this paper formally defines and reviews the first approach, referred to as navigation , towards a common understanding of search and decision‐making strategies to identify the most preferred solution among the Pareto set for a multiobjective optimization problem. In navigation methods, the decision maker interactively learns about the problem, whereas the decision support system learns about the preferences of the decision maker. This work introduces a detailed view on navigation leading to the identification of integral components and features. A number of different existing navigation methods are reviewed and characterized. Finally, an overview of applications involving navigation is given, and promising future research direction are discussed.     

Strategic Revenue Management under Uncertainty: A Case Study on Real Estate Projects in India

This paper proposes an approach for strategic revenue management under uncertainty for real estate projects. It integrates three modelling techniques: first, artificial neural network integrated support vector machines for forecasting the profit and loss‐making real estate residential projects; second, analytical network process approach using decision making trials and evaluation laboratory methodology for establishing interrelationships among factors; and third, multiobjective genetic algorithm approach for obtaining optimal numbers and types of apartments in a real estate project. We compare the respective revenues generated with the new number of apartments and price from the suggested revenue maximization model and that of the old practiced one through a case study of India. Copyright © 2015 John Wiley & Sons, Ltd.     

Approximation of Value Efficient Solutions

We introduce an approximation set to the value efficient set in multiobjective problems under partial information on the decision maker's preferences modelled by a vector value function. We show monotonicity and convergence properties based on increasingly precise vector value functions with two components, which improve the approximation and might be a support to possible solution methods. © 1997 John Wiley & Sons, Ltd.     

A bare bones bacterial foraging optimization algorithm

Bacterial foraging optimization (BFO), based on the social foraging behaviors of bacteria, is a new intelligent optimizer. It has been widely accepted as an optimization algorithm of current interest for a variety of fields. However, compared with other optimizers, the BFO possesses a poor convergence performance over complex optimization problems. To improve the optimization capability of the BFO, in this paper a bare bones bacterial foraging optimization (BBBFO) algorithm is developed. First, a chemotactic strategy based on Gaussian distribution is incorporated into this method through making use of both the historical information of individual and the share information of group. Then the swarm diversity is introduced in the reproduction strategy to promote the exploration ability of the algorithm. The performance of BBBFO is verified on various benchmark functions, the comparative results reveal that the proposed approach is more superior to its counterparts.     

Multiobjective Blockmodeling for Social Network Analysis

To date, most methods for direct blockmodeling of social network data have focused on the optimization of a single objective function. However, there are a variety of social network applications where it is advantageous to consider two or more objectives simultaneously. These applications can broadly be placed into two categories: (1) simultaneous optimization of multiple criteria for fitting a blockmodel based on a single network matrix and (2) simultaneous optimization of multiple criteria for fitting a blockmodel based on two or more network matrices, where the matrices being fit can take the form of multiple indicators for an underlying relationship, or multiple matrices for a set of objects measured at two or more different points in time. A multiobjective tabu search procedure is proposed for estimating the set of Pareto efficient blockmodels. This procedure is used in three examples that demonstrate possible applications of the multiobjective blockmodeling paradigm.     

Pareto simulated annealing—a metaheuristic technique for multiple-objective combinatorial optimization

This paper presents a multiple-objective metaheuristic procedure—Pareto simulated annealing. The goal of the procedure is to find in a relatively short time a good approximation of the set of efficient solutions of a multiple-objective combinatorial optimization problem. The procedure uses a sample, of so-called generating solutions. Each solution explores its neighbourhood in a way similar to that of classical simulated annealing. Weights of the objectives, used for their local aggregation, are tuned in each iteration in order to assure a tendency for approaching the efficient solutions set while maintaining a uniform distribution of the generating solutions over this set. A computational experiment shows that the method is a better tool for approximating the efficient set than some previous proposals. © 1998 John Wiley & Sons, Ltd.