Selecting the best choice in the full information group interview problem

We consider the problem of selecting the single best choice when several groups of choices are presented sequentially for evaluation. In the so-called group interview problem, we assume that the values of choices are random observations from a known distribution function and derive the optimal search strategy that maximizes the probability of selecting the best among all choices. Under the optimal search strategy derived by means of a dynamic programming technique, a decision maker simply selects the best choice in the group under consideration if its value is higher than the pre-specified decision value for that group. We also consider the optimal ordering strategy for the case where the decision maker is permitted to rearrange the sequence of groups for evaluation. We show that the optimal search and ordering strategies can be applied to many sequential decision problems such as the store location problem.     

Controlling the GI/M/1 queue by conditional acceptance of customers

In this paper we consider the problem of controlling the arrival of customers into a GI/M/1 service station. It is known that when the decisions controlling the system are made only at arrival epochs, the optimal acceptance strategy is of a control-limit type, i.e., an arrival is accepted if and only if fewer than n customers are present in the system. The question is whether exercising conditional acceptance can further increase the expected long run average profit of a firm which operates the system. To reveal the relevance of conditional acceptance we consider an extension of the control-limit rule in which the nth customer is conditionally admitted to the queue. This customer may later be rejected if neither service completion nor arrival has occurred within a given time period since the last arrival epoch. We model the system as a semi-Markov decision process, and develop conditions under which such a policy is preferable to the simple control-limit rule.     

Applications of bulk queues to group testing models with incomplete identification

A population of items is said to be “group-testable”, (i) if the items can be classified as “good” and “bad”, and (ii) if it is possible to carry out a simultaneous test on a batch of items with two possible outcomes: “Success” (indicating that all items in the batch are good) or “failure” (indicating a contaminated batch). In this paper, we assume that the items to be tested arrive at the group-testing centre according to a Poisson process and are served (i.e., group-tested) in batches by one server. The service time distribution is general but it depends on the batch size being tested. These assumptions give rise to the bulk queueing model M/G^(m,M)/1, where m and M(>m) are the decision variables where each batch size can be between m and M. We develop the generating function for the steady-state probabilities of the embedded Markov chain. We then consider a more realistic finite state version of the problem where the testing centre has a finite capacity and present an expected profit objective function. We compute the optimal values of the decision variables (m, M) that maximize the expected profit. For a special case of the problem, we determine the optimal decision explicitly in terms of the Lambert function.     

Direct Estimation of Linear Functionals from Indirect Noisy Observations

The authors study the efficiency of the linear-functional strategy, as introduced by Anderssen in 1986, for inverse problems with observations blurred by Gaussian white noise with known intensity δ. The optimal accuracy is presented and it is shown how this can be achieved by a linear-functional strategy based on the noisy observations. This optimal linear-functional strategy is obtained from Tikhonov regularization of some dual problem. Next, the situation is treated when only a finite number of noisy observations, given beforehand, is available. Under appropriate smoothness assumptions best possible accuracy still can be attained if the number of observations corresponds to the noise intensity in a proper way. It is also shown that, at least asymptotically, this number of observations cannot be reduced.     

Optimal dividends in the dual model

The optimal dividend problem proposed by de Finetti [de Finetti, B., 1957. Su un’impostazione alternativa della teoria collettiva del rischio. In: Transactions of the XVth International Congress of Actuaries, vol. 2. pp. 433-443] is to find the dividend-payment strategy that maximizes the expected discounted value of dividends which are paid to the shareholders until the company is ruined or bankrupt. In this paper, it is assumed that the surplus or shareholders’ equity is a Lévy process which is skip-free downwards; such a model might be appropriate for a company that specializes in inventions and discoveries. In this model, the optimal strategy is a barrier strategy. Hence the problem is to determine b^∗, the optimal level of the dividend barrier. A key tool is the method of Laplace transforms. A variety of numerical examples are provided. It is also shown that if the initial surplus is b^∗, the expectation of the discounted dividends until ruin is the present value of a perpetuity with the payment rate being the drift of the surplus process.     

A Bilevel Stochastic Programming Problem with Random Parameters in the Follower’s Objective Function

Under study is a bilevel stochastic linear programming problem with quantile criterion. Bilevel programming problems can be considered as formalization of the process of interaction between two parties. The first party is a Leader making a decision first; the second is a Follower making a decision knowing the Leader’s strategy and the realization of the random parameters. It is assumed that the Follower’s problem is linear if the realization of the random parameters and the Leader’s strategy are given. The aim of the Leader is the minimization of the quantile function of a loss function that depends on his own strategy and the optimal Follower’s strategy. It is shown that the Follower’s problem has a unique solution with probability 1 if the distribution of the random parameters is absolutely continuous. The lower-semicontinuity of the loss function is proved and some conditions are obtained of the solvability of the problem under consideration. Some example shows that the continuity of the quantile function cannot be provided. The sample average approximation of the problem is formulated. The conditions are given to provide that, as the sample size increases, the sample average approximation converges to the original problem with respect to the strategy and the objective value. It is shown that the convergence conditions hold for almost all values of the reliability level. A model example is given of determining the tax rate, and the numerical experiments are executed for this example.     

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.     

Markov ratio decision processes

A finite-state Markov decision process, in which, associated with each action in each state, there are two rewards, is considered. The objective is to optimize the ratio of the two rewards over an infinite horizon. In the discounted version of this decision problem, it is shown that the optimal value is unique and the optimal strategy is pure and stationary; however, they are dependent on the starting state. Also, a finite algorithm for computing the solution is given.     

Unifying temporal and organizational scales in multiscale decision-making

In enterprise systems, making decisions is a complex task for agents at all levels of the organizational hierarchy. To calculate an optimal course of action, an agent has to include uncertainties and the anticipated decisions of other agents, recognizing that they also engage in a stochastic, game-theoretic reasoning process. Furthermore, higher-level agents seek to align the interests of their subordinates by providing incentives. Incentive-giving and receiving agents need to include the effect of the incentive on their payoffs in the optimal strategy calculations. In this paper, we present a multiscale decision-making model that accounts for uncertainties and organizational interdependencies over time. Multiscale decision-making combines stochastic games with hierarchical Markov decision processes to model and solve multi-organizational-scale and multi-time-scale problems. This is the first model that unifies the organizational and temporal scales and can solve a 3-agent, 3-period problem. Solutions can be derived as analytic equations with low computational effort. We apply the model to a service enterprise challenge that illustrates the applicability and relevance of the model. This paper makes an important contribution to the foundation of multiscale decision theory and represents a key step towards solving the general X-agent, T-period problem.     

Linear programming under uncertainty: A basic property of the optimal solution

Summary We show that if the two-stage linear programming problem under uncertainty has an optimal solution, then it has an optimal solution in which the column vectors corresponding to the positive first stage decision variables are linearly independent. This leads to the result that if an optimal solution exists, then there exists an optimal solution in which not more than m + ¯m of the first stage decision variables are positive. These results extend to the multi-stage case.This research was partially supported by the Office of Naval Research under Contract Nonr-222(83), the National Science Foundation under Contract GP-4593, the Army Research Office under Contract DA-31-124-ARO-D-331 and the University of California. Reproduction in whole or part is permitted for any purpose of the United States Government.     

Optimal reinsurance under risk and uncertainty

This paper deals with the optimal reinsurance problem if both insurer and reinsurer are facing risk and uncertainty, though the classical uncertainty free case is also included. The insurer and reinsurer degrees of uncertainty do not have to be identical. The decision variable is not the retained (or ceded) risk, but its sensitivity with respect to the total claims. Thus, if one imposes strictly positive lower bounds for this variable, the reinsurer moral hazard is totally eliminated.Three main contributions seem to be reached. Firstly, necessary and sufficient optimality conditions are given in a very general setting. Secondly, the optimal contract is often a bang–bang solution, i.e., the sensitivity between the retained risk and the total claims saturates the imposed constraints. Thirdly, the optimal reinsurance problem is equivalent to other linear programming problem, despite the fact that risk, uncertainty, and many premium principles are not linear. This may be important because linear problems may be easily solved in practice, since there are very efficient algorithms.     

Pricing general insurance in a reactive and competitive market

A simple parameterisation is introduced which represents the insurance market’s response to an insurer adopting a pricing strategy determined via optimal control theory. Claims are modelled using a lognormally distributed mean claim size rate, and the market average premium is determined via the expected value principle. If the insurer maximises its expected wealth then the resulting Bellman equation has a moving boundary in state space that determines when it is optimal to stop selling insurance. This stochastic optimisation problem is simplified by the introduction of a stopping time that prevents an insurer leaving and then re-entering the insurance market. Three finite difference schemes are used to verify the existence of a solution to the resulting Bellman equation when there is market reaction. All of the schemes use a front-fixing transformation. If the market reacts, then it is found that the optimal strategy is altered, in that premiums are raised if the strategy is of loss-leading type and lowered if it is optimal for the insurer to set a relatively high premium and sell little insurance.     

Pricing and effort investment for a newsvendor-type product

We investigate a dominant retailer’s optimal joint strategy of pricing and timing of effort investment and analyze how it influences the decision of the manufacturer, the total supply chain profit, and the consumers’ payoff. We consider two pricing schemes of the retailer, namely, dollar markup and percentage markup, and two effort-investment sequences, namely, ex-ante and ex-post. A combination of four cases is analyzed. Our results show that: (1) under the same effort-decision sequence, a percentage-markup pricing scheme leads to higher expected profit for the retailer and the whole supply chain, but a lower expected profit for the manufacturer and a higher retail price for the consumers; (2) under the same markup-pricing strategy, the dominant retailer always prefers to postpone her effort decision until the manufacturer makes a commitment to wholesale price, since it can result in a Pareto-improvement for all the supply chain members. That is, the retailer’s and manufacturer’s expected profits are higher and the consumers pay a lower retail price; and (3) among the four joint strategies, the dominant retailer always prefers the joint strategy of percentage-markup plus ex-post effort decision. However, the dominated manufacturer always prefers the joint strategy of dollar-markup plus ex-post effort decision, which is also beneficial to the end consumers.     

Dismantle or remanufacture?

In this paper we study a firm’s disposition decision for returned end-of-use products, which can either be remanufactured and sold, or dismantled into parts that can be reused. We formulate this problem as a multi-period stochastic dynamic program, and find the structure of the optimal policy, which consists of monotonic switching curves. Specifically, if it is optimal to remanufacture in a given period and for given inventory levels, then it is also optimal to remanufacture when the inventory of part(s) is higher or the inventory of remanufactured product is lower.     

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.     

Customer equilibrium and optimal strategies in Markovian queues in series

We consider series of M/M/m queues with strategic customer behavior. Customers arrive to the first queue and decide whether to enter the system or balk and, if they enter, up to which queue to proceed before departing. Each customer makes an independent decision, with the objective of maximizing her total net benefit, which is equal to the value of service minus a cost due to expected delay. We formulate the customer decision as a game and identify the unique symmetric Nash equilibrium strategy, which is expressed in a backward recursive form. We also analyze the problem of maximizing the total customer welfare and establish the relationship between the equilibrium and the welfare maximizing strategies.     

A stochastic production planning model with a dynamic chance constraint

This paper deals with the optimal production planning for a single product over a finite horizon. The holding and production costs are assumed quadratic as in Holt, Modigliani, Muth and Simon (HMMS) [7] model. The cumulative demand is compound Poisson and a chance constraint is included to guarantee that the inventory level is positive with a probability of at least α at each time point. The resulting stochastic optimization problem is transformed into a deterministic optimal control problem with control variable and of the optimal solution is presented. The form of state variable inequality constraints. A discussion the optimal control (production rate) is obtained as follows: if there exists a time t₁ such that t₁?[O, T]where T is the end of the planning period, then (i) produce nothing until t₁ and (ii) produce at a rate equal to the expected demand plus a ‘correction factor’ between t₁ and T. If t₁ is found to be greater than T, then the optimal decision is to produce nothing and always meet the demand from the inventory.     

考虑品牌差异的双渠道供应链减排与低碳宣传策略

针对双渠道供应链低碳减排、低碳宣传与品牌策略问题,构建微分博弈模型,运用汉密尔顿-雅可比-贝尔曼方程分别求得集中决策和Stackelberg博弈下的低碳减排投入、低碳宣传投入和低碳宣传分担率。研究发现:集中决策情形下产品的减排量始终高于Stackelberg博弈情形下的减排量;产品品牌差异化程度与制造商所承担零售商低碳宣传成本的比例呈正相关;供应链成员的最优低碳宣传策略除了与品牌差异程度相关,还取决于供应链成员在不同渠道边际利润的相对大小;存在一个低碳宣传成本分担率能够实现制造商和零售商协调。并用数值算例验证了本文的相关结论。     

New algorithms and complexity status of the reducibility problem of sequences in open shop scheduling minimizing the makespan

We consider the problem of minimizing the makespan in open shop scheduling. The decision problem whether a given sequence in open shop scheduling is irreducible has already been considered, however, has not been solved yet. A sequence is an acyclic orientation of the Hamming graph K _n ×K _m . Irreducible sequences in open shop are the local optimal elements. We present two variants of algorithms based on the specific properties of the H-comparability graph. The first is polynomial whereas the second is exponential. The irreducibility is co-NP. The stated properties argue whether it belongs to P. The complexity status of the considered decision problem is updated.     

Long-term inventory policy-making through fuzzy decision-making models

The inventory policy, meant as a replenishment rule, has a considerable impact on most firms. The paper considers the determination of optimal inventory policy of firms from a global viewpoint of top management. The inventory is represented as a fuzzy system with the fuzzy inventory level as the output, the fuzzy replenishment as the input and fuzzy demand. The control problem is formulated in terms of decision-making in a fuzzy environment with fuzzy constraints imposed on replenishments, a fuzzy goal for preferable inventory levels to be attained and the fuzzy decision as the intersection of fuzzy constraints and the fuzzy goal at subsequent stages. The planning horizon is infinite. The problem is to find an optimal time-invariant strategy relating the optimal replenishments to the current inventory levels, maximizing the membership function of fuzzy decision. The existence of such a strategy is proved and an algorithm for its determination is given. The optimal time-invariant strategy obtained is represented as a fuzzy conditional statement equated with a fuzzy relation which is the firm's optimal fuzzy replenishment rule.