Discounted dynamic programming with unbounded returns: Application to economic models

In this paper, we study discounted Markov decision processes on an uncountable state space. We allow a utility (reward) function to be unbounded both from above and below. A new feature in our approach is an easily verifiable rate of growth condition introduced for a positive part of the utility function. This assumption, in turn, enables us to prove the convergence of a value iteration algorithm to a solution to the Bellman equation. Moreover, by virtue of the optimality equation we show the existence of an optimal stationary policy.     

Natural gas bilevel cash-out problem: Convergence of a penalty function method

This paper studies a special bi-level programming problem that arises from the dealings of a Natural Gas Shipping Company and the Pipeline Operator, with facilities of the latter used by the former. Because of the business relationships between these two actors, the timing and objectives of their decision-making process are different and sometimes even opposed. In order to model that, bi-level programming was traditionally used in previous works. Later, the problem was expanded and theoretically studied to facilitate its solution; this included extension of the upper level objective function, linear reformulation, heuristic approaches, and branch-and-bound techniques. In this paper, we present a linear programming reformulation of the latest version of the model, which is significantly faster to solve when implemented computationally. More importantly, this new formulation makes it easier to analyze the problem theoretically, allowing us to draw some conclusions about the nature of the solution of the modified problem. Numerical results concerning the running time, convergence, and optimal values, are presented and compared to previous reports, showing a significant improvement in speed without actual sacrifice of the solution’s quality.     

DEA based dimensionality reduction for classification problems satisfying strict non-satiety assumption

This study shows how data envelopment analysis (DEA) can be used to reduce vertical dimensionality of certain data mining databases. The study illustrates basic concepts using a real-world graduate admissions decision task. It is well known that cost sensitive mixed integer programming (MIP) problems are NP-complete. This study shows that heuristic solutions for cost sensitive classification problems can be obtained by solving a simple goal programming problem by that reduces the vertical dimension of the original learning dataset. Using simulated datasets and a misclassification cost performance metric, the performance of proposed goal programming heuristic is compared with the extended DEA-discriminant analysis MIP approach. The holdout sample results of our experiments shows that the proposed heuristic approach outperforms the extended DEA-discriminant analysis MIP approach.     

A mixed integer linear programming model for optimal sovereign debt issuance

Governments borrow funds to finance the excess of cash payments or interest payments over receipts, usually by issuing fixed income debt and index-linked debt. The goal of this work is to propose a stochastic optimization-based approach to determine the composition of the portfolio issued over a series of government auctions for the fixed income debt, to minimize the cost of servicing debt while controlling risk and maintaining market liquidity. We show that this debt issuance problem can be modeled as a mixed integer linear programming problem with a receding horizon. The stochastic model for the interest rates is calibrated using a Kalman filter and the future interest rates are represented using a recombining trinomial lattice for the purpose of scenario-based optimization. The use of a latent factor interest rate model and a recombining lattice provides us with a realistic, yet very tractable scenario generator and allows us to do a multi-stage stochastic optimization involving integer variables on an ordinary desktop in a matter of seconds. This, in turn, facilitates frequent re-calibration of the interest rate model and re-optimization of the issuance throughout the budgetary year allows us to respond to the changes in the interest rate environment. We successfully demonstrate the utility of our approach by out-of-sample back-testing on the UK debt issuance data.     

Stock repurchase with an adaptive reservation price: A study of the greedy policy

We consider the problem of stock repurchase over a finite time horizon. We assume that a firm has a reservation price for the stock, which is the highest price that the firm is willing to pay to repurchase its own stock. We characterize the optimal policy for the trader to maximize the total number of shares that they can buy over a fixed time horizon. In particular, we study a greedy policy, which involves in each period buying a quantity that drives stock price to the reservation price.     

Learning errors of linear programming support vector regression

In this paper, we give several results of learning errors for linear programming support vector regression. The corresponding theorems are proved in the reproducing kernel Hilbert space. With the covering number, the approximation property and the capacity of the reproducing kernel Hilbert space are measured. The obtained result (Theorem 2.1) shows that the learning error can be controlled by the sample error and regularization error. The mentioned sample error is summarized by the errors of learning regression function and regularizing function in the reproducing kernel Hilbert space. After estimating the generalization error of learning regression function (Theorem 2.2), the upper bound (Theorem 2.3) of the regularized learning algorithm associated with linear programming support vector regression is estimated.     

The Transit Route Arc-Node Service Maximization problem

This article presents a new method for determining optimal transit routes. The Transit Route Arc-Node Service Maximization model is a mathematical model that maximizes the service value of a route, rather than minimizing cost. Cost (distance) is considered as a budget constraint on the extent of the route. The mathematical formulation modifies and exploits the structure of linear programming problems designed for the traveling salesman problem. An innovative divide-and-conquer solution procedure is presented that not only makes the transit routing problem tractable, but also provides a range of high-quality alternate routes for consideration, some of which have substantially varying geometries. Variant formulations are provided for several common transit route types. The model is tested through its application to an existing street network in Richardson, TX. Optimal numeric results are obtained for several problem instances, and these results demonstrate that increased route cost is not correlated with increased service provision.     

Survivable network design with demand uncertainty

The objective in designing a communications network is to find the most cost efficient network design that specifies hardware devices to be installed, the type of transmission links to be installed, and the routing strategy to be followed. In this paper algorithmic ideas are presented for improving tractability in solving the survivable network design problem by taking into account uncertainty in the traffic requirements. Strategies for improving separation of metric inequalities are presented and an iterative approach for obtaining solutions, that significantly reduces computing times, is introduced. Computational results are provided based on data collected from an operational network.     

Optimizing departure times in vehicle routes

Most solution methods for the vehicle routing problem with time windows (VRPTW) develop routes from the earliest feasible departure time. In practice, however, temporary traffic congestion make such solutions non-optimal with respect to minimizing the total duty time. Furthermore, the VRPTW does not account for driving hours regulations, which restrict the available travel time for truck drivers. To deal with these problems, we consider the vehicle departure time optimization (VDO) problem as a post-processing of a VRPTW. We propose an ILP formulation that minimizes the total duty time. The results of a case study indicate that duty time reductions of 15% can be achieved. Furthermore, computational experiments on VRPTW benchmarks indicate that ignoring traffic congestion or driving hours regulations leads to practically infeasible solutions. Therefore, new vehicle routing methods should be developed that account for these common restrictions. We propose an integrated approach based on classical insertion heuristics.