Branching Constraint Satisfaction Problems and Markov Decision Problems Compared

Branching Constraint Satisfaction Problems (BCSPs) model a class of uncertain dynamic resource allocation problems. We describe the features of BCSPs, and show that the associated decision problem is NP-complete. Markov Decision Problems could be used in place of BCSPs, but we show analytically and empirically that, for the class of problems in question, the BCSP algorithms are more efficient than the related MDP algorithms.     

Using the WOWA operator in robust discrete optimization problems

In this paper a class of discrete optimization problems with uncertain costs is discussed. The uncertainty is modeled by introducing a scenario set containing a finite number of cost scenarios. A probability distribution over the set of scenarios is available. In order to choose a solution the weighted OWA criterion (WOWA) is applied. This criterion allows decision makers to take into account both probabilities for scenarios and the degree of pessimism/optimism. In this paper the complexity of the considered class of discrete optimization problems is described and some exact and approximation algorithms for solving it are proposed. Applications to the selection and the assignment problems, together with results of computational tests are shown.     

When are static and adjustable robust optimization problems with constraint-wise uncertainty equivalent?

Adjustable robust optimization (ARO) generally produces better worst-case solutions than static robust optimization (RO). However, ARO is computationally more difficult than RO. In this paper, we provide conditions under which the worst-case objective values of ARO and RO problems are equal. We prove that when the uncertainty is constraint-wise, the problem is convex with respect to the adjustable variables and concave with respect to the uncertain parameters, the adjustable variables lie in a convex and compact set and the uncertainty set is convex and compact, then robust solutions are also optimal for the corresponding ARO problem. Furthermore, we prove that if some of the uncertain parameters are constraint-wise and the rest are not, then under a similar set of assumptions there is an optimal decision rule for the ARO problem that does not depend on the constraint-wise uncertain parameters. Also, we show for a class of problems that using affine decision rules that depend on all of the uncertain parameters yields the same optimal objective value as when the rules depend solely on the non-constraint-wise uncertain parameters. Finally, we illustrate the usefulness of these results by applying them to convex quadratic and conic quadratic problems.     

Multi-objective optimization in uncertain random environments

Uncertain random variables are used to describe the phenomenon of simultaneous appearance of both uncertainty and randomness in a complex system. For modeling multi-objective decision-making problems with uncertain random parameters, a class of uncertain random optimization is suggested for decision systems in this paper, called the uncertain random multi-objective programming. For solving the uncertain random programming, some notions of the Pareto solutions and the compromise solutions as well as two compromise models are defined. Subsequently, some properties of these models are investigated, and then two equivalent deterministic mathematical programming models under some particular conditions are presented. Some numerical examples are also given for illustration.     

Bottleneck combinatorial optimization problems with uncertain costs and the OWA criterion

In this paper a class of bottleneck combinatorial optimization problems with uncertain costs is discussed. The uncertainty is modeled by specifying a discrete scenario set containing a finite number of cost vectors, called scenarios. In order to choose a solution the Ordered Weighted Averaging aggregation operator (OWA for short) is applied. The OWA operator generalizes traditional criteria in decision making under uncertainty such as the maximum, minimum, average, median, or Hurwicz criterion. New complexity and approximation results in this area are provided. These results are general and remain valid for many problems, in particular for a wide class of network problems.     

The existence of good Markov strategies for decision processes with general payoffs

For countable-state decision processes (dynamic programming problems), a general class of objective functions is identified for which it is shown that good Markov strategies always exist. This class includes product and lim inf rewards, as well as practically all the classical dynamic programming expected payoff functions.     

Robust H∞ output dynamic observer-based control of uncertain time-delay systems

In this paper, the robustness and H_∞ control problems of output dynamic observer-based control for a class of uncertain linear systems with time delay are considered. Under no disturbance input, the asymptotic stabilization for uncertain time-delay systems will be guaranteed. Linear matrix inequality (LMI) optimization approach is used to design three classes of the H_∞ output dynamic controls. Based on the results of this paper, the constraint of matrix equality is not necessary for designing the observer-based controls.     

A Unifying Approach to Robust Convex Infinite Optimization Duality

This paper considers an uncertain convex optimization problem, posed in a locally convex decision space with an arbitrary number of uncertain constraints. To this problem, where the uncertainty only affects the constraints, we associate a robust (pessimistic) counterpart and several dual problems. The paper provides corresponding dual variational principles for the robust counterpart in terms of the closed convexity of different associated cones.     

Uncertain random goal programming

Goal programming provides an efficient technique to deal with decision making problems with multiple conflicting objectives. This paper joins the streams of research on goal programming by providing a so-called uncertain random goal programming to model the multi-objective optimization problem involving uncertain random variables. Several equivalent deterministic forms are derived on the condition that the set of parameters consists of uncertain variables and random variables. Finally, an example is given to illustrate the application of the approach.     

An Efficient Algorithm for Non-Point Source Pollution Management Problems

A dynamic programming (DP) algorithm is proposed for a class of non-point source pollution control problems. The formulation deals with the selection of a spatial distribution of management practices in such a way as to meet a control agency's sediment pollution target. The inherently combinatorial nature of these problems — stemming from the discrete nature of the decision variables, which are production, conservation and mechanical control practices — gives them a special integer programming structure. This paper focuses on the DP formulation and the computer implementation of this algorithm. The approach is shown to be informative, robust and relatively efficient. Furthermore, the paper demonstrates that dynamic programming can be used to generate sensitivity analysis information for multiple-choice knapsack problems.     

An uncertain chromatic number of an uncertain graph based on $$\alpha $$-cut coloring

An uncertain graph is a graph in which the edges are indeterminate and the existence of edges are characterized by belief degrees which are uncertain measures. This paper aims to bring graph coloring and uncertainty theory together. A new approach for uncertain graph coloring based on an \(\alpha \)-cut of an uncertain graph is introduced in this paper. Firstly, the concept of \(\alpha \)-cut of uncertain graph is given and some of its properties are explored. By means of \(\alpha \)-cut coloring, we get an \(\alpha \)-cut chromatic number and examine some of its properties as well. Then, a fact that every \(\alpha \)-cut chromatic number may be a chromatic number of an uncertain graph is obtained, and the concept of uncertain chromatic set is introduced. In addition, an uncertain chromatic algorithm is constructed. Finally, a real-life decision making problem is given to illustrate the application of the uncertain chromatic set and the effectiveness of the uncertain chromatic algorithm.     

On a class of dynamic programming problems whose optimal controls and states are independent of the future

When applying dynamic programming for optimal decision making one usually needs considerable knowledge about the future. This knowledge, e.g. about future functions and parameters, necessary to determine optimal control policies, however, is often not available and thus precludes the application of dynamic programming.In the present paper it is shown that for a certain class of dynamic programming problems the optimal control policy is independent of the future. To illustrate the results an application in inventory control is given and further applications in the theories of economic growth and corporate finance are listed in the references.     

On the worst scenario method: A modified convergence theorem and its application to an uncertain differential equation

We propose a theoretical framework for solving a class of worst scenario problems. The existence of the worst scenario is proved through the convergence of a sequence of approximate worst scenarios. The main convergence theorem modifies and corrects the relevant results already published in literature. The theoretical framework is applied to a particular problem with an uncertain boundary value problem for a nonlinear ordinary differential equation with an uncertain coefficient. This research was supported in part by the project MSM4781305904 from the Ministry of Education, Youth and Sports of the Czech Republic.     

Dynamic facility location when the total number of facilities is uncertain: A decision analysis approach

Models developed to analyze facility location decisions have typically optimized one or more objectives, subject to physical, structural, and policy constraints, in a static or deterministic setting. Because of the large capital outlays that are involved, however, facility location decisions are frequently long-term in nature. Consequently, there may be considerable uncertainty regarding the way in which relevant parameters in the location decision will change over time. In this paper, we propose two approaches for analyzing these types of dynamic location problems, focussing on situations where the total number of facilities to be located in uncertain. We term this type of location problem NOFUN (Number Of Facilities Uncertain). We analyze the NOFUN problem using two well-established decision criteria: the minimization of expected opportunity loss (EOL), and the minimization of maximum regret. In general, these criteria assume that there are a finite number of decision options and a finite number of possible states of nature. The minisum EOL criterion assumes that one can assign probabilities for the occurrence of the various states of nature and, therefore, find the initial set of facility locations that minimize the sum of expected losses across all future states. The minimax regret criteria finds the pattern of initial facility locations whose maximum loss is minimized over all possible future states.     

Fuzzy stochastic linear programming: Survey and future research directions

In many real-life problems one has to base decision on information which is both fuzzily imprecise and probabilistically uncertain. Although consistency indexes providing a union nexus between possibilistic and probabilistic representation of uncertainty exist, there are no reliable transformations between them. This calls for new paradigms for incorporating the two kinds of uncertainty into mathematical models. Fuzzy stochastic linear programming is an attempt to fulfill this need. It deals with modelling and problem solving issues related to situations where randomness and fuzziness co-occur in a linear programming framework. In this paper we provide a survey of the essential elements, methods and algorithms for this class of linear programming problems along with promising research directions. Being a survey, the paper includes many references to both give due credit to results in the field and to help readers obtain more detailed information on issues of interest.     

二元不确定语言术语集成算子及在群决策中的应用

针对基于不确定语言评价信息的群决策问题,本文对不确定语言术语进行拓展,定义了包含语言术语权重信息的二元不确定语言术语,并给出能克服目前不确定语言术语集成运算不足的二元不确定语言术语集成运算法则。在此基础上,提出了基于二元不确定语言术语集成算子的群决策方法,并通过算例说明决策方法的可行性和有效性。     

Generalized Envelope Theorems: Applications to Dynamic Programming

We show in this paper that the class of Lipschitz functions provides a suitable framework for the generalization of classical envelope theorems for a broad class of constrained programs relevant to economic models, in which nonconvexities play a key role, and where the primitives may not be continuously differentiable. We give sufficient conditions for the value function of a Lipschitz program to inherit the Lipschitz property and obtain bounds for its upper and lower directional Dini derivatives. With strengthened assumptions we derive sufficient conditions for the directional differentiability, Clarke regularity, and differentiability of the value function, thus obtaining a collection of generalized envelope theorems encompassing many existing results in the literature. Some of our findings are then applied to decision models with discrete choices, to dynamic programming with and without concavity, to the problem of existence and characterization of Markov equilibrium in dynamic economies with nonconvexities, and to show the existence of monotone controls in constrained lattice programming problems.     

Dynamic programming and principles of optimality

A sequential decision model is developed in the context of which three principles of optimality are defined. Each of the principles is shown to be valid for a wide class of stochastic sequential decision problems. The relationship between the principles and the functional equations of dynamic programming is investigated and it is shown that the validity of each of them guarantees the optimality of the dynamic programming solutions. As no monotonicity assumption is made regarding the reward functions, the results presented in this paper resolve certain questions raised in the literature as to the relation among the principles of optimality and the optimality of the dynamic programming solutions.     

Uncertain linguistic Bonferroni mean operators and their application to multiple attribute decision making

In this paper, we investigate the multiple attribute decision making (MADM) problems with uncertain linguistic information. Motivated by the ideal of Bonferroni mean and geometric Bonferroni mean, we develop two aggregation techniques called the uncertain linguistic Bonferroni mean (ULBM) operator and the uncertain linguistic geometric Bonferroni mean (ULGBM) operator for aggregating the uncertain linguistic information. We study its properties and discuss its special cases. For the situations where the input arguments have different importance, we then define the uncertain linguistic weighted Bonferroni mean (ULWBM) operator and the uncertain linguistic weighted geometric Bonferroni mean (ULWGBM) operator, based on which we develop two procedures for multiple attribute decision making under the uncertain linguistic environments. Finally, a practical example is given to verify the developed approach and to demonstrate its practicality and effectiveness.     

Stability analysis of a class of uncertain switched systems on time scale using Lyapunov functions

This paper deals with the stability analysis of a class of uncertain switched systems on non-uniform time domains. The considered class consists of dynamical systems which commute between an uncertain continuous-time subsystem and an uncertain discrete-time subsystem during a certain period of time. The theory of dynamic equations on time scale is used to study the stability of these systems on non-uniform time domains formed by a union of disjoint intervals with variable length and variable gap. Using the concept of common Lyapunov function, sufficient conditions are derived to guarantee the asymptotic stability of this class of systems on time scale with bounded graininess function. The proposed scheme is used to study the leader–follower consensus problem under intermittent information transmissions.