Solving the multiobjective possibilistic linear programming problem

In conventional multiobjective decision making problems, the estimation of the parameters of the model is often a problematic task. Normally they are either given by the decision maker (DM), who has imprecise information and/or expresses his considerations subjectively, or by statistical inference from past data and their stability is doubtful. Therefore, it is reasonable to construct a model reflecting imprecise data or ambiguity in terms of fuzzy sets for which a lot of fuzzy approaches to multiobjective programming have been developed. In this paper we propose a method to solve a multiobjective linear programming problem involving fuzzy parameters (FP-MOLP), whose possibility distributions are given by fuzzy numbers, estimated from the information provided by the DM. As the parameters, intervening in the model, are fuzzy the solutions will be also fuzzy. We propose a new Pareto Optimal Solution concept for fuzzy multiobjective programming problems. It is based on the extension principle and the joint possibility distribution of the fuzzy parameters of the problem. The method relies on α-cuts of the fuzzy solution to generate its possibility distributions. These ideas are illustrated with a numerical example.     

Integer programming formulation of combinatorial optimization problems

This paper considers in a somewhat general setting when a combinatorial optimization problem can be formulated as an (all-integer) integer programming (IP) problem. The main result is that any combinatorial optimization problem can be formulated as an IP problem if its feasible region S is finite but there are many rather sample problems that have no IP formulation if their S is infinite. The approach used for finite S usually gives a formulation with a relatively small number of additional variables for example, an integer polynomial of n 0?1 variables requires at most n + 1 additional variables by our approach, whereas 2ⁿ - (n + 1) additional variables at maximum are required by other existing methods. Finally, the decision problem of deciding whether an arbitrarily given combinatorial optimization problem has an IP formulation is considered and it is shown by an argument closely related to Hilbert's tenth problem (drophantine equations) that no such algorithm exists.     

Using assignment examples to infer weights for ELECTRE TRI method: Some experimental results

Given a finite set of alternatives A, the sorting (or assignment) problem consists in the assignment of each alternative to one of the pre-defined categories. In this paper, we are interested in multiple criteria sorting problems and, more precisely, in the existing method ELECTRE TRI. This method requires the elicitation of preferential parameters (weights, thresholds, category limits,…) in order to construct a preference model which the decision maker (DM) accepts as a working hypothesis in the decision aid study. A direct elicitation of these parameters requiring a high cognitive effort from the DM (V. Mosseau, R. Slowinski, Journal of Global Optimization 12 (2) (1998) 174), proposed an interactive aggregation–disaggregation approach that infers ELECTRE TRI parameters indirectly from holistic information, i.e., assignment examples. In this approach, the determination of ELECTRE TRI parameters that best restore the assignment examples is formulated through a nonlinear optimization program.In this paper, we consider the subproblem of the determination of the weights only (the thresholds and category limits being fixed). This subproblem leads to solve a linear program (rather than nonlinear in the global inference model). Numerical experiments were conducted so as to check the behaviour of this disaggregation tool. Results showed that this tool is able to infer weights that restores in a stable way the assignment examples and that it is able to identify “inconsistencies” in the assignment examples.     

Decision making in multiobjective optimization aided by the multicriteria tournament decision method

This paper proposes a new method for multicriteria analysis, named Multicriteria Tournament Decision (MTD). It provides the ranking of alternatives from best to worst, according to the preferences of a human decision-maker (DM). It has some positive aspects such as: it has a simple algorithm with intuitive appeal; it involves few input parameters (just the importance weight of each criterion).The helpfulness of MTD is demonstrated by using it to select the final solution of multiobjective optimization problems in an a posteriori decision making approach. Having at hand a discrete approximation of the Pareto front (provided by a multiobjective evolutionary search algorithm), the choice of the preferred Pareto-optimal solution is performed using MTD.A simple method, named Gain Analysis method (GAM), for verifying the existence of a better solution (a solution associated to higher marginal rates of return) than the one originally chosen by the DM, is also introduced here. The usefulness of MTD and GAM methods is confirmed by the suitable results shown in this paper.     

Finding the K best policies in a finite-horizon Markov decision process

Directed hypergraphs represent a general modelling and algorithmic tool, which have been successfully used in many different research areas such as artificial intelligence, database systems, fuzzy systems, propositional logic and transportation networks. However, modelling Markov decision processes using directed hypergraphs has not yet been considered.In this paper we consider finite-horizon Markov decision processes (MDPs) with finite state and action space and present an algorithm for finding the K best deterministic Markov policies. That is, we are interested in ranking the first K deterministic Markov policies in non-decreasing order using an additive criterion of optimality. The algorithm uses a directed hypergraph to model the finite-horizon MDP. It is shown that the problem of finding the optimal policy can be formulated as a minimum weight hyperpath problem and be solved in linear time, with respect to the input data representing the MDP, using different additive optimality criteria.     

Decision making in multiobjective optimization aided by the multicriteria tournament decision method

This paper proposes a new method for multicriteria analysis, named Multicriteria Tournament Decision (MTD). It provides the ranking of alternatives from best to worst, according to the preferences of a human decision-maker (DM). It has some positive aspects such as: it has a simple algorithm with intuitive appeal; it involves few input parameters (just the importance weight of each criterion).The helpfulness of MTD is demonstrated by using it to select the final solution of multiobjective optimization problems in an a posteriori decision making approach. Having at hand a discrete approximation of the Pareto front (provided by a multiobjective evolutionary search algorithm), the choice of the preferred Pareto-optimal solution is performed using MTD.A simple method, named Gain Analysis method (GAM), for verifying the existence of a better solution (a solution associated to higher marginal rates of return) than the one originally chosen by the DM, is also introduced here. The usefulness of MTD and GAM methods is confirmed by the suitable results shown in this paper.     

An interactive dynamic approach based on hybrid swarm optimization for solving multiobjective programming problem with fuzzy parameters

Real engineering design problems are generally characterized by the presence of many often conflicting and incommensurable objectives. Naturally, these objectives involve many parameters whose possible values may be assigned by the experts. The aim of this paper is to introduce a hybrid approach combining three optimization techniques, dynamic programming (DP), genetic algorithms and particle swarm optimization (PSO). Our approach integrates the merits of both DP and artificial optimization techniques and it has two characteristic features. Firstly, the proposed algorithm converts fuzzy multiobjective optimization problem to a sequence of a crisp nonlinear programming problems. Secondly, the proposed algorithm uses H-SOA for solving nonlinear programming problem. In which, any complex problem under certain structure can be solved and there is no need for the existence of some properties rather than traditional methods that need some features of the problem such as differentiability and continuity. Finally, with different degree of α we get different α-Pareto optimal solution of the problem. A numerical example is given to illustrate the results developed in this paper.     

A new algorithm for generating all nondominated solutions of multiobjective discrete optimization problems

Most real-life decision-making activities require more than one objective to be considered. Therefore, several studies have been presented in the literature that use multiple objectives in decision models. In a mathematical programming context, the majority of these studies deal with two objective functions known as bicriteria optimization, while few of them consider more than two objective functions. In this study, a new algorithm is proposed to generate all nondominated solutions for multiobjective discrete optimization problems with any number of objective functions. In this algorithm, the search is managed over (p − 1)-dimensional rectangles where p represents the number of objectives in the problem and for each rectangle two-stage optimization problems are solved. The algorithm is motivated by the well-known ε-constraint scalarization and its contribution lies in the way rectangles are defined and tracked. The algorithm is compared with former studies on multiobjective knapsack and multiobjective assignment problem instances. The method is highly competitive in terms of solution time and the number of optimization models solved.     

Performance bounds for hierarchical systems under partial dynamic information

This paper discusses a general approach to obtain optimum performance bounds for (N+1)-person deterministic decision problems,N+1>2, with several levels of hierarchy and under partial dynamic information. Both cooperative and noncooperative modes of decision making are considered at the lower levels of hierarchy; in each case, it is shown that the optimum performance of the decision maker at the top of the hierarchy can be obtained by solving a sequence of open-loop (static) optimization problems. A numerical example included in the paper illustrates the general approach.     

Interactive outranking approaches for multicriteria decision-making problems with imprecise information

PROMETHEE is a powerful method, which can solve many multiple criteria decision making (MCDM) problems. It involves sophisticated preference modelling techniques but requires too much a priori precise information about parameter values (such as criterion weights and thresholds). In this paper, we consider a MCDM problem where alternatives are evaluated on several conflicting criteria, and the criterion weights and/or thresholds are imprecise or unknown to the decision maker (DM). We build robust outranking relations among the alternatives in order to help the DM to rank the alternatives and select the best alternative. We propose interactive approaches based on PROMETHEE method. We develop a decision aid tool called INTOUR, which implements the developed approaches.     

Investigation of two-warehouse inventory problems in interval environment under inflation via particle swarm optimization

ABSTRACT

In this paper, a two-warehouse inventory problem has been investigated under inflation with different deterioration effects in two separate warehouses (rented warehouse, RW, and owned warehouse, OW). The objective of this investigation is to determine the lot-size of the cycle of the two-warehouse inventory system by minimizing the average cost of the system. Considering different inventory policies, the corresponding models have been formulated for linear trend in demand and interval valued cost parameters. In OW, shortages, if any, are allowed and partially backlogged with a variable rate dependent on the duration of the waiting time up to the arrival of the next lot. The corresponding optimization problems have been formulated as non-linear constrained optimization problems with interval parameters. These problems have been solved by an efficient soft computing method, viz. practical swarm optimization. To illustrate the model, a numerical example has been solved with different partially backlogging rates. Then to study the effect of changes of different system parameters on the optimal policy, sensitivity analyses have been carried out graphically by changing one parameter at a time and keeping the others at their original values. Finally, a fruitful conclusion has been reached regarding the selection of an appropriate inventory policy of the two-warehouse system.     

An anytime multistep anticipatory algorithm for online stochastic combinatorial optimization

The one-step anticipatory algorithms (1s-AA) is an online algorithm making decisions under uncertainty by ignoring the non-anticipativity constraints in the future. It was shown to make near-optimal decisions on a variety of online stochastic combinatorial problems in dynamic fleet management and reservation systems. Here we consider applications in which 1s-AA is not as close to the optimum and propose Amsaa, an anytime multi-step anticipatory algorithm. Amsaa combines techniques from three different fields to make decisions online. It uses the sampling average approximation method from stochastic programming, search algorithms for Markov decision processes from artificial intelligence, and discrete optimization algorithms. Amsaa was evaluated on a stochastic project scheduling application from the pharmaceutical industry featuring endogenous observations of the uncertainty. The experimental results show that Amsaa significantly outperforms state-of-the-art algorithms on this application under various time constraints.     

Dynamic consistency for stochastic optimal control problems

For a sequence of dynamic optimization problems, we aim at discussing a notion of consistency over time. This notion can be informally introduced as follows. At the very first time step?t ₀, the decision maker formulates an optimization problem that yields optimal decision rules for all the forthcoming time steps?t ₀,t ₁,??,T; at the next time step?t ₁, he is able to formulate a new optimization problem starting at time?t ₁ that yields a new sequence of optimal decision rules. This process can be continued until the final time?T is reached. A?family of optimization problems formulated in this way is said to be dynamically consistent if the optimal strategies obtained when solving the original problem remain optimal for all subsequent problems. The notion of dynamic consistency, well-known in the field of economics, has been recently introduced in the context of risk measures, notably by Artzner et al. (Ann. Oper. Res. 152(1):5?C22, 2007) and studied in the stochastic programming framework by Shapiro (Oper. Res. Lett. 37(3):143?C147, 2009) and for Markov Decision Processes (MDP) by Ruszczynski (Math. Program. 125(2):235?C261, 2010). We here link this notion with the concept of ??state variable?? in MDP, and show that a significant class of dynamic optimization problems are dynamically consistent, provided that an adequate state variable is chosen.     

Numerical method for a dynamic optimization problem arising in the modeling of a population of aerosol particles

A model coupling differential equations and a sequence of constrained optimization problems is proposed for the simulation of the evolution of a population of particles at equilibrium interacting through a common medium.The first order optimality conditions of the optimization problems relaxed with barrier functions are coupled with the differential equations into a system of differential-algebraic equations that is discretized in time with an implicit first order scheme. The resulting system of nonlinear algebraic equations is solved at each time step with an interior-point/Newton method. The Newton system is block-structured and solved with Schur complement techniques, in order to take advantage of its sparsity. Application to the dynamics of a population of organic atmospheric aerosol particles is given to illustrate the evolution of particles of different sizes. To cite this article: A. Caboussat, A. Leonard, C. R. Acad. Sci. Paris, Ser. I 346 (2008).     

Dynamic multiple criteria decision making in changeable spaces: from habitual domains to innovation dynamics

Human behaviors involve dynamic, evolving, interactive and adaptive processes. Important decision makings usually are dynamic, involving multiple criteria in changeable spaces. This article introduces the behavior mechanism that integrates the findings of neural science, psychology, system science, optimization theory and multiple criteria decision making. It shows how our brain and mind operate and describes our behaviors and decision making as dynamic processes of multiple criteria decision making in changeable spaces. Unless extraordinary events occur or special effort exerted, the dynamic processes will be stabilized in certain domains, known as Habitual Domains. Habitual Domains, which play a vital role in upgrading the quality of our decision making and lives, will be explored. In addition, as important consequential derivatives, concepts of Competence Set Analysis and Innovation Dynamics will also be discussed. Note that these concepts involve transitions between dynamic and static states.     

Hybrid chaos optimization algorithm with artificial emotion

Much research on Artificial Intelligence (AI) has been focusing on exploring various potential applications of intelligent systems. In most cases, the researches attempt to model human intelligence by mimicking the brain structure and function, but they ignore an important aspect in human learning and decision making: the artificial emotion. In this paper, we present a new unconstrained global optimization method, hybrid chaos optimization algorithm with artificial emotion (HCOAAE), which avoids trapping to local minima, and improves convergence in large space and high-dimension optimization problems. The main purpose of artificial emotion is to mimic decision making behavior process of humans, to choose most suitable parameters of HCOAAE and decide whether to change current search strategy or not in the next iteration. Numerical simulations of 13 benchmark functions with different dimensions are used to test the performance of HCOAAE. Experimental results show that the proposed method significantly outperforms the existing methods in terms of convergence speed, computational effectiveness, and numerical stability.     

Interactive Polyhedral Outer Approximation (IPOA) strategy for general multiobjective optimization problems

We propose an interactive polyhedral outer approximation (IPOA) method to solve a broad class of multiobjective optimization problems (MOP) with, possibly, nonlinear and nondifferentiable objective and constraint functions, and with continuous or discrete decision variables. During the interactive optimization phase, the method progressively constructs a polyhedral approximation of the decision-maker’s (DM’s) unknown preference structure and a polyhedral outer-approximation of the feasible set of MOP. The piecewise linear approximation of the DM’s preferences also provides a mechanism for testing the consistency of the DM’s assessments and removing inconsistencies; it also allows post-optimality analysis. All the feasible trial solutions are non-dominated (efficient, or Pareto-optimal) so preference assessments are made in the context of non-dominated alternatives only. Upper and lower bounds on the yet unknown optimal value are produced at every iteration, allowing terminating the search prematurely at a good-enough solution and providing information about the closeness of this solution to the optimal solution. The IPOA method includes a preliminary phase in which a limited probe of the efficient set is conducted in order to find a good initial trial solution for the interactive phase. The computational requirements of the algorithm are relatively simple. The results of an extensive computational study are reported.     

Finding largest small polygons with GloptiPoly

A small polygon is a convex polygon of unit diameter. We are interested in small polygons which have the largest area for a given number of vertices n. Many instances are already solved in the literature, namely for all odd n, and for n = 4, 6 and 8. Thus, for even n ≥ 10, instances of this problem remain open. Finding those largest small polygons can be formulated as nonconvex quadratic programming problems which can challenge state-of-the-art global optimization algorithms. We show that a recently developed technique for global polynomial optimization, based on a semidefinite programming approach to the generalized problem of moments and implemented in the public-domain Matlab package GloptiPoly, can successfully find largest small polygons for n = 10 and n = 12. Therefore this significantly improves existing results in the domain. When coupled with accurate convex conic solvers, GloptiPoly can provide numerical guarantees of global optimality, as well as rigorous guarantees relying on interval arithmetic.     

Least squares problems with inequality constraints as quadratic constraints

Linear least squares problems with box constraints are commonly solved to find model parameters within bounds based on physical considerations. Common algorithms include Bounded Variable Least Squares (BVLS) and the Matlab function lsqlin. Here, the goal is to find solutions to ill-posed inverse problems that lie within box constraints. To do this, we formulate the box constraints as quadratic constraints, and solve the corresponding unconstrained regularized least squares problem. Using box constraints as quadratic constraints is an efficient approach because the optimization problem has a closed form solution. The effectiveness of the proposed algorithm is investigated through solving three benchmark problems and one from a hydrological application. Results are compared with solutions found by lsqlin, and the quadratically constrained formulation is solved using the L-curve, maximum a posteriori estimation (MAP), and the χ² regularization method. The χ² regularization method with quadratic constraints is the most effective method for solving least squares problems with box constraints.