Technical note: Finite-time regret analysis of Kiefer-Wolfowitz stochastic approximation algorithm and nonparametric multi-product dynamic pricing with unknown demand

We consider the problem of nonparametric multi-product dynamic pricing with unknown demand and show that the problem may be formulated as an online model-free stochastic program, which can be solved by the classical Kiefer-Wolfowitz stochastic approximation (KWSA) algorithm. We prove that the expected cumulative regret of the KWSA algorithm is bounded above by where κ₁, κ₂ are positive constants and T is the number of periods for any T = 1, 2, … . Therefore, the regret of the KWSA algorithm grows in the order of , which achieves the lower bounds known for parametric dynamic pricing problems and shows that the nonparametric problems are not necessarily more difficult to solve than the parametric ones. Numerical experiments further demonstrate the effectiveness and efficiency of our proposed KW pricing policy by comparing with some pricing policies in the literature.     

A multi‐stage stochastic programming approach for network capacity expansion with multiple sources of capacity

In networks, there are often more than one sources of capacity. The capacities can be permanently or temporarily owned by the decision maker. Depending on the nature of sources, we identify the permanent capacity, spot market capacity, and contract capacity. We use a scenario tree to model the uncertainty, and build a multi‐stage stochastic integer program that can incorporate multiple sources and multiple types of capacities in a general network. We propose two solution methodologies for the problem. Firstly, we design an asymptotically convergent approximation algorithm. Secondly, we design a cutting plane algorithm based on Benders decomposition to find tight bounds for the problem. The numerical experiments show superb performance of the proposed algorithms compared with commercial software. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 600–614, 2017     

大规模代谢网络分解的生物信息学研究

随着大规模分子相互作用数据的不断涌现,生物学网络方面的研究正日益得到重视.代谢网络处于生物体的功能执行阶段,其结构组成方式不仅反映了生物体的功能构成,也直接影响代谢工程中的途径分析和研究.作为代谢网络研究的重要环节,实现网络的合理分解不仅对于基因组范围内分子网络的结构和功能研究具有重要意义,也是代谢工程的途径分析和优化得以顺利进行的前提之一.在回顾代谢网络宏观结构和拓扑特征研究成果的基础上,通过对现有分解方法的深入分析,指出缺乏合理且有针对性的模型评估准则是目前网络分解研究中亟待解决的问题之一.今后的研究趋势在于如何整合更多的信息和发展更先进的分析方法,建立更合理的模型,并进一步拓展网络分解的应用范围.     

流域变换的串行与并行策略研究

流域变换是数字形态学中用于图像分割的一种经典方法,其并行化问题成为近年来研究的重点。首先给出了流域变换的数学模型,并归纳列举了几种离散情况下的形式化定义;其次分类总结了近年来流域变换串行算法研究的新进展,从而在此基础上重点讨论了相应的并行化策略。详细分析了设计并行流域算法需要考虑的几个问题;并比较评价了现有并行算法的性能特点,得出了一些结论;最后提出了有待进一步研究的问题。     

The building evacuation problem with shared information

In this article, the Building Evacuation Problem with Shared Information (BEPSI) is formulated as a mixed integer linear program, where the objective is to determine the set of routes along which to send evacuees (supply) from multiple locations throughout a building (sources) to the exits (sinks) such that the total time until all evacuees reach the exits is minimized. The formulation explicitly incorporates the constraints of shared information in providing online instructions to evacuees, ensuring that evacuees departing from an intermediate or source location at a mutual point in time receive common instructions. Arc travel time and capacity, as well as supply at the nodes, are permitted to vary with time and capacity is assumed to be recaptured over time. The BEPSI is shown to be NP‐hard. An exact technique based on Benders decomposition is proposed for its solution. Computational results from numerical experiments on a real‐world network representing a four‐story building are given. Results of experiments employing Benders cuts generated in solving a given problem instance as initial cuts in addressing an updated problem instance are also provided. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Scheduling for parallel dedicated machines with a single server

This paper examines scheduling problems in which the setup phase of each operation needs to be attended by a single server, common for all jobs and different from the processing machines. The objective in each situation is to minimize the makespan. For the processing system consisting of two parallel dedicated machines we prove that the problem of finding an optimal schedule is N P‐hard in the strong sense even if all setup times are equal or if all processing times are equal. For the case of m parallel dedicated machines, a simple greedy algorithm is shown to create a schedule with the makespan that is at most twice the optimum value. For the two machine case, an improved heuristic guarantees a tight worst‐case ratio of 3/2. We also describe several polynomially solvable cases of the later problem. The two‐machine flow shop and the open shop problems with a single server are also shown to be N P‐hard in the strong sense. However, we reduce the two‐machine flow shop no‐wait problem with a single server to the Gilmore—Gomory traveling salesman problem and solve it in polynomial time. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 304–328, 2000     

Scheduling to minimize the total compression and late costs

We consider a single-machine scheduling model in which the job processing times are controllable variables with linear costs. The objective is to minimize the sum of the cost incurred in compressing job processing times and the cost associated with the number of late jobs. The problem is shown to be NP-hard even when the due dates of all jobs are identical. We present a dynamic programming solution algorithm and a fully polynomial approximation scheme for the problem. Several efficient heuristics are proposed for solving the problem. Computational experiments demonstrate that the heuristics are capable of producing near-optimal solutions quickly. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 67–82, 1998     

Short‐term capacity allocation problem with tool and setup constraints

We consider a short‐term capacity allocation problem with tool and setup constraints that arises in the context of operational planning in a semiconductor wafer fabrication facility. The problem is that of allocating the available capacity of parallel nonidentical machines to available work‐in‐process (WIP) inventory of operations. Each machine can process a subset of the operations and a tool setup is required on a machine to change processing from one operation to another. Both the number of tools available for an operation and the number of setups that can be performed on a machine during a specified time horizon are limited. We formulate this problem as a degree‐constrained network flow problem on a bipartite graph, show that the problem is NP‐hard, and propose constant factor approximation algorithms. We also develop constructive heuristics and a greedy randomized adaptive search procedure for the problem. Our computational experiments demonstrate that our solution procedures solve the problem efficiently, rendering the use of our algorithms in real environment feasible. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

Approximation of multiclass queueing networks with highly variable arrivals under deterministic routing

In this paper, we present the heavy‐traffic bottleneck phenomenon under multiclass deterministic routing and discuss how it can be addressed by decomposition approximation. Examples show that Bitran and Tirupati's method and Whitt's enhancements for deterministic routing may not properly account for this phenomenon. We propose refinements to these methods based on Whitt's variability functions. Results of numerical experiments on simple networks and semiconductor manufacturing process show significant improvement in the approximation of expected waiting time at bottleneck stations. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.