Row-reduced column generation for degenerate master problems

Column generation for solving linear programs with a huge number of variables alternates between solving a master problem and a pricing subproblem to add variables to the master problem as needed. The method is known to often suffer from degeneracy in the master problem. Inspired by recent advances in coping with degeneracy in the primal simplex method, we propose a row-reduced column generation method that may take advantage of degenerate solutions. The idea is to reduce the number of constraints to the number of strictly positive basic variables in the current master problem solution. The advantage of this row-reduction is a smaller working basis, and thus a faster re-optimization of the master problem. This comes at the expense of a more involved pricing subproblem, itself eventually solved by column generation, that needs to generate weighted subsets of variables that are said compatible with the row-reduction, if possible. Such a subset of variables gives rise to a strict improvement in the objective function value if the weighted combination of the reduced costs is negative. We thus state, as a by-product, a necessary and sufficient optimality condition for linear programming.     

Optimal ordering and pricing policy with supplier quantity discounts and price-dependent stochastic demand

We study a joint ordering and pricing problem for a retailer whose supplier provides all-unit quantity discount for the product. Both generalized disjunctive programming model and mixed integer nonlinear programming model are presented to formulate the problem. Some properties of the problem are analysed, based on which a solution algorithm is developed. Two numerical examples are presented to illustrate the problem, which are solved by our solution algorithm. Managerial analysis indicates that supplier quantity discount has much influence on the ordering and pricing policy of the retailer and more profit can be obtained when the supplier provides quantity discount.     

Dynamic pricing for perishable items with costly price adjustments

Dynamic pricing is widely adopted in inventory management for perishable items, and the corresponding price adjustment cost should be taken into account. This work assumes that the price adjustment cost comprises of a fixed component and a variable one, and attempts to search for the optimal dynamic pricing strategy to maximize the firm’s profit. However, considering the fixed price adjustment cost turns this dynamic pricing problem to a non-smooth optimal control problem which cannot be solved directly by Pontryagin’s maximum principle. Hence, we first degenerate the original problem into a standard optimal control problem and calculate the corresponding solution. On the basis of this solution, we further propose a suboptimal pricing strategy which simultaneously combines static pricing and dynamic pricing strategies. The upper bound of profit gap between the suboptimal solution and the optimal one is obtained. Numerical simulation indicates that the suboptimal pricing strategy enjoys an efficient performance.     

Product line selection and pricing analysis: Impact of genetic relaxations

A model for the product line selection and pricing problem (PLSP) is presented andthree solution procedures based on a genetic algorithm are developed to analyze the results based on consumer preference patterns. Since the PLSP model is nonlinear and integer, two of the solution procedures use genetic encoding to “relax” the NP hard model. The relaxations result in linear integer and shortest path models for the fitness evaluation which are solved using branch and bound and labeling algorithms, respectively. Performance of the quality of solutions generated by the procedures is evaluated for various problem sizes and customer preference structures. The results show that the genetic relaxations provide efficient and effective solution methodologies for the problem, when compared to the pure artificial intelligence technique of genetic search. The impact of the preference structure on the product line and the managerial implications of the solution characteristics generated by the genetic relaxations are also discussed. The models can be used to explicitly consider tradeoffs between marketing and operations concerns in designing a product line.     

基于跳扩散模型欧式期权定价的条件二叉树方法

对股票价格的跳扩散模型进行了分析,在CRR二叉树期权定价模型的基础上考虑标的股票价格发生跳跃的情况,得出基于跳扩散过程的股票期权的条件二叉树定价模型,并且证明在极限情况下,该条件二叉树模型的期权定价公式趋于Merton的解析定价公式,数值试验证实该条件二叉树模型的有效性。     

Infinite-Dimensional Black-Scholes Equation with Hereditary Structure

This paper considers the option pricing problem for contingent claims of the European type in a (B,S)-market in which the stock price and the asset in the riskless bank account both have hereditary structures. The Black-Scholes equation for the classical option pricing problem is generalized to an infinite-dimensional equation to include the effects of time delay in the evolution of the financial market as well as a very general payoff function. A computational algorithm for the solution is also obtained via a double sequence of polynomials of a certain bounded linear functional on a Banach space and the time variable.     

基于腐损程度的季节性产品动态定价与订单量的集成优化

为了对易腐季节性产品的销售价格和订单量进行最优决策,考虑产品在不同腐损程度的情形下,需求与价格和时间同时相关的一类季节性产品的动态定价和订单量的集成优化问题.建立该类产品的价格制订次数、每次制订的价格和订单量的集成优化模型,并对模型进行求解,最后结合数例验证模型的实用性和可操作性,并分析产品腐损程度对价格制订次数、价格大小、订单量和利润的影响.结果表明,随着产品腐损程度的提高,零售商在销售季节内的产品价格最优制订次数保持不变;零售商在销售季节内所制订的最优价格逐渐微降;产品的最优订单量和所产生的最优利润逐渐微升.     

�����滥������

本文讨论了信用衍生产品之一的总收益互换的定价问题. 其中涉及到利率风险和违约风险, 本文利用HJM利率模型来刻画利率风险, 并利用强度模型和混合模型对违约风险进行建模. 分别考虑了违约时间与利率无关时总收益互换合约的定价问题, 以及违约时间与利率相关时总收益互换合约的定价问题, 给出了相应的定价模型, 并用蒙特卡罗模拟方法得到定价问题的数值解.     

Multi-phase dynamic constraint aggregation for set partitioning type problems

Dynamic constraint aggregation is an iterative method that was recently introduced to speed up the linear relaxation solution process of set partitioning type problems. This speed up is mostly due to the use, at each iteration, of an aggregated problem defined by aggregating disjoint subsets of constraints from the set partitioning model. This aggregation is updated when needed to ensure the exactness of the overall approach. In this paper, we propose a new version of this method, called the multi-phase dynamic constraint aggregation method, which essentially adds to the original method a partial pricing strategy that involves multiple phases. This strategy helps keeping the size of the aggregated problem as small as possible, yielding a faster average computation time per iteration and fewer iterations. We also establish theoretical results that provide some insights explaining the success of the proposed method. Tests on the linear relaxation of simultaneous bus and driver scheduling problems involving up to 2,000 set partitioning constraints show that the partial pricing strategy speeds up the original method by an average factor of 4.5.     

A dual approach to multiple exercise option problems under constraints

This paper considers the pricing of multiple exercise options in discrete time. This type of option can be exercised up to a finite number of times over the lifetime of the contract. We allow multiple exercise of the option at each time point up to a constraint, a feature relevant for pricing swing options in energy markets. It is shown that, in the case where an option can be exercised an equal number of times at each time point, the problem can be reduced to the case of a single exercise possibility at each time. In the general case there is not a solution of this type. We develop a dual representation for the problem and give an algorithm for calculating both lower and upper bounds for the prices of such multiple exercise options.     

拟蒙特卡罗法在亚洲期权定价中的应用

亚洲期权是场外交易中几种最受欢迎的新型期权之一,但它的价格却没有解析表达式,到目前为止,亚洲期权的定价仍是个公开问题.本文采用拟蒙特卡罗法中的Halton序列来估计它的价格,数值结果表明当观察点的个数N13时,它比蒙特卡罗法要好.本文还利用MATLAB程序生成了随机Halton序列,并将它与控制变量法结合起来估计亚洲期权的价格,估计值标准差的比较表明它在大多情况下比相应的蒙特卡罗法的估计效果要好.     

An approximate moving boundary method for American option pricing

We present a method to solve the free-boundary problem that arises in the pricing of classical American options. Such free-boundary problems arise when one attempts to solve optimal-stopping problems set in continuous time. American option pricing is one of the most popular optimal-stopping problems considered in literature. The method presented in this paper primarily shows how one can leverage on a one factor approximation and the moving boundary approach to construct a solution mechanism. The result is an algorithm that has superior runtimes-accuracy balance to other computational methods that are available to solve the free-boundary problems. Exhaustive comparisons to other pricing methods are provided. We also discuss a variant of the proposed algorithm that allows for the computation of only one option price rather than the entire price function, when the requirement is such.     

Periodic pricing and replenishment policy for continuously decaying inventory with multivariate demand

This paper deals with the joint decisions on pricing and replenishment schedule for a periodic review inventory system in which a replenishment order may be placed at the beginning of some or all of the periods. We consider a single product which is subject to continuous decay and a demand which is a function of price and time, without backlogging over a finite planning horizon. The proposed scheme may adjust periodically the selling price upward or downward that makes the pricing policy more responsive to structure changes in supply or demand. The problem is formulated as a dynamic programming model and solved by numerical search techniques. An extensive numerical study is conducted to attend qualitative insights into the structures of the proposed policy and its sensitivity with respect to major parameters. The numerical result shows that the solution generated by the periodic policy outperforms that by the fixed pricing policy in maximizing discount profit.     

Branching in branch-and-price: a generic scheme

Developing a branching scheme that is compatible with the column generation procedure can be challenging. Application specific and generic schemes have been proposed in the literature, but they have their drawbacks. One generic scheme is to implement standard branching in the space of the compact formulation to which the Dantzig-Wolfe reformulation was applied. However, in the presence of multiple identical subsystems, the mapping to the original variable space typically induces symmetries. An alternative, in an application specific context, can be to expand the compact formulation to offer a wider choice of branching variables. Other existing generic schemes for use in branch-and-price imply modifications to the pricing problem. This is a concern because the pricing oracle on which the method relies might become obsolete beyond the root node. This paper presents a generic branching scheme in which the pricing oracle of the root node remains of use after branching (assuming that the pricing oracle can handle bounds on the subproblem variables). The scheme does not require the use of an extended formulation of the original problem. It proceeds by recursively partitioning the subproblem solution set. Branching constraints are enforced in the pricing problem instead of being dualized via Lagrangian relaxation, and the pricing problem is solved by a limited number of calls to the pricing oracle. This generic scheme builds on previously proposed approaches and unifies them. We illustrate its use on the cutting stock and bin packing problems. This is the first branch-and-price algorithm capable of solving such problems to integrality without modifying the subproblem or expanding its variable space.     

A General Pricing Scheme for the Simplex Method

In the simplex method for linear programming the algorithmic step of checking the reduced costs of nonbasic variables is called the “pricing” step. If these reduced costs are all of the “right sign” the current basis (and solution) is optimal, if not, this procedure selects a candidate vector that looks profitable for inclusion in the basis. While theoretically the choice of any profitable vector will lead to a finite termination (provided degeneracy is handled properly) but the number of iterations until termination depends very heavily on the actual choice (which is defined by the selection rule applied). Pricing has long been an area of heuristics to help make better selection. As a result, many different and sophisticated pricing strategies have been developed, implemented and tested. So far none of them is known to be dominating all others in all cases. Therefore, advanced simplex solvers need to be equipped with many strategies so that the most suitable one can be activated for each individual problem instance. In this paper we present a general pricing scheme. It creates a large flexibility in pricing. It is controlled by three parameters. With different settings of the parameters many of the known strategies can be reproduced as special cases. At the same time, the framework makes it possible to define new strategies or variants of them. The scheme is equally applicable to general and network simplex algorithms.     

FINITE DIFFERENCE APPROXIMATION FOR PRICING THE AMERICAN LOOKBACK OPTION

In this paper we are concerned with the pricing of lookback options with American type constrains. Based on the differential linear complementary formula associated with the pricing problem, an implicit difference scheme is constructed and analyzed. We show that there exists a unique difference solution which is unconditionally stable. Using the notion of viscosity solutions, we also prove that the finite difference solution converges uniformly to the viscosity solution of the continuous problem. Furthermore, by means of the variational inequality analysis method, the O（△t ＋ △x^2）-order error estimate is derived in the discrete L2-norm provided that the continuous problem is sufficiently regular. In addition, a numerical example is provided to illustrate the theoretical results.     

The impact of dynamic pricing on the economic order decision

This paper analyzes the impact of dynamic pricing on the single product economic order decision of a monopolist retailer. Items are procured from an external supplier according to the economic order quantity (EOQ) model and are sold to customers on a single market without competition following the simple monopolist pricing problem. Coordinated decision making of optimal pricing and ordering is influenced by operating costs – including ordering and inventory holding costs – and the demand rate obtained from a price response function. The retailer is allowed to vary the selling price, either in a fixed number of discrete points in time or continuously. While constant and continuous pricing have received much attention in the literature, problems with a limited number of price changes are rather rare. This paper illustrates the benefit of dynamically changing prices to achieve operational efficiency in the EOQ model, that is to trigger high demand rates when inventories are high. We provide structural properties of the optimal time instants when the price should be changed. Taking into account costs for changes in price, it provides numerical guidance on number, timing, and size of price changes during an order cycle. Numerical examples show that the benefits of dynamic pricing in an EOQ framework can be achieved with only a few price changes and that products being unprofitable under static pricing may become profitable under dynamic pricing.     

Optimal revenue management in two class pre-emptive delay dependent Markovian queues

In this paper, we present a comparative study on the total revenue generated with pre-emptive and non pre-emptive priority scheduler for a fairly generic problem of pricing the server’s surplus capacity in a single server Markovian queue. The specific problem is to optimally price the server’s surplus capacity by introducing a new class of customers (secondary class) without affecting the pre-specified service level of its current customers (primary class) when pre-emption is allowed. Pre-emptive scheduling is used in various applications. First, a finite step algorithm is proposed to obtain global optimal operating and pricing parameters for this problem. These optimal operating and pricing parameters constitute a unique Nash equilibrium in a certain two player non cooperative game. We then describe the range of service level where pre-emptive scheduling gives feasible solution and generates some revenue while non pre-emptive scheduling has infeasible solution. Further, some complementary conditions are identified to compare revenue analytically for certain range of service level where strict priority to secondary class is optimal. Our computational examples show that the complementary conditions adjust in such a way that pre-emptive scheduling always generates more revenue. Theoretical analysis is found to be intractable for the range of service level when pure dynamic policy is optimal. Hence, extensive numerical examples are presented to describe different instances. It is noted in numerical examples that pre-emptive scheduling generates at least as much revenue as non pre-emptive scheduling. A certain range of service level is identified where improvement in revenue is quite significant.     

Dynamic pricing of inventory/capacity with infrequent price changes

We consider a problem of dynamically pricing a single product sold by a monopolist over a short time period. If demand characteristics change throughout the period, it becomes attractive for the company to adjust price continuously to respond to such changes (i.e., price-discriminate intertemporally). However, in practice there is typically a limit on the number of times the price can be adjusted due to the high costs associated with frequent price changes. If that is the case, instead of a continuous pricing rule the company might want to establish a piece-wise constant pricing policy in order to limit the number of price adjustments. Such a pricing policy, which involves optimal choice of prices and timing of price changes, is the focus of this paper.We analyze the pricing problem with a limited number of price changes in a dynamic, deterministic environment in which demand depends on the current price and time, and there is a capacity/inventory constraint that may be set optimally ahead of the selling season. The arrival rate can evolve in time arbitrarily, allowing us to model situations in which prices decrease, increase, or neither. We consider several plausible scenarios where pricing and/or timing of price changes are endogenized. Various notions of complementarity (single-crossing property, supermodularity and total positivity) are explored to derive structural results: conditions sufficient for the uniqueness of the solution and the monotonicity of prices throughout the sales period. Furthermore, we characterize the impact of the capacity constraint on the optimal prices and the timing of price changes and provide several other comparative statics results. Additional insights are obtained directly from the solutions of various special cases.     

A heuristic method for the minimum toll booth problem

This paper addresses the toll pricing problem in which the objective is to minimize the number of required toll facilities in a traffic network. The problem is shown to be NP-hard. To obtain a solution in a reasonable time, an effective metaheuristic algorithm is developed. The algorithm uses a local search technique in which the neighborhood function employs the dynamic slope scaling procedure to deal with the fixed charge nature of the objective function. Numerical results from 50 randomly generated and three real networks are reported.