Valuation of project portfolios: An endogenously discounted method

Real options analysis (ROA) has been developed to value assets in which managerial flexibilities create significant value. The methodology is ideal for the valuation of projects in which frequent adjustments (e.g. investment deferral, project scope changes, etc) are necessary in response to the realization of market and technological uncertainties. However, ROA has no practical application when valuing portfolios of multiple concurrent projects sharing resources, as the size of the problem grows exponentially with the number of projects and the length of the time horizon. In this paper an extension of ROA suitable for the valuation of project portfolios with substantial technological uncertainty (e.g. R&D portfolios) is proposed. The method exploits the distributed decision making strategy encountered in most organizations to decompose the portfolio valuation problem into a decision-making sub-problem and a set of single project valuation sub-problems that can be sequentially solved. Discrete event simulation is used for the first sub-problem, while a tailored ROA based strategy is used for the set of valuation sub-problems. A case study from the pharmaceutical industry is used to compare the decision tree analysis (DTA) method and the proposed method.     

CRM决策的序贯优化——以KDD98直邮决策为例

从多阶段、延迟回报的角度来看待CRM中的决策优化问题。以KDD98数据集为例,将邮寄序贯决策定义为一个部分可观察马尔可夫决策模型(POMDP)。提出了模型参数估计的EM算法并用MATLAB实现;用模型对数似然值、BIC统计量选择最佳模型;用向前一步预测对模型进行检验;用Incremental prune算法对模型求解。实证结果表明,POMDP模型可以很好的捕捉客户购买行为的动态变化,对客户的购买有很好的预测效果。在此基础上,说明了如何使用该模型以客户终生价值最大化为目标优化直邮策略。     

A note on Kirkwood's algebraic method for decision problems

The main objectives of this note are to point out some strengths and some limitations of Kirkwood's algebraic method for decision problems, and to propose a modification to address the limitations. The modification is based on the valuation network technique, and it enables us to better relate Kirkwood's method to the graphical techniques of valuation networks and influence diagrams.     

Progressive hedging as a meta-heuristic applied to stochastic lot-sizing

In a great many situations, the data for optimization problems cannot be known with certainty and furthermore the decision process will take place in multiple time stages as the uncertainties are resolved. This gives rise to a need for stochastic programming (SP) methods that create solutions that are hedged against future uncertainty. The progressive hedging algorithm (PHA) of Rockafellar and Wets is a general method for SP. We cast the PHA in a meta-heuristic framework with the sub-problems generated for each scenario solved heuristically. Rather than using an approximate search algorithm for the exact problem as is typically the case in the meta-heuristic literature, we use an algorithm for sub-problems that is exact in its usual context but serves as a heuristic for our meta-heuristic. Computational results reported for stochastic lot-sizing problems demonstrate that the method is effective.     

A framework and a mean-field algorithm for the local control of spatial processes

The Markov Decision Process (MDP) framework is a tool for the efficient modelling and solving of sequential decision-making problems under uncertainty. However, it reaches its limits when state and action spaces are large, as can happen for spatially explicit decision problems. Factored MDPs and dedicated solution algorithms have been introduced to deal with large factored state spaces. But the case of large action spaces remains an issue. In this article, we define graph-based Markov Decision Processes (GMDPs), a particular Factored MDP framework which exploits the factorization of the state space and the action space of a decision problem. Both spaces are assumed to have the same dimension. Transition probabilities and rewards are factored according to a single graph structure, where nodes represent pairs of state/decision variables of the problem. The complexity of this representation grows only linearly with the size of the graph, whereas the complexity of exact resolution grows exponentially. We propose an approximate solution algorithm exploiting the structure of a GMDP and whose complexity only grows quadratically with the size of the graph and exponentially with the maximum number of neighbours of any node. This algorithm, referred to as MF-API, belongs to the family of Approximate Policy Iteration (API) algorithms. It relies on a mean-field approximation of the value function of a policy and on a search limited to the suboptimal set of local policies. We compare it, in terms of performance, with two state-of-the-art algorithms for Factored MDPs: SPUDD and Approximate Linear Programming (ALP). Our experiments show that SPUDD is not generally applicable to solving GMDPs, due to the size of the action space we want to tackle. On the other hand, ALP can be adapted to solve GMDPs. We show that ALP is faster than MF-API and provides solutions of similar quality for most problems. However, for some problems MF-API provides significantly better policies, and in all cases provides a better approximation of the value function of approximate policies. These promising results show that the GMDP model offers a convenient framework for modelling and solving a large range of spatial and structured planning problems, that can arise in many different domains where processes are managed over networks: natural resources, agriculture, computer networks, etc.     

Behavioral optimal insurance

The present work studies the optimal insurance policy offered by an insurer adopting a proportional premium principle to an insured whose decision-making behavior is modeled by Kahneman and Tversky’s Cumulative Prospect Theory with convex probability distortions. We show that, under a fixed premium rate, the optimal insurance policy is a generalized insurance layer (that is, either an insurance layer or a stop–loss insurance). This optimal insurance decision problem is resolved by first converting it into three different sub-problems similar to those in Jin and Zhou (2008); however, as we now demand a more regular optimal solution, a completely different approach has been developed to tackle them. When the premium is regarded as a decision variable and there is no risk loading, the optimal indemnity schedule in this form has no deductibles but a cap; further results also suggests that the deductible amount will be reduced if the risk loading is decreased. As a whole, our paper provides a theoretical explanation for the popularity of limited coverage insurance policies in the market as observed by many socio-economists, which serves as a mathematical bridge between behavioral finance and actuarial science.     

Multiple-retrieval case-based reasoning for course timetabling problems

The structured representation of cases by attribute graphs in a case-based reasoning (CBR) system for course timetabling has been the subject of previous research by the authors. In that system, the case base is organized as a decision tree and the retrieval process chooses those cases that are sub-attribute graph isomorphic to the new case. The drawback of that approach is that it is not suitable for solving large problems. This paper presents a multiple-retrieval approach that partitions a large problem into small solvable sub-problems by recursively inputting the unsolved part of the graph into the decision tree for retrieval. The adaptation combines the retrieved partial solutions of all the partitioned sub-problems and employs a graph heuristic method to construct the whole solution for the new case. We present a methodology which is not dependent upon problem-specific information and which, as such, represents an approach which underpins the goal of building more general timetabling systems. We also explore the question of whether this multiple-retrieval CBR could be an effective initialization method for local search methods such as hill climbing, tabu search and simulated annealing. Significant results are obtained from a wide range of experiments. An evaluation of the CBR system is presented and the impact of the approach on timetabling research is discussed. We see that the approach does indeed represent an effective initialization method for these approaches.     

Using bid data for the management of sequential,multi-unit,online auctions with uniformly distributed bidder valuations

Internet auctions for consumers’ goods are an increasingly popular selling venue. We have observed that many sellers, instead of offering their entire inventory in a single auction, split it into sequential auctions of smaller lots, thereby reducing the negative market impact of larger lots. Information technology also makes it possible to collect and analyze detailed bid data from online auctions. In this paper, we develop and test a new model of sequential online auctions to explore the potential benefits of using real bid data from earlier auctions to improve the management of future auctions. Assuming a typical truth-revealing auction model, we quantify the effect of the lot size on the closing price and derive a closed-form solution for the problem of allocating inventory across multiple auctions when bidder valuation distributions are known. We also develop a decision methodology for allocating inventory across multiple auctions that dynamically incorporates the results of previous auctions as feedback into the management of subsequent auctions, and updating the lot size and number of auctions. We demonstrate how information signals from previous auctions can be used to update the auctioneer’s beliefs about the customers’ valuation distribution, and then to significantly increase the seller’s profit potential. We use several examples to reveal the benefits of using detailed transaction data for the management of sequential, multi-unit, online auctions and we demonstrate how these benefits are influenced by the inventory holding costs, the number of bidders, and the dispersion of consumers’ valuations.     

Probabilistic decision graphs for optimization under uncertainty

This paper provides a survey on probabilistic decision graphs for modeling and solving decision problems under uncertainty. We give an introduction to influence diagrams, which is a popular framework for representing and solving sequential decision problems with a single decision maker. As the methods for solving influence diagrams can scale rather badly in the length of the decision sequence, we present a couple of approaches for calculating approximate solutions. The modeling scope of the influence diagram is limited to so-called symmetric decision problems. This limitation has motivated the development of alternative representation languages, which enlarge the class of decision problems that can be modeled efficiently. We present some of these alternative frameworks and demonstrate their expressibility using several examples. Finally, we provide a list of software systems that implement the frameworks described in the paper.     

Probabilistic decision graphs for optimization under uncertainty

This paper provides a survey on probabilistic decision graphs for modeling and solving decision problems under uncertainty. We give an introduction to influence diagrams, which is a popular framework for representing and solving sequential decision problems with a single decision maker. As the methods for solving influence diagrams can scale rather badly in the length of the decision sequence, we present a couple of approaches for calculating approximate solutions. The modeling scope of the influence diagram is limited to so-called symmetric decision problems. This limitation has motivated the development of alternative representation languages, which enlarge the class of decision problems that can be modeled efficiently. We present some of these alternative frameworks and demonstrate their expressibility using several examples. Finally, we provide a list of software systems that implement the frameworks described in the paper.     

Conjugacy and dynamics in Thompson’s groups

We give a unified solution to the conjugacy problem for Thompson’s groups \(F, \,T\), and \(V\). The solution uses “strand diagrams”, which are similar in spirit to braids and generalize tree-pair diagrams for elements of Thompson’s groups. Strand diagrams are closely related to piecewise-linear functions for elements of Thompson’s groups, and we use this correspondence to investigate the dynamics of elements of \(F\). Though many of the results in this paper are known, our approach is new, and it yields elegant proofs of several old results.     

Multicriteria energy policy investments and energy market clearance via integer programming

The deregulation of energy markets has created a framework for policy making, still under evolution, which is much more complex than the previous one. As a consequence, new requirements need to be met, concerning both technical design and financial management. This framework renders the use of multicriteria techniques attractive. Here, the investments in suppliers, depending on the policy implemented, are formulated as an integer programming problem, which consists of different sub-problems according to the assumptions made and the market’s regulations. The equivalent relaxed problem is a mixed integer programming problem that can represent the clearance of the energy market by considering several criteria besides price and quantity. Nonlinearities are reformulated by inserting additional binary variables so that the solution algorithms are more effective and efficient in most realistic cases. The feasible solutions and the optimal solution that maximizes every time the market regulator’s gain are obtained, after imposing some thresholds on the criteria used to evaluate the different energy technologies, thus creating a decision support system for the regulator.     

Incorporating inventory and routing costs in strategic location models

We consider a supply chain design problem where the decision maker needs to decide the number and locations of the distribution centers (DCs). Customers face random demand, and each DC maintains a certain amount of safety stock in order to achieve a certain service level for the customers it serves. The objective is to minimize the total cost that includes location costs and inventory costs at the DCs, and distribution costs in the supply chain. We show that this problem can be formulated as a nonlinear integer programming model, for which we propose a Lagrangian relaxation based solution algorithm. By exploring the structure of the problem, we find a low-order polynomial algorithm for the nonlinear integer programming problem that must be solved in solving the Lagrangian relaxation sub-problems. We present computational results for several instances of the problem with sizes ranging from 40 to 320 customers. Our results show the benefits of having an integrated supply chain design framework that includes location, inventory, and routing decisions in the same optimization model.     

Viscosity solutions of Eikonal equations on topological networks

In this paper we introduce a notion of viscosity solutions for Eikonal equations defined on topological networks. Existence of a solution for the Dirichlet problem is obtained via representation formulas involving a distance function associated to the Hamiltonian. A comparison theorem based on Ishii’s classical argument yields the uniqueness of the solution.     

Decision Networks

Decision Networks is a technique for solving problems which involve a sequence of decisions. It is similar in style to critical path analysis in that it consists of arrow diagrams which give a visual representation of the problem and are used as a basis for a simple calculation procedure. The technique can deal with deterministic and stochastic problems and in the latter case is more general than decision trees. The decision network approach meets the need for a method of solution for multi-stage decision problems which is easily understood, helps the user to visualize the nature of the problem and is routine in application.     

Time-critical interactive dynamic influence diagram

Multiagent time-critical dynamic decision making is a challenging task in many real-world applications where a trade-off between solution quality and computational tractability is required. In this paper, we present a formal representation for modelling time-critical multiagent dynamic decision problems based on interactive dynamic influence diagrams (I-DIDs). The new representation called time-critical I-DIDs (TC-IDIDs) represents space-temporal abstraction by providing time-index to nodes and the model is defined in terms of the condensed and deployed forms. The condensed form is a static model of TC-IDIDs and can be expanded into its dynamic version. To facilitate the conversion between the two forms, we exploit the notion of object-orientation design to develop flexible and reusable TC-IDIDs. The difficulty on expanding TC-IDIDs is to select a proper time sequence to index nodes in the condensed form so that the expanded TC-IDIDs can be solved efficiently without compromising the quality of the policy. For this purpose, we propose two methods to build the condensed form of TC-IDIDs. We evaluate the solution quality and time complexity in three well-studied problems and provide results in support.     

A Decision Model for a Sequential Testing Problem in civil Engineering

A sequential decision problem in civil engineering is formulatedas a dynamic programming model. A set of theorems lead to amore efficient formulation, permitting the solution routineto be programmed on a microcomputer. The solution is printedin table fonn, directly providing a decision rule usable bythe foreman in the field. The paper illustrates a point whichis becoming increasingly apparent: the power and availabilityof portable computer systems are making many decision problemsamenable to on-site analysis using models based upon rigoroustheory.     

A methodology for assessing eco-efficiency in logistics networks

Recent literature on sustainable logistics networks points to two important questions: (i) How to spot the preferred solution(s) balancing environmental and business concerns? (ii) How to improve the understanding of the trade-offs between these two dimensions? We posit that a visual exploration of the efficient frontier and trade-offs between profitability and environmental impacts are particularly suitable to answer these two questions. The visual representation of the efficient frontier, however, presents two challenges. The first is to obtain a good approximation for such frontier without enumerating all extreme efficient solutions. The second is to obtain a good visual representation of the efficient frontier. We propose a two-phased heuristic to handle these two problems. The algorithm is designed for the multi-objective linear problem with three objectives: minimize costs, cumulative energy demand and waste in a reverse logistics network. We illustrate our approach by designing a complex recycling logistics network in Germany.     

A solution approach to the inventory routing problem in a three-level distribution system

We consider the infinite horizon inventory routing problem in a three-level distribution system with a vendor, a warehouse and multiple geographically dispersed retailers. In this problem, each retailer faces a demand at a deterministic, retailer-specific rate for a single product. The demand of each retailer is replenished either from the vendor through the warehouse or directly from the vendor. Inventories are kept at both the retailers and the warehouse. The objective is to determine a combined transportation (routing) and inventory strategy minimizing a long-run average system-wide cost while meeting the demand of each retailer without shortage. We present a decomposition solution approach based on a fixed partition policy where the retailers are partitioned into disjoint and collectively exhaustive sets and each set of retailers is served on a separate route. Given a fixed partition, the original problem is decomposed into three sub-problems. Efficient algorithms are developed for the sub-problems by exploring important properties of their optimal solutions. A genetic algorithm is proposed to find a near-optimal fixed partition for the problem. Computational results show the performance of the solution approach.     

An efficient algorithm for the bipartite matching problem

The minimum cost bipartite matching problem is considered. An approach based on the solution of a sequence of shortest path sub-problems is proposed. The particular structure of the problem and the use of reduced costs make it possible to devise an efficient “threshold” algorithm to solve these sub-problems. The computational behaviour of the proposed procedure is analyzed.