Multicommodity Flow Problem with Variable Arcs Capacities

The problem of maximizing the sum of the flows of all commodities in a network where the capacities of some arcs can be increased by integer numbers within a fixed budget is solved in this paper. Benders' technique is used to decompose the problem. Then Rosen's primal partitioning and non-linear duality theory are used to solve the subproblems generated by the Benders' decomposition. An application of a multicommodity network to the defence problem is mentioned.     

有预算限制的最大多种物资流问题

研究有预算限制的最大多种物资流问题,给出了这个问题的不依赖物资数k的全多项式时间近似算法,其算法复杂性是O~(-ε2m2).同时,利用有预算限制的最大多种物资流问题的研究结果,我们也得到了费用最小的最大多种物资流问题的近似算法和算法复杂性.     

一个局部带优先权的最大多物资网络流问题

给出一个局部带优先权的最大多物资网络流问题(MMFP-LPRI),证明它的解存在,并给出其η-松弛解的定义.通过做辅助网络,并运用程丛电等根据Korte和Vygen于2000年在Young,Garg和K(o|¨)nemann等工作的基础上给出的求最大多种物资网络流问题的ε-近似解的多项式方案设计的一个算法作为子程序进行二分收索建立了一个求所给问题的η-松弛解的拟多项式算法.最后,进行算法分析,证明了所设计的算法的输出结果确实是MMFP-LPRT的一个η-松弛解.     

具有全局性公平满意度的最大多物资网络流问题

我们研究-个具有全局性公平满意度的最大多物资网络流问题(MMFP-GFMR).该项工作不仅丰富了最大多物资网络流问题的内容,而且可用于研究某些实际优化决策问题,例如运输过程中的一些资源分配问题.文中主要内容如下:(A)定义问题MMFP-GFMR并证明其解的存在性.(B)设计-个求解MMFP-GFMR的拟多项式逼近算法.(C)研究算法的复杂性与逼近程度.(D)最后通过模拟计算验证了我们的工作.     

Reflection-Projection Method for Convex Feasibility Problems with an Obtuse Cone

The convex feasibility problem asks to find a point in the intersection of finitely many closed convex sets in Euclidean space. This problem is of fundamental importance in the mathematical and physical sciences, and it can be solved algorithmically by the classical method of cyclic projections.In this paper, the case where one of the constraints is an obtuse cone is considered. Because the nonnegative orthant as well as the set of positive-semidefinite symmetric matrices form obtuse cones, we cover a large and substantial class of feasibility problems. Motivated by numerical experiments, the method of reflection-projection is proposed: it modifies the method of cyclic projections in that it replaces the projection onto the obtuse cone by the corresponding reflection.This new method is not covered by the standard frameworks of projection algorithms because of the reflection. The main result states that the method does converge to a solution whenever the underlying convex feasibility problem is consistent. As prototypical applications, we discuss in detail the implementation of two-set feasibility problems aiming to find a nonnegative [resp. positive semidefinite] solution to linear constraints in ⁿ [resp. in , the space of symmetric n×n matrices] and we report on numerical experiments. The behavior of the method for two inconsistent constraints is analyzed as well.     

Some Remarks on the Convex Feasibility Problem and Best Approximation Problem

In this paper we investigate several solution algorithms for the convex fea- sibility problem(CFP)and the best approximation problem(BAP)respectively.The algorithms analyzed are already known before,but by adequately reformulating the CFP or the BAP we naturally deduce the general projection method for the CFP from well-known steepest decent method for unconstrained optimization and we also give a natural strategy of updating weight parameters.In the linear case we show the connec- tion of the two projection algorithms for the CFP and the BAP respectively.In addition, we establish the convergence of a method for the BAP under milder assumptions in the linear case.We also show by examples a Bauschke's conjecture is only partially correct.     

凸可行问题的一种强收敛算法

无限维Hilbert空间中,解凸可行问题的平行投影算法通常是弱收敛的.本文对一般的平行投影算法进行改进,设计了一种解凸可行问题的具有强收敛性的新算法.该算法主要是在原有算法基础上引入了一个参数序列,在参数序列满足一定的控制条件下保证了算法的强收敛性.为了简单证明算法的强收敛性,我们构建了一个新的积空间,然后把原空间的这种改进平行投影算法转换为积空间中的交替投影算法.这样,改进的平行投影算法的强收敛性就可以通过交替投影算法的收敛性证明得到.     

凸可行问题的块迭代次梯度投影算法

本文,针对由非线性不等式系统构成的凸可行问题,提出了序列块迭代次梯度投影算法和平行块迭代次梯度投影算法.将非线性不等式系统分成若干个子系统,然后将当前迭代点在子系统各个子集上的次梯度投影的凸组合作为当前迭代点在这个子系统上的近似投影.在较弱条件下证明了两种算法的收敛性.     

Regularity and Stability for a Convex Feasibility Problem

Set-Valued and Variational Analysis - Let us consider two sequences of closed convex sets {An} and {Bn} converging with respect to the Attouch-Wets convergence to A and B, respectively. Given a...     

Algorithms for an Integer Multicommodity Network Flow Problem with Node Reliability Considerations

In this paper, we consider the problem of sending a set of multiple commodities from their origin to destination nodes via intermediate hubs. Each hub node is associated with a reliability function, which depends on the total flow that crosses that hub. The probability that each commodity is successfully relayed from its origin to its destination is given by the product of hub reliabilities on the commodity’s path. The problem we consider seeks to find minimum-cost commodity paths such that each commodity reaches its destination with a sufficiently large probability. We first formulate the problem as a nonlinear multicommodity network-flow problem and prove that it is strongly NP-hard. We then present two linearization techniques for this formulation, and propose a pair of lower- and upper-bounding formulations, which can then be used within an exact cutting-plane algorithm to solve the problem. Finally, we analyze the computational effectiveness of our proposed strategies on a set of randomly generated instances.     

Solving the Problem of Rerostering Nurse Schedules with Hard Constraints: New Multicommodity Flow Models

The problem of rerostering nurse schedules arises in hospitals when at least one nurse informs that she will be unable to perform the shifts assigned to her on one or more future work days. As a result, the current roster must be rebuilt in accordance with labour contract rules and institutional requirements. All such restraints are regarded as hard constraints. However, major alterations in the previously assigned nurse schedules must be avoided. This paper is based on a case study of a public hospital in Portugal. It presents two new integer multicommodity flow formulations for the rerostering problem, besides a computational experiment performed using real data. The first model is based on a directed multilevel acyclic network. The aggregation of nodes in this network led to the second model. The results obtained show that the second integer multicommodity flow formulation outperforms the first, both in terms of solution quality, as well as in computational time.     

Parallel Algorithms for Solving the Convex Minimum Cost Flow Problem

In this paper we deal with the solution of the separable convex cost network flow problem. In particular, we propose a parallel asynchronous version of the -relaxation method and we prove theoretically its correctness.We present two implementations of the parallel method for a shared memory multiprocessor system, and we empirically analyze their numerical performance on different test problems. The preliminary numerical results show a good reduction of the execution time of the parallel algorithm with the respect to the sequential counterpart.     

Iterative Methods of Solving Stochastic Convex Feasibility Problems and Applications

The stochastic convex feasibility problem (SCFP) is the problem of finding almost common points of measurable families of closed convex subsets in reflexive and separable Banach spaces. In this paper we prove convergence criteria for two iterative algorithms devised to solve SCFPs. To do that, we first analyze the concepts of Bregman projection and Bregman function with emphasis on the properties of their local moduli of convexity. The areas of applicability of the algorithms we present include optimization problems, linear operator equations, inverse problems, etc., which can be represented as SCFPs and solved as such. Examples showing how these algorithms can be implemented are also given.     

A Polynomial Cutting Surfaces Algorithm for the Convex Feasibility Problem Defined by Self-Concordant Inequalities

Consider a nonempty convex set in ^m which is defined by a finite number of smooth convex inequalities and which admits a self-concordant logarithmic barrier. We study the analytic center based column generation algorithm for the problem of finding a feasible point in this set. At each iteration the algorithm computes an approximate analytic center of the set defined by the inequalities generated in the previous iterations. If this approximate analytic center is a solution, then the algorithm terminates; otherwise either an existing inequality is shifted or a new inequality is added into the system. As the number of iterations increases, the set defined by the generated inequalities shrinks and the algorithm eventually finds a solution of the problem. The algorithm can be thought of as an extension of the classical cutting plane method. The difference is that we use analytic centers and convex cuts instead of arbitrary infeasible points and linear cuts. In contrast to the cutting plane method, the algorithm has a polynomial worst case complexity of O(Nlog 1/) on the total number of cuts to be used, where N is the number of convex inequalities in the original problem and is the maximum common slack of the original inequality system.     

广义多品种最小费用流问题的对偶理论

基于广义多品种最小费用流问题的性质，将问题转化成一对含有内、外层问题的双水平规划，内层规划实际是单品种费用流问题，而外层问题是分离的凸规划，使用相关的凸分析理论，导出了广义多品种最小费用流问题的对偶规划，对偶定理和Kuhn-Tucker条件。     

锥凸集值映射的基本性质

本文首先在R~m的幂集上定义了一种锥序关系并借助这种序关系定义锥凸集值映射,证明了普通单值凸函数的一些基本性质拓广到这种锥凸集值映射时仍成立.     

A Comparison of Heuristics for the Discrete Cost Multicommodity Network Optimization Problem

In this paper, approximate solutions algorithms for discrete cost multicommodity network optimization problems are presented and compared. Firstly, extensions of classical greedy heuristics, based on link-rerouting and flow-rerouting heuristics, are presented in details. Secondly, a new approximate solution algorithm, which basically consists of a heuristic implementation of the exact Benders-type cutting plane generation method, is proposed. All these algorithms are extensively compared on randomly generated graphs up to 50 nodes and 90 links. It clearly appears that this new Benders-type approach is very promising since it produces the best heuristic solutions.     

Iterative Regularization Methods for the Multiple-Sets Split Feasibility Problem in Hilbert Spaces

In this paper, we introduce iterative regularization methods for solving the multiple-sets split feasibility problem, that is to find a point closest to a family of closed convex subsets in one space such that its image under a bounded linear mapping will be closest to another family of closed convex subsets in the image space. We consider the cases, when the families are either finite or infinite. We also give two numerical examples for illustrating our main method.

     

An Integer Multicommodity Flow Model Applied to the Rerostering of Nurse Schedules

The problem of rerostering service schedules is very common in organizations that work shifts around the clock every day of the year with a set number of employees. Whenever one or more workers announce that they will not be able to attend to tasks previously assigned in their schedule, those tasks must be performed at the expense of alterations in the schedules of other workers. These changes should not conflict with the rules laid down by the administration and employment contracts and should affect the previous schedules as little as possible. This is a difficult real problem calling for a computational tool to cope with it easily. In the paper the issue is described in detail in the context of nurse scheduling and formulated as an integer multicommodity flow problem with additional constraints, in a multi-level acyclical network. A heuristic was implemented as a first approach to solving the problem. Subsequently the integer linear programming formulation of the multicommodity flow model and two linear relaxations were tested using CPLEX [2] optimizers. The computational results reported regard real instances from a Lisbon state hospital. Satisfactory rosters were obtained within acceptable computational times in all instances tested, either with the integer optimizer, or with the heuristic. This being so, refinements will be undertaken to embed these methodologies in a decision support system that may assist the head nurse in her daily rerostering activities.     

Grasp Embedded Scatter Search for the Multicommodity Capacitated Network Design Problem

A GRASP embedded Scatter Search is developed for the multicommodity capacitated network design problem. Difficulty for this problem arises from the fact that selection of the optimal network design is an NP-complete combinatorial problem. There exist no polynomial exact algorithms which can solve this problem in a reasonable period of time for realistically sized instances. In such cases, heuristic procedures are commonly used. Two strategies were designed for GRASP: a traditional approach and a memory based technique. As for Scatter Search, 5 different strategies were used to update the reference set. Computational results on a large set of randomly generated instances show the convenience of the proposed procedures.