A Dantzig-Wolfe Decomposition Based Heuristic Scheme for Bi-level Dynamic Network Design Problem

We present a heuristic to solve the NP-hard bi-level network design problem (NDP). The heuristic is developed based on the Dantzig-Wolfe decomposition principle such that it iteratively solves a master problem and a pricing problem. The master problem is the budget allocation linear program solved by CPLEX to determine the budget allocation and construct a modified cell transmission network for the pricing problem. The pricing problem is the user-optimal dynamic traffic assignment (UODTA) solved by an existing combinatorial algorithm. To facilitate the decomposition principle, we propose a backward connectivity algorithm and complementary slackness procedures to efficiently approximate the required dual variables from the UODTA solution. The dual variables are then employed to augment a new column in the master program in each iteration. The iterative process repeats until a stopping criterion is met. Numerical experiments are conducted on two test networks. Encouraging results demonstrate the applicability of the heuristic scheme on solving large-scale NDP. Though a single destination problem is considered in this paper, the proposed scheme can be extended to solve multi-destination problems as well.     

A Branch and Bound Algorithm for An Uncapacitated Facility Location Problem with a Side Constraint

In this paper, a branch and bound algorithm for solving an uncapacitated facility location problem (UFLP) with an aggregate capacity constraint is presented. The problem arises as a subproblem when Lagrangean relaxation of the capacity constraints is used to solve capacitated facility location problems. The algorithm is an extension of a procedure used by Christofides and Beasley (A tree search algorithm for the p-median problem. European Journal of Operational Research , Vol. 10, 1982, pp. 196–204) to solve p -median problems and is based on Lagrangean relaxation in combination with subgradient optimization for lower bounding, simple Lagrangean heuristics to produce feasible solutions, and penalties to reduce the problem size. For node selection, a jump-backtracking rule is proposed, and alternative rules for choosing the branching variable are discussed. Computational experience is reported.     

基于遗传分枝定界算法的Flow-shop调度问题

Flow shop调度问题属于NP难题,传统的方法很难求出精确最优解,提出了一种遗传分枝定界算法,即在遗传算法中引入分枝定界算法保持对优化解有贡献的工件部分顺序,求解3机Flow shop调度问题,该算法与常用的遗传局部算法和遗传动态规划算法类似,用随机方法测试例子,与目前著名的Taillard的禁忌搜索算法和Reeves的遗传算法两种改进算法进行比较,大量的数据实验证实了遗传分枝定界算法的有效性。     

一个并行分枝限界算法产生器的设计与实现

分枝限界算法是一种求解组合优化问题的一般性方法,并行化是提高算法性能的有效手段。文章使用［５］中提出的算法模式和结构模式的概念和思想设计并实现了一个并行分枝限界算法的产生器。该产生器通过提供并行分枝限界算法的抽象框架,将它应用于要求解的问题,可以得到问题的并行分枝限界算法。     

基于Visual C++的0-1背包问题的分枝限界算法

0-1背包问题是经典的NP问题。本文对0-1背包问题的分枝限界算法进行了分析,用Visual C++实现该算法。     

一种离散问题的新型鳗鱼算法

通过对鳗鱼生活行为的分析与研究,提出一种离散问题的新型鳗鱼群智能算法。描述鳗鱼洄游中的行为,提取鳗鱼浓度适应、邻近学习、性别突变3个重要行为,并建立模型进行数学描述。通过对鳗鱼3个重要行为的合理组织,引入等级划分制度与标识度的思想,给出应用于组合优化问题的离散型鳗鱼算法,特别是对于离散个体间的邻近学习,采用切割片段法,使种群个体间的信息可以相互传递。通过TSP问题公共测试库TSPLIB中的数据对算法进行测试,结果表明,该算法具有较强的寻优能力。     

A-Optimality Orthogonal Forward Regression Algorithm Using Branch and Bound

In this brief, we propose an orthogonal forward regression (OFR) algorithm based on the principles of the branch and bound (BB) and A-optimality experimental design. At each forward regression step, each candidate from a pool of candidate regressors, referred to as ${cal S}$, is evaluated in turn with three possible decisions: 1) one of these is selected and included into the model; 2) some of these remain in ${cal S}$ for evaluation in the next forward regression step; and 3) the rest are permanently eliminated from ${cal S}$ . Based on the BB principle in combination with an A-optimality composite cost function for model structure determination, a simple adaptive diagnostics test is proposed to determine the decision boundary between 2) and 3). As such the proposed algorithm can significantly reduce the computational cost in the A-optimality OFR algorithm. Numerical examples are used to demonstrate the effectiveness of the proposed algorithm.      

An Alternative Approach for Solving the Environmentally-Oriented Discrete Network Design Problem

This paper addresses the discrete network design problem (DNDP) with emphasis on the environmental benefits. These benefits are traditionally quantified by emission models, which in general account for vehicle speeds, traffic flows and emission coefficients. An alternative approach for approximating the environmental impact of traffic is developed. This approach finds the route that keeps the most balanced speed profile throughout the route, which contributes to fuel consumption reduction. The paper formulates an optimization problem that includes the described approach for the DNDP. The solution of the problem consists of projects that contribute the most to the generation of such “balanced speed routes”. The paper illustrates the problem and the solution for a real-size network with a medium-size set of candidate projects.     

Interval Branch and Bound Algorithm for Finding the First-Zero-Crossing-Point in One-Dimensional Functions

In this paper, new ideas have been incorporated to a basic interval branch-and-bound algorithm which solves the problem of finding zeros in one-dimensional functions. These new ideas are based on the combination of a new rejection criterion, a selection strategy and an easy-to-obtain precondition of the problem at hand. The methodology described here focuses on finding the first zero crossing point, allowing the search of other zero crossing points to be avoided. In addition, a heuristic subdivision criterion has been proposed that, compared to bisection rule, provides improvements in most of the forty problems that have been tested.     

求解批量流水线调度问题的离散差分进化算法

在研究机床加工的过程中,针对最小化E / T指标的批量流水线调度问题,为了提高工效,提出了一种离散差分进化算法.与传统的差分进化算法不同,离散差分进化算法采用基于工件排列的编码方式,并使用基于工件排列编码的变异和交叉操作.方法可以有效解决流水车间调度问题.为了进一步提高算法的优化性能,提出了一种自适应的多邻域局部搜索算法,并将其嵌入到离散差分进化算法中以增强其局部探测能力.仿真试验表明了所得算法在求解质量和求解效率两方面优于传统的研究成果.     

A Network Flow Algorithm for Reconstructing Binary Images from Discrete X-rays

We present a new algorithm for reconstructing binary images from their projections along a small number of directions. Our algorithm performs a sequence of related reconstructions, each using only two projections. The algorithm makes extensive use of network flow algorithms for solving the two-projection subproblems. Our experimental results demonstrate that the algorithm can compute highly accurate reconstructions from a small number of projections, even in the presence of noise. Although the effectiveness of the algorithm is based on certain smoothness assumptions about the image, even tiny, non-smooth details are reconstructed exactly. The class of images for which the algorithm is most effective includes images of convex objects, but images of objects that contain holes or consist of multiple components can also be reconstructed very well. Kees Joost Batenburg received his PhD degree in Mathematics from the University of Leiden, The Netherlands, in 2006. He also holds a M.Sc. degree in Computer Science. From 2002 to 2006 he worked as a PhD student at CWI in Amsterdam and at the University of Leiden. He is currently a postdoctoral researcher at the Vision Lab of the University of Antwerp, Belgium. His research interests include theory and applications of discrete tomography, combinatorial optimization and natural computing (evolutionary algorithms, neural networks).     

求解TSP问题的伪贪婪离散粒子群优化算法

以旅行商问题为例,提出一种基于元胞结构的伪贪婪离散粒子群优化算法.为了体现粒子对环境的感知能力,设计了伪贪婪的粒子位置修改操作算子,为了反映粒子间不同学习能力,体现粒子的个体差异性,设计了3种学习算子来提高算法的局部求精能力,为了更好地保持粒子群的多样性,采用了元胞结构作为粒子群的种群拓扑和邻城结构,这些策略使算法在空...     

多状态网络可靠度下界的矩阵分解算法

为减少计算多状态网络可靠度精确值的复杂性,提出基于分解计算多状态网络不可靠度精确值的思想,在此基础上提出一个求解多状态网络不可靠度动态上界(对应于可靠度动态下界)的算法.算法先通过分解运算去除某些边引起的d-最小割集之间的相关性,将网络不可靠度转化为多个互斥事件的概率之和,再应用MESP界求取这些事件的概率,计算网络不可靠度上界,对应得到可靠度下界,并计算了得到的可靠度下界与精确值间的绝对误差界.通过定义d-最小割集矩阵,利用矩阵分解实现算法,结构清晰、便于编程计算.相关引理的证明及算例分析表明随着分解的深入,算法能够得到满足精度要求的可靠度下界.     

独立任务分配问题的离散粒子群优化算法

以异构环境下独立任务分配问题为例,提出一种离散粒子群优化算法.对粒子的位置、速度等量及其运算规则进行重新定义.为抑制早熟停滞现象,为粒子和粒子群分别定义个体多样性和微观多样性.算法中使用排斥算子来保持粒子群的多样性,使用学习算子来提高算法的局部求精能力,使算法在空间探索和局部求精间取得较好的平衡.与领域中的其它典型算法进行仿真比较,结果表明,离散粒子群优化算法具有良好的性能.     

求解无线网络基站选址问题的一种改进遗传算法

该文提出了一种改进的遗传算法解决无线网络规划中基站选址的问题,实现了用最少的基站数量实现最大覆盖的优化目标。利用孤岛模型的并行算法提高了优化的速度和质量;采用一致交叉算子,提高了算法的搜索能力,有利于算法收敛;提出了一种新的迁移策略,在迁入其他子群最优个体的同时,不破坏种群的多样性,防止了未成熟收敛。实验证明,该文提出的改进算法获得了较好的优化效果。     

Efficient Subwindow Search: A Branch and Bound Framework for Object Localization

Most successful object recognition systems rely on binary classification, deciding only if an object is present or not, but not providing information on the actual object location. To estimate the object's location, one can take a sliding window approach, but this strongly increases the computational cost because the classifier or similarity function has to be evaluated over a large set of candidate subwindows. In this paper, we propose a simple yet powerful branch and bound scheme that allows efficient maximization of a large class of quality functions over all possible subimages. It converges to a globally optimal solution typically in linear or even sublinear time, in contrast to the quadratic scaling of exhaustive or sliding window search. We show how our method is applicable to different object detection and image retrieval scenarios. The achieved speedup allows the use of classifiers for localization that formerly were considered too slow for this task, such as SVMs with a spatial pyramid kernel or nearest-neighbor classifiers based on the chi^2 distance. We demonstrate state-of-the-art localization performance of the resulting systems on the UIUC Cars data set, the PASCAL VOC 2006 data set, and in the PASCAL VOC 2007 competition.     

有限存储分布式社交网络中数据的动态划分和复制

社交网络的庞大数据需求分布式存储,多个用户的数据分散存储在各个存储和计算节点上可以保持并行性和冗余性。如何在有限的分布式存储空间内高性能存储和访问用户数据具有现实意义。在当前的社交网络系统中,用户数据之间的读写操作会导致大量跨存储节点的远程访问。减少节点间的远程访问可以降低网络负载和访问延迟,提高用户体验。提出一种基于用户交互行为的动态划分复制算法,利用用户之间的朋友关系和评论行为描述社交网络的结构,周期性划分复制用户数据,从而提高本地访问率,降低网络负载。通过真实数据集验证,该算法相比随机划分和复制算法能够大大提升本地访问率,降低访问延迟。     

基于混合遗传算法的网络拓扑设计

提出了一种由启发式算法和遗传算法混合使用的混合遗传算法用于通信网络中的骨干网拓扑设计。文中骨干网拓扑设计问题是在满足R边连通和跳数约束的情况下使得网络费用最小。在遗传算法中,交叉和变异操作会产生不可行解,可通过增加链路来使不可行解变为可行解。增加链路后,其费用一般要比父代个体大,并且有多余的链路。该文的混合遗传算法是在遗传算法中加入启发式策略,来消除多余的链路,降低子代的费用,加快算法的收敛速度。仿真结果验证了算法的有效性。     

Lower tolerance-based Branch and Bound algorithms for the ATSP

In this paper, we develop a new tolerance-based Branch and Bound algorithm for solving NP-hard problems. In particular, we consider the asymmetric traveling salesman problem (ATSP), an NP-hard problem with large practical relevance. The main algorithmic contribution is our lower bounding strategy that uses the expected costs of including arcs in the solution to the assignment problem relaxation of the ATSP, the so-called lower tolerance values. The computation of the lower bound requires the calculation of a large set of lower tolerances. We apply and adapt a finding from [23] that makes it possible to compute all lower tolerance values efficiently. Computational results show that our Branch and Bound algorithm exhibits very good performance in comparison with state-of-the-art algorithms, in particular for difficult clustered ATSP instances.