Optimal construction and rebalancing of index-tracking portfolios

Index funds aim to track the performance of a financial index, such as, e.g., the Standard?&?Poor’s?500 index. Index funds have become popular because they offer attractive risk-return profiles at low costs. The index-tracking problem considered in this paper consists of rebalancing the composition of the index fund’s tracking portfolio in response to new market information and cash deposits and withdrawals from investors such that the index fund’s tracking accuracy is maximized. In a frictionless market, maximum tracking accuracy is achieved by investing the index fund’s entire capital in a tracking portfolio that has the same normalized value development as the index. In the presence of transaction costs, which reduce the fund’s capital, one has to manage the trade-off between transaction costs and similarity in terms of normalized value developments. Existing mathematical programing formulations for the index-tracking problem do not optimize this trade-off explicitly, which may result in substantial transaction costs or tracking portfolios that differ considerably from the index in terms of normalized value development. In this paper, we present a mixed-integer linear programing formulation with a novel optimization criterion that directly considers the trade-off between transaction costs and similarity in terms of normalized value development. In an experiment based on a set of real-world problem instances, the proposed formulation achieves a considerably higher tracking accuracy than state-of-the-art formulations.     

Revisiting dynamic programming for finding optimal subtrees in trees

In this paper we revisit an existing dynamic programming algorithm for finding optimal subtrees in edge weighted trees. This algorithm was sketched by Maffioli in a technical report in 1991. First, we adapt this algorithm for the application to trees that can have both node and edge weights. Second, we extend the algorithm such that it does not only deliver the values of optimal trees, but also the trees themselves. Finally, we use our extended algorithm for developing heuristics for the k-cardinality tree problem in undirected graphs G with node and edge weights. This NP-hard problem consists of finding in the given graph a tree with exactly k edges such that the sum of the node and the edge weights is minimal. In order to show the usefulness of our heuristics we conduct an extensive computational analysis that concerns most of the existing problem instances. Our results show that with growing problem size the proposed heuristics reach the performance of state-of-the-art metaheuristics. Therefore, this study can be seen as a cautious note on the scaling of metaheuristics.     

Sequential buying policies

This paper deals with the problem of a decision maker trying to purchase a certain number of units of an item at the lowest total purchasing cost within a given number of time periods. At the beginning of every period, the decision maker must decide whether or not to pay a fee to search for a seller. Once a seller is found, he offers a price to him under the realization that the price may be rejected. Assume that a maximum of one unit of item can be purchased every period. This paper develops a dynamic model which provides decision rules that consist of pricing policies and search rules for the decision maker.     

Dynamic uncapacitated lot sizing with random demand under a fillrate constraint

This paper deals with the single-item dynamic uncapacitated lot sizing problem with random demand. We propose a model based on the “static uncertainty” strategy of Bookbinder and Tan (1988). In contrast to these authors, we use exact expressions for the inventory costs and we apply a fillrate constraint. We present an exact solution method and modify several well-known dynamic lot sizing heuristics such that they can be applied for the case of dynamic stochastic demands. A numerical experiment shows that there are significant differences in the performance of the heuristics whereat the ranking of the heuristics is different from that reported for the case of deterministic demand.     

The profit maximizing capacitated lot-size (PCLSP) problem

This paper extends the results for capacitated lot-sizing research to include pricing. Based on a few examples, the new version appears to by much easier to solve computationally. The paper, by including price, can modify demand as well as production schedule. Due to model assumptions (form of demand) a feasible solution can be found easily, unlike CLSP.     

Non-randomized policies for constrained Markov decision processes

This paper addresses constrained Markov decision processes, with expected discounted total cost criteria, which are controlled by non-randomized policies. A dynamic programming approach is used to construct optimal policies. The convergence of the series of finite horizon value functions to the infinite horizon value function is also shown. A simple example illustrating an application is presented.     

在寿命周期内具有抛物型需求的物品的最优补充模型

本文建立了在寿命周期内具有二次抛物需求的物品的一个确定型最优批量模型,提供了产生最优补充策略的一个简单的动态规划方法,用数字例子说明了该模型的求解过程,并出示了模型参数的灵敏度分析．     

Dynamic decision making for graphical models applied to oil exploration

We present a framework for sequential decision making in problems described by graphical models. The setting is given by dependent discrete random variables with associated costs or revenues. In our examples, the dependent variables are the potential outcomes (oil, gas or dry) when drilling a petroleum well. The goal is to develop an optimal selection strategy of wells that incorporates a chosen utility function within an approximated dynamic programming scheme. We propose and compare different approximations, from naive and myopic heuristics to more complex look-ahead schemes, and we discuss their computational properties. We apply these strategies to oil exploration over multiple prospects modeled by a directed acyclic graph, and to a reservoir drilling decision problem modeled by a Markov random field. The results show that the suggested strategies clearly improve the naive or myopic constructions used in petroleum industry today. This is useful for decision makers planning petroleum exploration policies.     

Keep or return? Managing ordering and return policies in start-up companies

Start-up companies are considered an important factor in the success of a nation’s economy. We are interested in the decisions for long-term survival of these firms when they have considerable cash restrictions. In this paper we analyse several inventory control models to manage inventory purchasing and return policies. The Markov decision models are formulated for both established companies that look at maximising average profit and start-up companies that look at maximising their long-term survival probability. We contrast both objectives, and present properties of the policies and the survival probabilities. We find that start-up companies may need to be riskier if the return price is very low, but there is a period where a start-up firm becomes more cautious than an established company and there is a point, as it accumulates capital, where it starts behaving as an established firm. We compare the various models and give conditions under which their policies are equivalent.     

A dynamic programming based reduction procedure for the multidimensional 0–1 knapsack problem

This paper presents a preprocessing procedure for the 0–1 multidimensional knapsack problem. First, a non-increasing sequence of upper bounds is generated by solving LP-relaxations. Then, a non-decreasing sequence of lower bounds is built using dynamic programming. The comparison of the two sequences allows either to prove that the best feasible solution obtained is optimal, or to fix a subset of variables to their optimal values. In addition, a heuristic solution is obtained. Computational experiments with a set of large-scale instances show the efficiency of our reduction scheme. Particularly, it is shown that our approach allows to reduce the CPU time of a leading commercial software.     

Optimal ordering policies for periodic-review systems with a refined intra-cycle time scale

Chiang [C. Chiang, Optimal ordering policies for periodic-review systems with replenishment cycles, European Journal of Operational Research 170 (2006) 44–56] recently proposed a dynamic programming model for periodic-review systems in which a replenishment cycle consists of a number of small periods (each of identical but arbitrary length) and holding and shortage costs are charged based on the ending inventory of small periods. The current paper presents an alternative (and concise) dynamic programming model. Moreover, we allow the possibility of a positive fixed cost of ordering. The optimal policy is of the familiar (s, S) type because of the convexity of the one-cycle cost function. As in the periodic-review inventory literature, we extend this result to the lost-sales periodic problem with zero lead-time. Computation shows that the long-run average cost is rather insensitive to the choice of the period length. In addition, we show how the proposed model is modified to handle the backorder problem where shortage is charged on a per-unit basis irrespective of its duration. Finally, we also investigate the lost-sales problem with positive lead-time, and provide some computational results.     

Time and inventory dependent optimal maintenance policies for single machine workstations: An MDP approach

In this work the problem of obtaining an optimal maintenance policy for a single-machine, single-product workstation that deteriorates over time is addressed, using Markov Decision Process (MDP) models. Two models are proposed. The decision criteria for the first model is based on the cost of performing maintenance, the cost of repairing a failed machine and the cost of holding inventory while the machine is not available for production. For the second model the cost of holding inventory is replaced by the cost of not satisfying the demand. The processing time of jobs, inter-arrival times of jobs or units of demand, and the failure times are assumed to be random. The results show that in order to make better maintenance decisions the interaction between the inventory (whether in process or final), and the number of shifts that the machine has been working without restoration, has to be taken into account. If this interaction is considered, the long-run operational costs are reduced significantly. Moreover, structural properties of the optimal policies of the models are obtained after imposing conditions on the parameters of the models and on the distribution of the lifetime of a recently restored machine.     

Optimal policies for inventory systems with two types of product sharing common hardware platforms: Single period and finite horizon

In this paper, we consider an inventory system whose products share a common hardware platform but are differentiated by two types of software. Choice of different software results in different installation cost and different selling price of the whole product. Product with different software also faces different customer demand. We investigate the optimal proportion of an order to be installed with software 1 or 2, that maximizes expected profit in the single and multiple period scenarios, respectively. The optimal policy is analytically obtained and proved to be an order-up-to policy in each scenario. Our investigation reveals that whether to replenish, and how much to replenish each product depend not only on its own initial inventory level, and system parameters, but also the initial inventory level of the other product. We perform numerical experiments using the optimal policies we have derived in the paper.     

Optimal intervention policies for a multidimensional simple epidemic process

We consider a deterministic simple epidemic process in which the susceptibles are exposed to n+1 diseases. It is assumed that one disease is relatively harmless while the others cause serious symptoms. Policies for introducing infection by the harmless disease are considered and, under a suitable cost structure, the optimal policy that minimises the future cost for every initial state is found. For the corresponding stochastic model, the optimal policy is found by implementing a suitable dynamic programming algorithm, and is compared numerically with the optimal policy for the deterministic model.     

Optimal ordering policies with convertible lead times

A firm receives orders that will be required at an uncertain time given by an Erlang distribution, and over time observes the associated independent exponential events. The firm, in turn, places orders at a linear cost from a supplier with fixed lead time l and has the option of converting (expediting) each order, at a cost, over a certain time interval after the order is originally placed. A converted order arrives l_e < l units of time after it is converted. We show that a threshold policy is optimal. Under such a policy the firm places an order after a certain number of exponential events have been observed. An order is converted the first time, if any, when the residual lead time exceeds a time threshold related to the number of exponential events realized since the order was placed.     

A linear programming approach for linear programs with probabilistic constraints

We study a class of mixed-integer programs for solving linear programs with joint probabilistic constraints from random right-hand side vectors with finite distributions. We present greedy and dual heuristic algorithms that construct and solve a sequence of linear programs. We provide optimality gaps for our heuristic solutions via the linear programming relaxation of the extended mixed-integer formulation of Luedtke et al. (2010) [13] as well as via lower bounds produced by their cutting plane method. While we demonstrate through an extensive computational study the effectiveness and scalability of our heuristics, we also prove that the theoretical worst-case solution quality for these algorithms is arbitrarily far from optimal. Our computational study compares our heuristics against both the extended mixed-integer programming formulation and the cutting plane method of Luedtke et al. (2010) [13]. Our heuristics efficiently and consistently produce solutions with small optimality gaps, while for larger instances the extended formulation becomes intractable and the optimality gaps from the cutting plane method increase to over 5%.     

A distance-based point-reassignment heuristic for the k-hyperplane clustering problem

We consider the k-Hyperplane Clustering problem where, given a set of m   points in Rⁿ${\mathbb{R}}^n$, we have to partition the set into k subsets (clusters) and determine a hyperplane for each of them, so as to minimize the sum of the squares of the Euclidean distances between the points and the hyperplane of the corresponding clusters. We give a nonconvex mixed-integer quadratically constrained quadratic programming formulation for the problem. Since even very small-size instances are challenging for state-of-the-art spatial branch-and-bound solvers like Couenne, we propose a heuristic in which many “critical” points are reassigned at each iteration. Such points, which are likely to be ill-assigned in the current solution, are identified using a distance-based criterion and their number is progressively decreased to zero. Our algorithm outperforms the best available one proposed by Bradley and Mangasarian on a set of real-world and structured randomly generated instances. For the largest instances, we obtain an average improvement in the solution quality of 54%.     

不确定性需求下易逝品零售商横向调货策略研究

本文通过建立易逝品零售商间横向调货模型,研究了不确定性需求与不确定性需求更新零售商之间协调调货行为下最优调货价格和调货量。研究结果表明,在不确定性需求条件下,零售商间横向调货模型中调货价格和调货量的存在纯策略纳什均衡解;在不确定性需求更新条件时,零售商间横向调货价格和调货量在任意时刻均存在纯策略纳什均衡解。数值实验也证实了理论部分的研究结论。