Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints

When vehicle routing problems with additional constraints, such as capacity or time windows, are solved via column generation and branch-and-price, it is common that the pricing subproblem requires the computation of a minimum cost constrained path on a graph with costs on the arcs and prizes on the vertices. A common solution technique for this problem is dynamic programming. In this paper we illustrate how the basic dynamic programming algorithm can be improved by bounded bi-directional search and we experimentally evaluate the effectiveness of the enhancement proposed. We consider as benchmark problems the elementary shortest path problems arising as pricing subproblems in branch-and-price algorithms for the capacitated vehicle routing problem, the vehicle routing problem with distribution and collection and the capacitated vehicle routing problem with time windows.     

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.     

Network flow problems with pricing decisions

This paper considers a class of network flow problems in which the demand levels of the nodes are determined through pricing decisions representing the revenue received per unit demand at the nodes. We must simultaneously determine the pricing decisions and the network flow decisions in order to maximize profits, i.e., the revenues received from the pricing decisions minus the cost of the network flow decisions. Specializations of this class of problems have numerous applications in supply chain management. We show that the class of problems with a single pricing decision throughout the network can be solved in polynomial time under both continuous pricing restrictions and integer pricing restrictions. For the class of problems with customer-specific pricing decisions, we provide conditions under which the problem can be solved in polynomial-time for continuous pricing restrictions and prove that the problem is NP-hard for integer pricing restrictions.     

Branch-and-price algorithm for a combined problem of virtual path establishment and traffic packet routing in a layered communication network

This paper considers a combined problem of establishing virtual paths (VPs) and routing traffic (packet) demands through the virtual paths in a layered communication network where each physical link is subject to its capacity constraints. The problem is modeled as a path-based formulation for which a branch-and-price solution algorithm is derived. The solution algorithm is composed of an efficient pricing algorithm, and also a branching rule based on a variable dichotomy, which does not destroy the structure of the associated pricing problems. Computational experiments are performed to test the efficiency of the algorithm, which show that the algorithm works quite well in finding optimal solutions (for the test instances) within reasonable time. Its immediate application may be made to a centralized network management on mid-term global reconfiguration and long-term VP planning.     

MC方差减小技术在算术平均亚式外汇期权定价中的应用

建立了利率和汇率波动率均为随机情形下算术平均亚式外汇期权的定价模型.由于其定价问题求解十分困难,运用蒙特卡罗(Monte Carlo)方法并结合控制变量方差减小技术进行模拟,有效地减小了模拟方差,得到了期权定价问题的数值结果.     

Pricing problems with a continuum of customers as stochastic Stackelberg games

The pricing problem where a company sells a certain kind of product to a continuum of customers is considered. It is formulated as a stochastic Stackelberg game with nonnested information structure. The inducible region concept, recently developed for deterministic Stackelberg games, is extended to treat the stochastic pricing problem. Necessary and sufficient conditions for a pricing scheme to be optimal are derived, and the pricing problem is solved by first delineating its inducible region, and then solving a constrained optimal control problem.The research work reported here as supported in part by the National Science Foundation under Grant ECS-81-05984, Grant ECS-82-10673, and by the Air Force Office of Scientific Research under AFOSR Grant 80-0098.     

Partial difference equation method for lattice path problems

Many problems concerning lattice paths, especially on the square lattice have been exactly solved. For a single path, many methods exist that allow exact calculation regardless of whether the path inhabits a strip, a semi-infinite space or infinite space, or perhaps interacts with the walls. It has been shown that a transfer matrix method using the Bethe Ansatz allows for the calculation of the partition function for many non-intersecting paths interacting with a wall. This problem can also be considered using the Gessel-Viennot methodology. In a concurrent development, two non-intersecting paths interacting with a wall have been examined in semi-infinite space using a set of partial difference equations.Here, we review thispartial difference equation method for the case of one path in a half plane. We then demonstrate that the answer for arbitrary numbers of non-intersecting paths interacting with a wall can be obtained using this method. One reason for doing this is its pedagogical value in showing its ease of use compared to the transfer matrix method. The solution is expressed in a new form as a constant term formula, which is readily evaluated. More importantly, it is the natural method that generalizes easily to many intersecting paths where there is inter-path interactions (e.g., osculating lattice paths). We discuss the relationship of the partial difference equation method to the transfer matrix method and their solution via a Bethe Ansatz.     

Optimal monopoly pricing with congestion and random utility via partial mass transport

We consider a bilevel optimization framework corresponding to a monopoly spatial pricing problem: the price for a set of given facilities maximizes the profit (upper level problem) taking into account that the demand is determined by consumers' cost minimization (lower level problem). In our model, both transportation costs and congestion costs are considered, and the lower level problem is solved via partial transport mass theory. The partial transport aspect of the problem comes from the fact that each consumer has the possibility to remain out of the market. We also generalize the model and our variational analysis to the stochastic case where utility involves a random term.     

Complexity of solution structures in nonlinear pricing

This paper characterizes and enumerates the possible solution structures in nonlinear pricing problem when the number of buyer types is given. It is shown that the single-crossing property, which is a standard assumption in the literature, reduces the complexity of solving the problem dramatically. The number of possible solution structures is important when the pricing problem is solved under limited information.     

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.     

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.     

Path problems in generalized stars, complete graphs, and brick wall graphs

Path problems such as the maximum edge-disjoint paths problem, the path coloring problem, and the maximum path coloring problem are relevant for resource allocation in communication networks, in particular all-optical networks. In this paper, it is shown that maximum path coloring can be solved optimally in polynomial time for bidirected generalized stars, even in the weighted case. Furthermore, the maximum edge-disjoint paths problem is proved NP-hard for complete graphs (undirected or bidirected), a constant-factor off-line approximation algorithm is presented for the weighted case, and an on-line algorithm with constant competitive ratio is given for the unweighted case. Finally, an open problem concerning the existence of routings that simultaneously minimize the maximum load and the number of colors is solved: an example for a graph and a set of requests is given such that any routing that minimizes the maximum load requires strictly more colors for path coloring than a routing that minimizes the number of colors.     

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.     

Subgradient optimization applied to a discrete nonlinear problem in engineering design

The particular application considered here is the design of relief-header systems, involving compressible fluid flow through tree-networks. The flowrates are specified, and the design problem involves the choice of discrete pipe sizes to minimize total cost while satisfying pressure-drop constraints, which are highly nonlinear. The problem is solved in two stages. Firstly the problem of obtaining the optimal set of continuous pipe sizes is addressed; it turns out that a dual formulation provides and extremely rapid solution. Next, a subgradient optimization procedure is used on the dual in order to solve for the discrete pipe sizes. Networks of up to 78 paths and 205 sections, each involving 50 discrete pipe sizes, have been solved.     

双随机跳扩散模型下亚式期权的定价

研究了双随机跳扩散模型下的亚式期权的定价问题.首先引入一个双随机跳扩散过程.然后通过测度变换消除了亚式期权定价中的路经依赖性问题.最后利用鞅定价方法和Ito引理得到了跳扩散模型下的亚式期权价格必须满足的一个积微分方程.通过数值求解该积微分方程就可以得到了亚式期权的价格,供投资者参考.     

Models and algorithms for three-stage two-dimensional bin packing

We consider the three-stage two-dimensional bin packing problem (2BP) which occurs in real-world applications such as glass, paper, or steel cutting. We present new integer linear programming formulations: models for a restricted version and the original version of the problem are developed. Both only involve polynomial numbers of variables and constraints and effectively avoid symmetries. Those models are solved using CPLEX. Furthermore, a branch-and-price (B&P) algorithm is presented for a set covering formulation of the unrestricted problem, which corresponds to a Dantzig-Wolfe decomposition of the polynomially-sized model. We consider column generation stabilization in the B&P algorithm using dual-optimal inequalities. Fast column generation is performed by applying a hierarchy of four methods: (a) a fast greedy heuristic, (b) an evolutionary algorithm, (c) solving a restricted form of the pricing problem using CPLEX, and finally (d) solving the complete pricing problem using CPLEX. Computational experiments on standard benchmark instances document the benefits of the new approaches: The restricted version of the integer linear programming model can be used to quickly obtain near-optimal solutions. The unrestricted version is computationally more expensive. Column generation provides a strong lower bound for 3-stage 2BP. The combination of all four pricing algorithms and column generation stabilization in the proposed B&P framework yields the best results in terms of the average objective value, the average run-time, and the number of instances solved to proven optimality.     

Coloring all directed paths in a symmetric tree,with an application to optical networks*

Let T be a symmetric directed tree, i.e., an undirected tree with each edge viewed as two opposite arcs. We prove that the minimum number of colors needed to color the set of all directed paths in T, so that two paths of the same color never use the same directed arc of T, is equal to the maximum number of different paths that contain the same arc of T. The proof implies a polynomial time algorithm for actually coloring the paths with the minimum number of colors. When only a subset of the directed paths is to be colored, the problem is known to be NP‐complete; we describe certain instances of the problem which can be efficiently solved. These results are applied to WDM (wavelength‐division multiplexing) routing in all‐optical networks. In particular, we solve the all‐to‐all gossiping problem in optical networks. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 183–196, 2001     

Continuous learning methods in two-buyer pricing problem

This paper presents continuous learning methods in a monopoly pricing problem where the firm has uncertainty about the buyers’ preferences. The firm designs a menu of quality-price bundles and adjusts them using only local information about the buyers’ preferences. The learning methods define different paths, and we compare how much profit the firm makes on these paths, how long it takes to learn the optimal tariff, and how the buyers’ utilities change during the learning period. We also present a way to compute the optimal path in terms of discounted profit with dynamic programming and complete information. Numerical examples show that the optimal path may involve jumps where the buyer types switch from one bundle to another, and this is a property which is difficult to include in the learning methods. The learning methods have, however, the benefit that they can be generalized to pricing problems with many buyers types and qualities.     

Efficient Monte Carlo simulation for integral functionals of Brownian motion

In the paper, we develop a variance reduction technique for Monte Carlo simulations of integral functionals of a Brownian motion. The procedure is based on a new method of sampling the process, which combines the Brownian bridge construction with conditioning on integrals along paths of the process. The key element in our method is the identification of a low-dimensional vector of variables that reduces the dimension of the integration problem more effectively than the Brownian bridge. We illustrate the method by applying it in conjunction with low-discrepancy sequences to the problem of pricing Asian options.     

Pricing and lot-sizing for a deteriorating item in a periodic review inventory system with shortages

We consider a single product that is, subject to continuous decay, a multivariate demand function of price and time, shortages allowed and completely backlogged in a periodic review inventory system in which the selling price is allowed to adjust upward or downward periodically. The objective of this paper is to determine the periodic selling price and lot-size over multiperiod planning horizon so that the total discount profit is maximized. The proposed model can be used as an add-in optimizer like an advanced planning system in an enterprise resource planning system that coordinates distinct functions within a firm. Particular attention is placed on investigating the effect of periodic pricing jointly with shortages on the total discount profit. The problem is formulated as a bivariate optimization model solved by dynamic programming techniques coupled with an iterative search process. An intensive numerical study shows that the periodic pricing is superior to the fixed pricing in profit maximization. It also clarifies that shortages strategy can be an effective cost control mechanism for managing deterioration inventory.