Adaptive integration for multi-factor portfolio credit loss models

We propose algorithms of adaptive integration for calculation of the tail probability in multi-factor credit portfolio loss models. We first modify the classical Genz-Malik rule, a deterministic multiple integration rule suitable for portfolio credit models with number of factors less than 8. Later on we arrive at the adaptive Monte Carlo integration, which essentially replaces the deterministic integration rule by antithetic random numbers. The latter can not only handle higher-dimensional models but is also able to provide reliable probabilistic error bounds. Both algorithms are asymptotic convergent and consistently outperform the plain Monte Carlo method.     

The Express heuristic for probabilistically constrained integer problems

Integer problems under joint probabilistic constraints with random coefficients in both sides of the constraints are extremely hard from a computational standpoint since two different sources of complexity are merged. The first one is related to the challenging presence of probabilistic constraints which assure the satisfaction of the stochastic constraints with a given probability, whereas the second one is due to the integer nature of the decision variables. In this paper we present a tailored heuristic approach based on alternating phases of exploration and feasibility repairing which we call Express (Explore and Repair Stochastic Solution) heuristic. The exploration is carried out by the iterative solution of simplified reduced integer problems in which probabilistic constraints are discarded and deterministic additional constraints are adjoined. Feasibility is restored through a penalty approach. Computational results, collected on a probabilistically constrained version of the classical 0–1 multiknapsack problem, show that the proposed heuristic is able to determine good quality solutions in a limited amount of time.     

Managing a portfolio of long term service agreements

Long-term service agreements (LTSAs) for the maintenance of capital-intensive equipments such as gas turbines and aircraft engines are gaining wide acceptance. A typical LTSA contract spans over a period of around 10 years making a manufacturer fully responsible for maintaining the customer equipment. In this paper, we address the management of a portfolio of such contracts from the manufacturer’s perspective. The goal is to meet all the service requirements imposed by the contracts while minimizing total cost incurred. We develop a deterministic integer programming model to generate the optimal maintenance schedules that minimize the total portfolio cost. We then propose two heuristic algorithms for the problem.     

Safety first portfolio choice based on financial and sustainability returns

The aim of this paper is to expand the methodological spectrum of socially responsible investing by introducing stochastic sustainability returns into safety first models for portfolio choice. We provide a foundation of the notion of sustainability in portfolio theory and establish a general model for generalized safety first portfolio management with probabilistic constraints and three specifications of it. Moreover, we prove theorems about conditions for unique optimal solutions and for the constraints of one model being more restrictive than those of another. In an empirical part, we calculate the costs of investing according to our approach in terms of less financial return.     

A location–allocation heuristic for the capacitated multi-facility Weber problem with probabilistic customer locations

The capacitated multi-facility Weber problem is concerned with locating m facilities in the Euclidean plane, and allocating their capacities to n customers at minimum total cost. The deterministic version of the problem, which assumes that customer locations and demands are known with certainty, is a non-convex optimization problem and difficult to solve. In this work, we focus on a probabilistic extension and consider the situation where the customer locations are randomly distributed according to a bivariate distribution. We first present a mathematical programming formulation, which is even more difficult than its deterministic version. We then propose an alternate location–allocation local search heuristic generalizing the ideas used originally for the deterministic problem. In its original form, the applicability of the heuristic depends on the calculation of the expected distances between the facilities and customers, which can be done for only very few distance and probability density function combinations. We therefore propose approximation methods which make the method applicable for any distance function and bivariate location distribution.     

A generalized stochastic goal programming model

In this paper we show how one can get stochastic solutions of Stochastic Multi-objective Problem (SMOP) using goal programming models. In literature it is well known that one can reduce a SMOP to deterministic equivalent problems and reduce the analysis of a stochastic problem to a collection of deterministic problems. The first sections of this paper will be devoted to the introduction of deterministic equivalent problems when the feasible set is a random set and we show how to solve them using goal programming technique. In the second part we try to go more in depth on notion of SMOP solution and we suppose that it has to be a random variable. We will present stochastic goal programming model for finding stochastic solutions of SMOP. Our approach requires more computational time than the one based on deterministic equivalent problems due to the fact that several optimization programs (which depend on the number of experiments to be run) needed to be solved. On the other hand, since in our approach we suppose that a SMOP solution is a random variable, according to the Central Limit Theorem the larger will be the sample size and the more precise will be the estimation of the statistical moments of a SMOP solution. The developed model will be illustrated through numerical examples.     

Stochastic scheduling to minimize expected maximum lateness

This paper is concerned with the problems in scheduling a set of jobs associated with random due dates on a single machine so as to minimize the expected maximum lateness in stochastic environment. This is a difficult problem and few efforts have been reported on its solution in the literature. In this paper, we first derive a deterministic equivalent to the expected maximum lateness and then propose a dynamic programming algorithm to obtain the optimal solutions. The procedures to compute optimal solutions are initially developed in the case of deterministic processing times, and then extended to stochastic processing times following arbitrary probability distributions. Moreover, several heuristic rules are suggested to compute near-optimal solutions, which are shown to be highly efficient and accurate by computer-based experiments.     

Time asymptotics for solutions of the Burgers equation with a periodic force

We consider the Burgers equation with a periodic force which presents a simplified model for turbulence. We are interested in the asymptotic behaviour of solutions for . This problem has been studied by Sinai who uses a probabilistic and very technical approach. Using methods from spectral theory we get similar results. This functional analytic approach gives an easier proof. For certain initial data (periodic or some random perturbations of those) we show time-convergence towards a deterministic periodic limit solution related to the ground state of a certain Schr?dinger operator. Received June 10, 1998     

Dynamic traveling salesman problem with stochastic release dates

The dynamic traveling salesman problem with stochastic release dates (DTSP-srd) is a problem in which a supplier has to deliver parcels to its customers. These parcels are delivered to its depot while the distribution is taking place. The arrival time of a parcel to the depot is called its release date. In the DTSP-srd, release dates are stochastic and dynamically updated as the distribution takes place. The objective of the problem is the minimization of the total time needed to serve all customers, given by the sum of the traveling time and the waiting time at the depot. The problem is represented as a Markov Decision Process and is solved through a reoptimization approach. Two models are proposed for the problem to be solved at each stage. The first model is stochastic and exploits the entire probabilistic information available for the release dates. The second model is deterministic and uses an estimation of the release dates. An instance generation procedure is proposed to simulate the evolution of the information to perform computational tests. The results show that a more frequent reoptimization provides better results across all tested instances and that the stochastic model performs better than the deterministic model. The main drawback of the stochastic model lies in the computational time required to evaluate a solution, which makes an iteration of the heuristic substantially more time-consuming than in the case where the deterministic model is used.     

Re-solving stochastic programming models for airline revenue management

We study some mathematical programming formulations for the origin-destination model in airline revenue management. In particular, we focus on the traditional probabilistic model proposed in the literature. The approach we study consists of solving a sequence of two-stage stochastic programs with simple recourse, which can be viewed as an approximation to a multi-stage stochastic programming formulation to the seat allocation problem. Our theoretical results show that the proposed approximation is robust, in the sense that solving more successive two-stage programs can never worsen the expected revenue obtained with the corresponding allocation policy. Although intuitive, such a property is known not to hold for the traditional deterministic linear programming model found in the literature. We also show that this property does not hold for some bid-price policies. In addition, we propose a heuristic method to choose the re-solving points, rather than re-solving at equally-spaced times as customary. Numerical results are presented to illustrate the effectiveness of the proposed approach.     

Solving the Dirichlet problem for Navier–Stokes equations by probabilistic approach

We construct a number of layer methods for Navier-Stokes equations (NSEs) with no-slip boundary conditions. The methods are obtained using probabilistic representations of solutions to NSEs and exploiting ideas of the weak sense numerical integration of stochastic differential equations. Despite their probabilistic nature, the proposed methods are nevertheless deterministic.     

Solving the maximum clique problem using a tabu search approach

We describe two variants of a tabu search heuristic, a deterministic one and a probabilistic one, for the maximum clique problem. This heuristic may be viewed as a natural alternative implementation of tabu search for this problem when compared to existing ones. We also present a new random graph generator, the -generator, which produces graphs with larger clique sizes than comparable ones obtained by classical random graph generating techniques. Computational results on a large set of test problems randomly generated with this new generator are reported and compared with those of other approximate methods.The authors are grateful to the Quebec Government (Fonds F.C.A.R.) and to the Canadian Natural Sciences and Engineering Research Council (grant 0GP0038816) for financial support.     

Minimum power multicasting in wireless networks under probabilistic node failures

In this paper we deal with a probabilistic extension of the minimum power multicast (MPM) problem for wireless networks. The deterministic MPM problem consists in assigning transmission powers to the nodes, so that a multihop connection can be established between a source and a given set of destination nodes and the total power required is minimized. We present an extension to the basic problem, where node failure probabilities for the transmission are explicitly considered. This model reflects the necessity of taking uncertainty into account in the availability of the hosts. The novelty of the probabilistic minimum power multicast (PMPM) problem treated in this paper consists in the minimization of the assigned transmission powers, imposing at the same time a global reliability level to the solution network. An integer linear programming formulation for the PMPM problem is presented. Furthermore, an exact algorithm based on an iterative row and column generation procedure, as well as a heuristic method are proposed. Computational experiments are finally presented.     

A new method for mean-variance portfolio optimization with cardinality constraints

Several portfolio selection models take into account practical limitations on the number of assets to include and on their weights in the portfolio. We present here a study of the Limited Asset Markowitz (LAM) model, where the assets are limited with the introduction of quantity and cardinality constraints. We propose a completely new approach for solving the LAM model based on a reformulation as a Standard Quadratic Program, on a new lower bound that we establish, and on other recent theoretical and computational results for such problem. These results lead to an exact algorithm for solving the LAM model for small size problems. For larger problems, such algorithm can be relaxed to an efficient and accurate heuristic procedure that is able to find the optimal or the best-known solutions for problems based on some standard financial data sets that are used by several other authors. We also test our method on five new data sets involving real-world capital market indices from major stock markets. We compare our results with those of CPLEX and with those obtained with very recent heuristic approaches in order to illustrate the effectiveness of our method in terms of solution quality and of computation time. All our data sets and results are publicly available for use by other researchers.     

A multi-heuristic approach for solving the pre-marshalling problem

Minimizing the number of reshuffling operations at maritime container terminals incorporates the pre-marshalling problem (PMP) as an important problem. Based on an analysis of existing solution approaches we develop new heuristics utilizing specific properties of problem instances of the PMP. We show that the heuristic performance is highly dependent on these properties. We introduce a new method that exploits a greedy heuristic of four stages, where for each of these stages several different heuristics may be applied. Instead of using randomization to improve the performance of the heuristic, we repetitively generate a number of solutions by using a combination of different heuristics for each stage. In doing so, only a small number of solutions is generated for which we intend that they do not have undesirable properties, contrary to the case when simple randomization is used. Our experiments show that such a deterministic algorithm significantly outperforms the original nondeterministic method. The improvement is twofold, both in the quality of found solutions, and in the computational effort.     

基于随机因子模型的增强型指数基金

创新性的假设传统的Fama-French三因素模型中的三因素为服从正态分布的随机变量,进而获得了股票收益随机变量的分布信息.采取部分复制的原则建立增强型指数基金随机投资组合优化模型,通过引入投资组合风险概率约束给出增强型指数基金的绝对风险上限,针对增强型指数基金建立基于VaR的超额收益概率约束.引入最买入门槛限制降低增强型指数基金的管理费用,增强其流动性.最后,根据股票收益的概率分布特征,获得基于上述约束的指数基金和增强型指数基金的确定性优化模型,并同时基于上证A股进行了实证分析.     

Telecommunication Link Restoration Planning with Multiple Facility Types

To ensure uninterrupted service, telecommunication networks contain excess (spare) capacity for rerouting (restoring) traffic in the event of a link failure. We study the NP-hard capacity planning problem of economically installing spare capacity on a network to permit link restoration of steady-state traffic. We present a planning model that incorporates multiple facility types, and develop optimization-based heuristic solution methods based on solving a linear programming relaxation and minimum cost network flow subproblems. We establish bounds on the performance of the algorithms, and discuss problem instances that nearly achieve these worst-case bounds. In tests on three real-world problems and numerous randomly-generated problems containing up to 50 nodes and 150 edges, the heuristics provide good solutions (often within 0.5% of optimality) to problems with single facility type, in equivalent or less time than methods from the literature. For multi-facility problems, the gap between our heuristic solution values and the linear programming bounds are larger. However, for small graphs, we show that the optimal linear programming value does not provide a tight bound on the optimal integer value, and our heuristic solutions are closer to optimality than implied by the gaps.     

Optimal selection of a portfolio of options under Value-at-Risk constraints: a scenario approach

This paper introduces a multiperiod model for the optimal selection of a financial portfolio of options linked to a single index. The objective of the model is to maximize the expected return of the portfolio under constraints limiting its Value-at-Risk. We rely on scenarios to represent future security prices. The model contains several interesting features, like the consideration of transaction costs, bid-ask spreads, arbitrage-free option pricing, and the possibility to rebalance the portfolio with options introduced at the start of each period. The resulting mixed integer programming model is applied to realistic test instances involving options on the S&P500 index. In spite of the large size and of the numerical difficulty of this model, near-optimal solutions can be computed by a standard branch-and-cut solver or by a specialized heuristic. The structure and the financial features of the selected portfolios are also investigated.     

Anticipative portfolio optimization under constraints and a higher interest rate for borrowing

We study a stochastic control problem to maximize expected utility from terminal and/or consumption. The novel feature of our work is that the portfolio is allowed to anticipate the future with constraints and a higher interest rate for borrowing. The investor possesses information about the terminal values of the components of the Brownian motion, possibly distorted by ‘noise’. We use the technique from the so-called enlargement of filtrations, to model our problem. General existence results are established for optimal portfolio and consumption strategies. Equivalent conditions for optimality are obtained, and explicit solutions leading to feedback formulae are derived for special utility functions and for deterministic coefficients.     

HARA frontiers of optimal portfolios in stochastic markets

In this paper, we consider the optimal portfolio selection problem in continuous-time settings where the investor maximizes the expected utility of the terminal wealth in a stochastic market. The utility function has the structure of the HARA family and the market states change according to a Markov process. The states of the market describe the prevailing economic, financial, social and other conditions that affect the deterministic and probabilistic parameters of the model. This includes the distributions of the random asset returns as well as the utility function. We analyzed Black–Scholes type continuous-time models where the market parameters are driven by Markov processes. The Markov process that affects the state of the market is independent of the underlying Brownian motion that drives the stock prices. The problem of maximizing the expected utility of the terminal wealth is investigated and solved by stochastic optimal control methods for exponential, logarithmic and power utility functions. We found explicit solutions for optimal policy and the associated value functions. We also constructed the optimal wealth process explicitly and discussed some of its properties. In particular, it is shown that the optimal policy provides linear frontiers.