Using possibilistic logic for modeling qualitative decision: Answer Set Programming algorithms

A qualitative approach to decision making under uncertainty has been proposed in the setting of possibility theory, which is based on the assumption that levels of certainty and levels of priority (for expressing preferences) are commensurate. In this setting, pessimistic and optimistic decision criteria have been formally justified. This approach has been transposed into possibilistic logic in which the available knowledge is described by formulas which are more or less certainly true and the goals are described in a separate prioritized base. This paper adapts the possibilistic logic handling of qualitative decision making under uncertainty in the Answer Set Programming (ASP) setting. We show how weighted beliefs and prioritized preferences belonging to two separate knowledge bases can be handled in ASP by modeling qualitative decision making in terms of abductive logic programming where (uncertain) knowledge about the world and prioritized preferences are encoded as possibilistic definite logic programs and possibilistic literals respectively. We provide ASP-based and possibilistic ASP-based algorithms for calculating optimal decisions and utility values according to the possibilistic decision criteria. We describe a prototype implementing the algorithms proposed on top of different ASP solvers and we discuss the complexity of the different implementations.     

具有模糊报酬的多目标马尔可夫决策规划

给出一种模糊多目标马尔可夫决策规划的定义,即当报酬是模糊函数时的多目标马尔可夫决策规划,并解决求解这种规划的最优策略的方法以及这种多目标规划最优解的判决问题。     

Rough set approach to multiple criteria classification with imprecise evaluations and assignments

Dominance-based Rough Set Approach (DRSA) has been introduced to deal with multiple criteria classification (also called multiple criteria sorting, or ordinal classification with monotonicity constraints), where assignments of objects may be inconsistent with respect to dominance principle. In this paper, we consider an extension of DRSA to the context of imprecise evaluations of objects on condition criteria and imprecise assignments of objects to decision classes. The imprecisions are given in the form of intervals of possible values. In order to solve the problem, we reformulate the dominance principle and introduce second-order rough approximations. The presented methodology preserves well-known properties of rough approximations, such as rough inclusion, complementarity, identity of boundaries and precisiation. Moreover, the meaning of the precisiation property is extended to the considered case. The paper presents also a way to reduce decision tables and to induce decision rules from rough approximations.     

Behavioral multi-criteria decision analysis: the TODIM method with criteria interactions

In this paper a multi-criteria decision aiding model is developed through the use of the Choquet integral. The proposed model is an extension of the TODIM method, which is based on nonlinear Cumulative Prospect Theory. The paper starts by reviewing the first steps of behavioral decision theory. A presentation of the TODIM method follows. The basic concepts of the Choquet integral as related to multi-criteria decision aiding are reviewed. It is also shown how the measures of dominance of the TODIM method can be rewritten through the application of the Choquet integral. From the ordering of decision criteria the fuzzy measures of criteria interactions are computed, which leads to the ranking of alternatives. A case study on the forecasting of property values for rent in a Brazilian city illustrates the proposed model. Results obtained from the use of the Choquet integral are then compared against a previously made usage of the TODIM method. It is concluded that significant advantages exist derived from the use of the Choquet integral. The paper closes with recommendations for future research.     

Grundzüge des Dynamic Programming

Zusammenfassung Es wird ein kurzer Überblick über einige Hauptprobleme des Dynamic Programming — einer speziellen Lösungsmethode zur Auffindung optimaler Lösungen bei mehrstufigen Extremwertsaufgaben — gegeben. Es wird gezeigt, wie in gewissen Fällen die Problemstellung des Linear Programming verallgemeinert und die Aufgabe mit Hilfe dieser Methode gelöst werden kann. Abschließend wird ein Optimalisierungsprinzip angegeben, das eine Kennzeichnung der Aufgaben gestattet, die einer Lösung durch die Methode des Dynamic Programming zugänglich sind.

---

Summary A brief survey is given about several main problems of dynamic programming — a special procedure for finding optimal solutions of multi-stage extremal value problems. It is shown that in certain cases the approach of linear programming can be generalized and the problem be solved by means of this procedure. Finally a principle of optimization is stated which permits a characterization of the problems lending themselves to a solution by means of dynamic programming.

     

GDDP: Generalized Dual Dynamic Programming Theory

This document presents theoretical considerations about the solution of dynamic optimization problems integrating the Benders Theory, the Dynamic Programming approach and the concepts of Control Theory. The so called Generalized Dual Dynamic Programming Theory (GDDP) can be considered as an extension of two previous approaches known as Dual Dynamic Programming (DDP): The first is the work developed by Pereira and Pinto [3–5], which was revised by Velásquez and others [8,9]. The second is the work developed by Read and others [2,6,7].     

模糊积分变换与模糊Choquet积分的一致连续性

在一般非负单调函数空间 m[0 ,a]上引入模糊积分变换与距离的概念 ,证明了这种模糊积分变换与模糊 Choquet积分在 m[0 ,a]上关于这种距离是一致连续的 ,从而说明当 m[0 ,a]上两个函数变化不大时 ,不会使相应的模糊积分变换与模糊 Choquet积分产生较大的变化 .     

The Linear Program approach in multi-chain Markov Decision Processes revisited

Linear Programming is known to be an important and useful tool for solving Markov Decision Processes (MDP). Its derivation relies on the Dynamic Programming approach, which also serves to solve MDP. However, for Markov Decision Processes with several constraints the only available methods are based on Linear Programs. The aim of this paper is to investigate some aspects of such Linear Programs, related to multi-chain MDPs. We first present a stochastic interpretation of the decision variables that appear in the Linear Programs available in the literature. We then show for the multi-constrained Markov Decision Process that the Linear Program suggested in [9] can be obtained from an equivalent unconstrained Lagrange formulation of the control problem. This shows the connection between the Linear Program approach and the Lagrange approach, that was previously used only for the case of a single constraint [3, 14, 15].     

A multiple criteria model for pricing alcoholic beverages

In this paper we discuss the problem of determining optimal price changes in an alcohol sales monopoly. In Finland, the pricing of alcoholic beverages is entrusted to a State Monopoly (Alko Ltd.). The price decisions are considered to be among the most important alcohol policy measures. The pricing problem is not only a profit maximization problem. Other relevant objectives include the restriction of sales with the intention of reducing harmful effects due to alcohol consumption, and the minimization of the impact of price increases on the consumer price index.A multiple criteria model for finding the most preferred solution for the problem of pricing alcoholic beverages is developed. The model includes three criteria: profit (max.), consumption of absolute alcohol (min.), and impact on the consumer price index (min.). Using logarithms of relative changes instead of absolute criterion values makes it possible to operate with a fully linear model.The model can be solved by using any existing multiple criteria decision method. Reflecting our own bias, we use a visual interactive goal programming method developed by Korhonen and Laakso [3] and further refined by Korhonen and Wallenius [4]. The method is implemented on an IBM/PC1 under the name VIG (Visual Interactive Goal Programming).     

A novel approach to Bilevel nonlinear programming

Recently developed methods of monotonic optimization have been applied successfully for studying a wide class of nonconvex optimization problems, that includes, among others, generalized polynomial programming, generalized multiplicative and fractional programming, discrete programming, optimization over the efficient set, complementarity problems. In the present paper the monotonic approach is extended to the General Bilevel Programming GBP Problem. It is shown that (GBP) can be transformed into a monotonic optimization problem which can then be solved by “polyblock” approximation or, more efficiently, by a branch-reduce-and-bound method using monotonicity cuts. The method is particularly suitable for Bilevel Convex Programming and Bilevel Linear Programming.      

Fast local search methods for solving limited memory influence diagrams

Limited memory influence diagrams are graph-based models that describe decision problems with limited information such as planning with teams and/or agents with imperfect recall. Solving a (limited memory) influence diagram is an NP-hard problem, often approached through local search. In this work we give a closer look at k-neighborhood local search approaches. We show that finding a k-neighboring strategy that improves on the current solution is W[1]-hard and hence unlikely to be polynomial-time tractable. We also show that finding a strategy that resembles an optimal strategy (but may have low expected utility) is NP-hard. We then develop fast schema to perform approximate k-local search; experiments show that our methods improve on current local search algorithms both with respect to time and to accuracy.     

Decision support for spare parts acquisition in post product life cycle

A major task in service management is the timely and cost efficient provision of spare parts for durable products. This especially holds good, when the regular production of the product, its components and parts has been discontinued, but customer service still has to be guaranteed for quite a long time. In such post product life cycle period, three options are available to organize the spare parts acquisition, namely (i) setting up a single large order within the final lot of regular production, (ii) performing extra production runs until the end of service and (iii) using remanufacturing to gain spare parts from used products. These three options are characterized by different cost and flexibility properties. Due to the time-variability and uncertainty of demands for spare parts and also that of the returns of used products, it is a challenging task to find out the optimal combination of these three options. In this paper we show how this problem can be modeled and solved by Decision Tree and stochastic Dynamic Programming procedure. Based on the Dynamic Programming approach a heuristic method is proposed, which can be employed to come up with a simple solution procedure for real-world spare parts acquisition problems during the post product life cycle. A numerical example is presented to demonstrate the application of the solution methods described in the paper.     

Note on Multiple Objective Dynamic Programming

A technique for finding MINSUM and MINMAX solutions to multi-criteria decision problems, called Multi Objective Dynamic Programming, capable of handling a wide range of linear, nonlinear, deterministic and stochastic multi-criteria decision problems, is presented and illustrated. Multiple objectives are considered by defining an adjoint state space and solving a (N + 1) terminal optimisation problem. The method efficiently generates both individual (criterion) optima and multiple criteria solutions in a single pass. Sensitivity analysis on weights over the various objectives is easily performed.     

Portfolio selection under possibilistic mean–variance utility and a SMO algorithm

In this paper, we propose a new portfolio selection model with the maximum utility based on the interval-valued possibilistic mean and possibilistic variance, which is a two-parameter quadratic programming problem. We also present a sequential minimal optimization (SMO) algorithm to obtain the optimal portfolio. The remarkable feature of the algorithm is that it is extremely easy to implement, and it can be extended to any size of portfolio selection problems for finding an exact optimal solution.     

The Monotonicity Problem in Finding Roots of Polynomials by Kuhn's Algorithm

In this paper the problem proposed by Kuhn on the presence of a monotonicity property related to the Kuhn's algorithm for finding roots of a polynomials is solved in the affirmative. Furthermore, an estimate of the threshold number D in the above-mentioned monotonicity problem expressed in terms of the complex coefficients of the polynomial is obtained.     

An a posteriori decision support methodology for solving the multi-criteria supplier selection problem

This research presents a novel, state-of-the-art methodology for solving a multi-criteria supplier selection problem considering risk and sustainability. It combines multi-objective optimization with the analytic network process to take into account sustainability requirements of a supplier portfolio configuration. To integrate ‘risk’ into the supplier selection problem, we develop a multi-objective optimization model based on the investment portfolio theory introduced by Markowitz. The proposed model is a non-standard portfolio selection problem with four objectives: (1) minimizing the purchasing costs, (2) selecting the supplier portfolio with the highest logistics service, (3) minimizing the supply risk, and (4) ordering as much as possible from those suppliers with outstanding sustainability performance. The optimization model, which has three linear and one quadratic objective function, is solved by an algorithm that analytically computes a set of efficient solutions and provides graphical decision support through a visualization of the complete and exactly-computed Pareto front (a posteriori approach). The possibility of computing all Pareto-optimal supplier portfolios is beneficial for decision makers as they can compare all optimal solutions at once, identify the trade-offs between the criteria, and study how the different objectives of supplier portfolio configuration may be balanced to finally choose the composition that satisfies the purchasing company's strategy best. The approach has been applied to a real-world supplier portfolio configuration case to demonstrate its applicability and to analyze how the consideration of sustainability requirements may affect the traditional supplier selection and purchasing goals in a real-life setting.     

下层存在多追随者的分层次线性诱导决策问题及算法

本文讨论上层决策给定的条件下,下层存在多追随者的多目标分层次诱 导决策问题．在线性情况下,此类问题的最优解可在有界多面体区域的某个端点实 现;应用罚函数理论,原决策问题转换为一个在有界多面体区域求连续凸函数最大值 的最优化问题．建议采用的计算方法较为简单,容易实现,而且能够保证求出问题的 全局最优解．     

Valuating residential real estate using parametric programming

When the estimation of the single equation multiple linear regression model is looked upon as an optimization problem, we show how the principles and methods of optimization can assist the analyst in finding an attractive prediction model. We illustrate this with the estimation of a linear prediction model for valuating residential property using regression quantiles. We make use of the linear parametric programming formulation to obtain the family of regression quantile models associated with a data set. We use the principle of dominance to reduce the number of models for consideration in the search for the most preferred property valuation model (s). We also provide useful displays that assist the analyst and the decision maker in selecting the final model (s). The approach is an interface between data analysis and operations research.     

Solving Large-Scale Fuzzy and Possibilistic Optimization Problems

Fuzzy and possibilistic optimization methods are demonstrated to be effective tools in solving large-scale problems. In particular, an optimization problem in radiation therapy with various orders of complexity from 1000 to 62,250 constraints for fuzzy and possibilistic linear and nonlinear programming implementations possessing (1) fuzzy or soft inequalities, (2) fuzzy right-hand side values, and (3) possibilistic right-hand side is used to demonstrate that fuzzy and possibilistic optimization methods are tractable and useful. We focus on the uncertainty in the right side of constraints which arises, in the context of the radiation therapy problem, from the fact that minimal and maximal radiation tolerances are ranges of values, with preferences within the range whose values are based on research results, empirical findings, and expert knowledge, rather than fixed real numbers. The results indicate that fuzzy/possibilistic optimization is a natural and effective way to model various types of optimization under uncertainty problems and that large fuzzy and possibilistic optimization problems can be solved efficiently.