Telecommunication Network Capacity Design for Uncertain Demand

The expansion of telecommunication services has increased the number of users sharing network resources. When a given service is highly demanded, some demands may be unmet due to the limited capacity of the network links. Moreover, for such demands, telecommunication operators should pay penalty costs. To avoid rejecting demands, we can install more capacities in the existing network. In this paper we report experiments on the network capacity design for uncertain demand in telecommunication networks with integer link capacities. We use Poisson demands with bandwidths given by normal or log-normal distribution functions. The expectation function is evaluated using a predetermined set of realizations of the random parameter. We model this problem as a two-stage mixed integer program, which is solved using a stochastic subgradient procedure, the Barahona's volume approach and the Benders decomposition.     

模糊网络最大流算法研究

将模糊数差值B~-A~视为模糊方程X~+A~=B~的解,进而探讨了模糊方程的求解问题,并基于目的规划理论,给出了模糊方程的广义解定义.运用目的规划的单纯型方法,得到了模糊方程广义解的计算公式及模糊方程广义解的若干性质.由模糊方程的广义解引申出了模糊数差值的定义.运用该定义将传统的网络最大流算法推广到模糊环境.结果表明,模糊数差值定义,克服了基于扩展原理意义下的模糊运算所产生的各种问题,解决了这些传统理论方法的拓展问题.     

A Dynamic Domain Contraction Algorithm for Nonconvex Piecewise Linear Network Flow Problems*

We consider the Nonconvex Piecewise Linear Network Flow Problem (NPLNFP) which is known to be -hard. Although exact methods such as branch and bound have been developed to solve the NPLNFP, their computational requirements increase exponentially with the size of the problem. Hence, an efficient heuristic approach is in need to solve large scale problems appearing in many practical applications including transportation, production-inventory management, supply chain, facility expansion and location decision, and logistics. In this paper, we present a new approach for solving the general NPLNFP in a continuous formulation by adapting a dynamic domain contraction. A Dynamic Domain Contraction (DDC) algorithm is presented and preliminary computational results on a wide range of test problems are reported. The results show that the proposed algorithm generates solutions within 0 to 0.94 % of optimality in all instances that the exact solutions are available from a branch and bound method.     

分配网络的一个最小费用流算法

分配网络流广泛应用于解决水源、电力的调度及工厂的产品运输、分配、合成等问题.本文提出一个分配网络流的最小费用流算法.     

A Branch-and-Bound Algorithm for Concave Network Flow Problems

In this paper a Branch-and-Bound (BB) algorithm is developed to obtain an optimal solution to the single source uncapacitated minimum cost Network Flow Problem (NFP) with general concave costs. Concave NFPs are NP-Hard, even for the simplest version therefore, there is a scarcity of exact methods to address them in their full generality. The BB algorithm presented here can be used to solve optimally single source uncapacitated minimum cost NFPs with any kind of concave arc costs. The bounding is based on the computation of lower bounds derived from state space relaxations of a dynamic programming formulation. The relaxations, which are the subject of the paper (Fontes et al., 2005b) and also briefly discussed here, involve the use of non-injective mapping functions, which guarantee a reduction on the cardinality of the state space. Branching is performed by either fixing an arc as part of the final solution or by removing it from the final solution. Computational results are reported and compared to available alternative methods for addressing the same type of problems. It could be concluded that our BB algorithm has better performance and the results have also shown evidence that it has a sub-exponential time growth.     

有上下界网络最大流与最小截问题

为了便于建立与有上下界网络最大流与最小截问题有关的决策支持系统,本文给出一个求有上下界网络最大流与最小截的数值算法,证明了算法的理论依据,并举例说明了算法在堵塞流理论中的应用。该算法能判定问题是否有可行解,在问题有可行解的情况下能求得问题的最优解。该算法具有易于编程实现、收敛性好等优点。数值实验表明该算法有较高的计算效率,可用于求解最小饱和流问题。     

Domain Decomposition of Optimal Control Problems for Dynamic Networks of Elastic Strings

We consider optimal control problems related to exact- and approximate controllability of dynamic networks of elastic strings. In this note we concentrate on problems with linear dynamics, no state and no control constraints. The emphasis is on approximating target states and velocities in part of the network using a dynamic domain decomposition method (d³m) for the optimality system on the network. The decomposition is established via a Uzawa-type saddle-point iteration associated with an augmented Lagrangian relaxation of the transmission conditions at multiple joints. We consider various cost functions and prove convergence of the infinite dimensional scheme for an exemplaric choice of the cost. We also give numerical evidence in the case of simple exemplaric networks.     

混沌神经网络优化算法用于求解无等待流水调度问题的最小最大完工时间

利用李小平等提出的相邻工件加工结束时间差矩阵,将求解无等待流水调度问题的最小最大完工时间(Makespan)问题映射为TSP问题,构造对应的能量函数,进而得到随机混沌神经网络(SCSA)算法.实验结果证明该混沌神经网络优化算法优于RAJ算法和GANRAJ算法.     

动态供应链网络均衡模型构建与分析

基于单一商品流,考虑了时间变量和库存问题,建立了三层动态供应链网络结构模型.对制造商、零售商和需求市场的多期独立决策行为及其相互作用进行了分析,应用变分不等式构建了各层均衡模型和整个供应链网络均衡模型.最后与相关文献的模型进行了比较.     

A New Successive Partition Algorithm for Concave Minimization Based on Cone Decomposition and Decomposition Cuts

In this paper we propose a new partition algorithm for concave minimization. The basic structure of the algorithm resembles that of conical algorithms. However, we make extensive use of the cone decomposition concept and derive decomposition cuts instead of concavity cuts to perform the bounding operation. Decomposition cuts were introduced in the context of pure cutting plane algorithms for concave minimization and has been shown to be superior to concavity cuts in numerical experiments. Thus by using decomposition cuts instead of concavity cuts to perform the bounding operation, unpromising parts of the feasible region can be excluded from further explorations at an earlier stage. The proposed successive partition algorithm finds an -global optimal solution in a finite number of iterations.     

基于线性规划的网络流量流向控制策略

互联网的快速发展给运营商带来了网络流量流向控制的需求.控制网络流量流向不但要保证服务质量,而且要尽可能降低运营费用,更要保证各网络链路具备裕量能应对突发变化.在网络流量流向控制中结合成熟的线性规划方法从能全局角度实现网络流量流向的多目标控制,保障网络的健康运行.     

不确定运行时间环境下的车辆调度问题及启发式算法

考虑到物流公司或者配送中心车辆实际运行过程中时间的不确定性,提出了配送服务线路包含时间窗口、车辆容量约束的随机规划模型,以最小化车辆运行成本同时尽可能降低所服务顾客的不满意度.同时,又稍作改进给出了平均-风险模型,由于VRP问题是NP难的,给出了一种基于禁忌搜索的启发式算法,并以北京市13个点的为例,给出求解结果.     

Stochastic Output Feedback of Uncertain Time-Delay Systems with Saturating Actuators

This paper deals with the class of uncertain continuous-time linear systems with Markovian jumps, time delay, and saturating actuators. Under norm-bounded uncertainties and based on the Lyapunov method, sufficient conditions on stochastic stability and stochastic stabilizability are developed. A design algorithm for a stabilizing observer-based robust output feedback controller is proposed in terms of the solutions of linear matrix inequalities.     

求解网络最大流问题的一个算法

为了便于建立与网络最大流问题有关的决策支持系统，本给出一个求解网络最大流问题的数值算法。证明了算法的理论依据，并举例说明了算法的应用。该算法能求出网络最大流和最小截，并具有易于编程实现、收敛性好等优点，大量数值实验表明该算法非常实用有效。     

A Decomposition Methodology Applied to the Multi-Area Optimal Power Flow Problem

This paper describes a decomposition methodology applied to the multi-area optimal power flow problem in the context of an electric energy system. The proposed procedure is simple and efficient, and presents some advantages with respect to other common decomposition techniques such as Lagrangian relaxation and augmented Lagrangian decomposition. The application to the multi-area optimal power flow problem allows the computation of an optimal coordinated but decentralized solution. The proposed method is appropriate for an Independent System Operator in charge of the electric energy system technical operation. Convergence properties of the proposed decomposition algorithm are described and related to the physical coupling between the areas. Theoretical and numerical results show that the proposed decentralized methodology has a lower computational cost than other decomposition techniques, and in large large-scale cases even lower than a centralized approach.     

An Inventory-Location Model: Formulation, Solution Algorithm and Computational Results

We introduce a distribution center (DC) location model that incorporates working inventory and safety stock inventory costs at the distribution centers. In addition, the model incorporates transport costs from the suppliers to the DCs that explicitly reflect economies of scale through the use of a fixed cost term. The model is formulated as a non-linear integer-programming problem. Model properties are outlined. A Lagrangian relaxation solution algorithm is proposed. By exploiting the structure of the problem we can find a low-order polynomial algorithm for the non-linear integer programming problem that must be solved in solving the Lagrangian relaxation subproblems. A number of heuristics are outlined for finding good feasible solutions. In addition, we describe two variable forcing rules that prove to be very effective at forcing candidate sites into and out of the solution. The algorithms are tested on problems with 88 and 150 retailers. Computation times are consistently below one minute and compare favorably with those of an earlier proposed set partitioning approach for this model (Shen, 2000; Shen, Coullard and Daskin, 2000). Finally, we discuss the sensitivity of the results to changes in key parameters including the fixed cost of placing orders. Significant reductions in these costs might be expected from e-commerce technologies. The model suggests that as these costs decrease it is optimal to locate additional facilities.     

A Constant-Potential Infeasible-Start Interior-Point Algorithm with Computational Experiments and Applications

We present a constant-potential infeasible-start interior-point (INFCP) algorithm for linear programming (LP) problems with a worst-case iteration complexity analysis as well as some computational results.The performance of the INFCP algorithm is compared to those of practical interior-point algorithms. New features of the algorithm include a heuristic method for computing a good starting point and a procedure for solving the augmented system arising from stochastic programming with simple recourse. We also present an application to large scale planning problems under uncertainty.     

A Primal-Dual Algorithm for Monotropic Programming and its Application to Network Optimization

This paper presents a new primal-dual algorithm for solving a class of monotropic programming problems. This class involves many problems arising in a number of important applications in telecommunications networks, transportation and water distribution. The proposed algorithm is inspired by Kallio and Ruszczyski approach for linear programming [M. Kallio and A. Ruszczyski, WP-94-15, IIASA, 1994]. The problem is replaced by a game using two different augmented Lagrangian functions defined for the primal and the dual problems. It is then possible to develop a block-wise Gauss-Seidel method to reach an equilibrium of the game with alternating steps made in each component of the primal and dual variables. Finally, we show how this algorithm may be applied to some important problems in Network Optimization such as the minimum quadratic cost single flow problems and convex multicommodity flow problems.     

网络最大流的"冲塞式"求法

网络最大流的理论与方法在运输与网络管理中有着重要的应用。受在管道中冲塞物体的原理的启发，本提出了一种新的求解网络最大流的方法，该方法较以往的解法有一些特别的优点。     

An Incremental Algorithm for the Maximum Flow Problem

An incremental algorithm may yield an enormous computational time saving to solve a network flow problem. It updates the solution to an instance of a problem for a unit change in the input. In this paper we have proposed an efficient incremental implementation of maximum flow problem after inserting an edge in the network G. The algorithm has the time complexity of O((n)² m), where n is the number of affected vertices and m is the number of edges in the network. We have also discussed the incremental algorithm for deletion of an edge in the network G.