Modelling and optimization of reservoirs for long-term regulation with variable head using functional analysis

In this paper, functional analysis and minimum norm formulation are applied to maximize the total benefits from two hydro reservoirs. The hydroelectric power generation is treated as a nonlinear function; water head variation and stochasticity of the river flows are included. The resulting problem has a nonlinear objective function and linear constraints. The proposed method is computationally efficient, compared to previous techniques. Numerical results are presented for widely different water conditions for an actual system in operation.This work was supported by the National Research Council of Canada, Grant No. A4146. The authors wish to thank B. C. Hydro for providing the reservoir data.     

Long-term optimal operation of series parallel reservoirs for critical period with specified monthly generation and average monthly storage

We present in this paper an efficient approach for solving the problem of planning the long-term (multiyear) operation of a multireservoir hydroelectric power system for the critical period with a monthly variable load. This load is equal to a certain percentage of the total generation at the end of the year, subject to satisfying a number of constraints on the hydrosystem, using the minimum norm formulation.The proposed method is efficient in computing time and in calculating the total expected benefits from the system during the critical period. Numerical results are reported for a real system in operation consisting of two rivers. Each river has two series reservoirs.This work was supported by the Natural Science and Engineering Research Council of Canada, Grant No. A4146.     

Modelling and optimization of parallel reservoirs having nonlinear storage curves under critical water conditions for long-term regulation

This paper deals with the problem of parallel reservoirs having nonlinear storage-elevation curves (quadratic functions) for long-term regulation under critical water conditions using the minimum norm formulation. To overcome these nonlinearities, we introduce a set of pseudo-state variables. A set of optimizing equations is obtained. The proposed method is efficient in computing time and in calculating the expected benefits of generation from the system during the critical period. Numerical results are reported for a real system in operation consisting of two rivers; each river has two reservoirs in series.This work was supported by the National Research Council of Canada, Grant No. A4146. The authors would like to acknowledge data obtained from B. C. Hydro.     

Optimization of reservoirs in series on a river with a nonlinear storage curve for long-term regulation

We present in this paper a new approach to finding the monthly optimal operation of a multireservoir power system connected in series on a river. The hydroelectric power generation is a highly nonlinear function of the storage, and the conversion factor assigned to each power plant is also a nonlinear function of the storage. We use for both a quadratic function of the storage; the resulting problem has a highly nonlinear objective function and linear constraints. We propose a transformation such that the system equations are reduced to linear-quadratic form. Lagrange and Kuhn-Tucker multipliers are used to adjoin the equality and inequality constraints to the objective function. Numerical results are presented for a real system in operation consisting of two reservoirs in series on a river for widely different water conditions.This work was supported by the National Research Council of Canada, Grant No. A4146. The authors would like to acknowledge data obtained from B.C. Hydro.     

Optimal long-term operation of a multireservoir power system for critical water conditions

We present in this paper a new method for solving the optimization problem of a variable head multireservoir power system under a critical water condition for long-term regulation. The problem is formulated as a minimum norm problem. The proposed method is efficient in computing time and in calculating the expected benefits from the system during the critical period. Numerical results are presented for a real system in operation consisting of two rivers; each river has two reservoirs connected in a series.This work was supported by the National Research Council of Canada, Grant No. A4146. The authors wish to thank B. C. Hydro for providing the reservoir data.     

关于TLS问题

1.引 言考虑观测线性系统AX=B,（1.1a）其中A∈Cm×n,B∈Cm×d（本文通篇假设m≥n d）,分别是精确但不可观测的A0∈Cm×n,B0∈Cm×d的近似,即精确线性系统是A0X=B0.（1.1b）Golub和Van Loan于1980年提出的总体最小二乘问题（以下简称TLS问题）就是求解线性系统AX=B（1.2）     

带时间窗取送货问题的混合算法

为解决带时间窗的取送货问题,建立了集合划分模型,设计列生成算法与启发式规则相结合的CGA混合算法进行求解。首先,放松约束构建主问题及受限主问题,运用单纯形法与分支定界进行求解;其次,建立时空网络以构建子问题,基于修正的Dijkstra's算法,设计包含算法A、B1、B2的求解算法;最后,通过启发式算法解决节点重复覆盖问题。为验证算法有效性,进一步构建了OPT近似最优解算法;并基于CGA提出三种求解策略C1、C2、C3,做单因素方差分析,采用算例分析算法的性能。实验结果表明,对于客户点数量小于30的小规模算例,CGA与OPT所得结果相近,但CGA求解效率更显著;针对客户点数量为600的大规模算例,CGA至多在20分钟内求得结果,可见本文算法的精度和效率较高。而针对不同类型及规模的客户点的单因素方差分析结果显示,C1、C2、C3在“平均行驶距离成本”、“平均车辆数”、“平均求解时间”三个维度上差异性显著,经营者可根据实际需求进行策略选择。     

Optimizing multi-item multi-period inventory control system with discounted cash flow and inflation: Two calibrated meta-heuristic algorithms

A mixed binary integer mathematical programming model is developed in this paper for ordering items in multi-item multi-period inventory control systems, in which unit and incremental quantity discounts as well as interest and inflation factors are considered. Although the demand rates are assumed deterministic, they may vary in different periods. The situation considered for the problem at hand is similar to a seasonal inventory control model in which orders and sales happen in a given season. To make the model more realistic, three types of constraints including storage space, budget, and order quantity are simultaneously considered. The goal is to find optimal order quantities of the products so that the net present value of total system cost over a finite planning horizon is minimized. Since the model is NP-hard, a genetic algorithm (GA) is presented to solve the proposed mathematical problem. Further, since no benchmarks can be found in the literature to assess the performance of the proposed algorithm, a branch and bound and a simulated annealing (SA) algorithm are employed to solve the problem as well. In addition, to make the algorithms more effective, the Taguchi method is utilized to tune different parameters of GA and SA algorithms. At the end, some numerical examples are generated to analyze and to statistically and graphically compare the performances of the proposed solving algorithms.     

Parameter estimation for partially observable systems subject to random failure

In this paper, we present a parameter estimation procedure for a condition‐based maintenance model under partial observations. Systems can be in a healthy or unhealthy operational state, or in a failure state. System deterioration is driven by a continuous time homogeneous Markov chain and the system state is unobservable, except the failure state. Vector information that is stochastically related to the system state is obtained through condition monitoring at equidistant sampling times. Two types of data histories are available — data histories that end with observable failure, and censored data histories that end when the system has been suspended from operation but has not failed. The state and observation processes are modeled in the hidden Markov framework and the model parameters are estimated using the expectation–maximization algorithm. We show that both the pseudolikelihood function and the parameter updates in each iteration of the expectation–maximization algorithm have explicit formulas. A numerical example is developed using real multivariate spectrometric oil data coming from the failing transmission units of 240‐ton heavy hauler trucks used in the Athabasca oil sands of Alberta, Canada. Copyright © 2012 John Wiley & Sons, Ltd.     

Frequency planning as a set partitioning problem

Some aspects of a new computerized method for automatic generation of frequency plans for radio communication systems are presented. The emphasis is on problem formulation where the frequency planning problem is recast as a set partitioning problem. The objective is minimization of total system interference. A solution algorithm that has been found useful in practical applications is presented. An alternative algorithm is also demonstrated.     

Periodic maintenance and repair rate control in stochastic manufacturing systems

In this paper, we consider a periodic preventive maintenance, repair, and production model of a flexible manufacturing system with failure-prone machines, where the control variables are the repair rate and production rate. We use periodic preventive maintenance to reduce the machine failure rates and improve the productivity of the system. One of the distinct features of the model is that the repair rate is adjustable. Our objective is to choose a control process that minimizes the total cost of inventory/shortage, production, repair, and maintenance. Under suitable conditions, we show that the value function is locally Lipschitz and satisfies an Hamilton-Jacobi-Bellman equation. A sufficient condition for optimal control is obtained. Since analytic solutions are rarely available, we design an algorithm to approximate the optimal control problem. To demonstrate the performance of the numerical method, an example is presented.Research of this author was supported by the Natural Sciences and Engineering Research Council of Canada, Grant OGP0036444.Research of this author was supported in part by the University of Georgia.Research of this author was supported in part by the National Science Foundation, Grant DMS-92-24372.     

Optimal shape of a strongest inverted column

By using Pontryagin's maximum principle we determine the shape of the strongest column positioned in a constant gravity field, simply supported at the lower end and clamped at upper end (with the possibility of axial sliding). It is shown that the cross-sectional area function is determined from the solution of a nonlinear boundary value problem. A variational principle for this boundary value problem is formulated and two first integrals are constructed. These integrals lead to an a priori estimate of the value of one the missing initial condition and to the reduction of the order of the system. The optimal shape of a column is determined by numerical integration.     

带时间窗分车运输同时收发车辆路径问题及其启发式算法

本文结合汽车零部件第三方物流的实际背景,提出了带时间窗的可分车运输同时收发车辆路径问题(简称SVRPSPDTW),并给出了问题的数学模型,同时提出两个求解该问题的启发式算法,最后进行了数值试验.由于没有可以利用的算例,本文在Solomn测试基准库的基础上构建了针对新问题的算例.计算结果表明,所有算例计算时间均不超过1秒,且算法1无论是从车辆的使用数还是从车辆行驶的路径总长度上都明显优于算法2,从而说明算法1是寻找SVRPSPDTW问题初始可行解的较为有效的算法.     

Branch-and-price-and-cut for the multiple traveling repairman problem with distance constraints

In this paper, we extend the multiple traveling repairman problem by considering a limitation on the total distance that a vehicle can travel; the resulting problem is called the multiple traveling repairmen problem with distance constraints (MTRPD). In the MTRPD, a fleet of identical vehicles is dispatched to serve a set of customers. Each vehicle that starts from and ends at the depot is not allowed to travel a distance longer than a predetermined limit and each customer must be visited exactly once. The objective is to minimize the total waiting time of all customers after the vehicles leave the depot. To optimally solve the MTRPD, we propose a new exact branch-and-price-and-cut algorithm, where the column generation pricing subproblem is a resource-constrained elementary shortest-path problem with cumulative costs. An ad hoc label-setting algorithm armed with bidirectional search strategy is developed to solve the pricing subproblem. Computational results show the effectiveness of the proposed method. The optimal solutions to 179 out of 180 test instances are reported in this paper. Our computational results serve as benchmarks for future researchers on the problem.     

A column generation based decomposition algorithm for a parallel machine just-in-time scheduling problem

We propose a column generation based exact decomposition algorithm for the problem of scheduling n jobs with an unrestrictively large common due date on m identical parallel machines to minimize total weighted earliness and tardiness. We first formulate the problem as an integer program, then reformulate it, using Dantzig–Wolfe decomposition, as a set partitioning problem with side constraints. Based on this set partitioning formulation, a branch and bound exact solution algorithm is developed for the problem. In the branch and bound tree, each node is the linear relaxation problem of a set partitioning problem with side constraints. This linear relaxation problem is solved by column generation approach where columns represent partial schedules on single machines and are generated by solving two single machine subproblems. Our computational results show that this decomposition algorithm is capable of solving problems with up to 60 jobs in reasonable cpu time.     

An Integrated Inventory-Routing System for Multi-item Joint Replenishment with Limited Vehicle Capacity

In this paper, we develop a mathematical programming approach for coordinating inventory and transportation decisions in an inbound commodity collection system. In particular, we consider a system that consists of a set of geographically dispersed suppliers that manufacture one or more non-identical items, and a central warehouse that stocks these items. The warehouse faces a constant and deterministic demand for the items from outside retailers. The items are collected by a fleet of vehicles that are dispatched from the central warehouse. The vehicles are capacitated, and must also satisfy a frequency constraint. Adopting a policy in which each vehicle always collects the same set of items, we formulate the inventory-routing problem of minimizing the long-run average inventory and transportation costs as a set partitioning problem. We employ a column generation approach to determine a lower bound on the total costs, and develop a branch-and-price algorithm that finds the optimal assignment of items to vehicles. We also propose greedy constructive heuristics, and develop a very large-scale neighborhood (VLSN) search algorithm to find near-optimal solutions for the problem. Computational tests are performed on a set of randomly generated problem instances.The work of this author was supported by a scholarship of the Faculty of Engineering of Ubonratchathani University, Ubonratchathani, Thailand., The work of this author was supported in part by the National Science Foundation under Grant No. DMI-0085682.     

A new algorithm for solving variational inequalities with application to the traffic assignment problem

The variational inequality problem in Euclidian space is formulated as a nonconvex, nondifferentiable optimization problem. We show that any stationary point is optimal, and we propose a solution algorithm that decreases the nondifferential objective monotonically. Application to the asymmetric traffic assignment problem is considered.Research supported by C.R.S.H. (Canada) grant #410-81-0722-RL and F.C.A.C. (Québec) grant # 83-AS-0026.     

Optimal discrete long-term operation of nuclear-hydrothermal power systems

We discuss in this paper an algorithm for solving the optimal long-term operating problem of a hydrothermal-nuclear power system by application of the minimum norm optimization technique. The algorithm proposed here has the ability to deal with large-scale power systems and with equality and/or inequality constraints on the variables. A discrete model for the xenon and iodine concentrations is used, as well as a discrete model for hydro reservoirs. The optimization is done on a monthly time basis. For simplicity of the problem formulation, the transmission line losses are considered as a part of the load.This work supported by the Natural Sciences and Engineering Research Council of Canada, Grant No. A4146.     

The design of corporate tax structures

We consider the corporate tax structuring problem (TaxSP), a combinatorial optimization problem faced by firms with multinational operations. The problem objective is nonlinear and involves the minimization of the firm's overall tax payments i.e. the maximization of shareholder returns. We give a dynamic programming (DP) formulation of this problem including all existing schemes of tax-relief and income-pooling. We apply state space relaxation and state space descent to the DP recursions and obtain an upper bound to the value of optimal TaxSP solutions. This bound is imbedded in a B&B tree search to provide another exact solution procedure. Computational results from DP and B&B are given for problems up to 22 subsidiaries. For larger size TaxSPs we develop a heuristic referred to as the Bionomic Algorithm (BA). This heuristic is also used to provide an initial lower bound to the B&B algorithm. We test the performance of BA firstly against the exact solutions of TaxSPs solvable by the B&B algorithm and secondly against results obtained for large-size TaxSPs by Simulated Annealing (SA) and Genetic Algorithms (GA). We report results for problems of up to 150 subsidiaries, including some real-world problems for corporations based in the US and the UK. Support for this work was provided by the IST Framework 5 Programme of the European Union, Contract IST2000-29405, Eurosignal ProjectMathematics Subject Classification (2000): 90C39, 91B28     

基于分支割平面的一类无容量限制设施选址问题求解算法

无容量限制设施选址问题是经典的组合优化问题, 具有广泛的应用价值,然而该问题已被证明是NP难问题, 并且传统的分支定界方法求解速度较慢.研究以最大化总收益费用与总投建费用之差为目标的无容量限制设施选址问题,将其转化为节点包装问题,并根据模型的图形特点提出了新的合法不等式族------轴不等式族,经过严格的数学证明后得出轴不等式要强于原有的奇洞不等式. 同时,设计出切割不等式快速搜索算法嵌入到分支割平面方法中. 最后,通过实验验证了轴不等式族的强有效性, 以及分支割平面方法比分支定界方法求解速度快、节点数量少的优点.