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.     

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.     

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

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

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

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

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

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

一种求解最短枝切长度问题的学习算法

枝切法是一种高效的抗噪声相位展开方法,而最短枝切长度能够保证最优的相位展开结果。最短枝切长度问题属于组合优化问题,提出一种求解该问题的学习算法,将最短枝切长度问题的解视为个体,该算法通过个体之间的学习以及个体自身的变异实现进化,作用类似于遗传算法中的交叉算子以及变异算子。通过对多幅含噪声包裹相位图进行实验验证,该算法比传统的求解最短枝切长度问题的算法更快更优。     

基于K-MEANS聚类的分支定界算法在网络异常检测中的应用

网络异常检测技术是入侵检测领域研究的热点之一。在异常检测中,针对其存在的对训练集中关键数据的 选取不准确、选取过程耗时较长、检测的误报率过高等问题,结合经典的K-MEANS算法和分支定界算法,建立起一 种网络异常检测模型,以有效地提高在大量训练集中选取关键数据的准确率,同时降低数据选取的时耗。通过大量基 于著名的KDD Cup 1999数据集的实验,表明此模型能够达到较高的检则准确性,并能有效地控制检测错误报警的发 生。     

面向离散优化问题的量子协同演化算法

为解决现有离散优化算法在有限时间内容易出现过早收敛或难以收敛的问题,提出了面向离散优化问题的量子协同演化算法。该算法通过种群初始化策略构建分布均匀的初始种群,并改进粒子群和单点优化算法成为具有不同搜索能力的协同演化策略,进而利用量子旋转门根据种群个体的进化情况自适应地选择合适的演化策略,最后利用精英保持策略避免种群的退化。在标准离散问题和背包问题的测试环境中,各算法的平均收敛精度和实际收敛情况均表明,已提出的算法能够在有限时间内,收敛到精度较高的解,可用于求解具有时效要求的离散优化问题。     

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

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

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.     

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.      

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.     

交通网络设计问题的人工鱼群算法

人工鱼群算法是一种新的群体智能优化算法,可较好地避免局部极值并取得全局极值,但针对离散优化问题却存在开发平衡及探索能力差等缺点。为此,设计一种自适应变异的人工鱼群算法,在迭代过程中添加变异算子并自动调节视野范围和拥挤度因子。将该算法应用于多等级选择的离散型交通网络二层规划模型设计中,上下层模型分别采用人工鱼群算法及Frank-Wolfe算法进行求解,从而为求解这类模型提供新方法。仿真结果表明,该算法具有较好的稳定性和收敛速度,能够应用于大型城市交通网络设计中。     

Rent-or-Buy Network Design Problem and the Sample-Augment Algorithm: A Survey

The Rent-or-Buy Network Design problem is a fundamental connectivity-related network design problem. The problem captures the "economies of scale" property, which says that the per-unit cost of installing capacity on edges of the network decreases as more capacity is installed. The Sample-Augment algorithm is a simple but powerful randomized approximation algorithm that effectively deals with the Rent-or-Buy and related problems. In this paper we systematically survey the Rent-or-Buy problem and the Sample-Augment algorithm, as well as its two analysis techniques, i.e., the cost-sharing method and the core-detouring scheme.     

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

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

离散灰狼优化算法求解VRPSPDTW问题

本文针对带时间窗约束的同时送取货车辆路径问题,建立了以总配送距离最小化为目标的数学模型.根据模型的特征,在保留灰狼算法(GWO)搜索机制的基础上,提出了离散灰狼优化算法(DGWO)进行求解.采用多种策略构建种群的初始解,并允许出现不可行解,扩大种群的搜索区域;引入带评分策略的邻域搜索策略,调整每种算子的概率,使算法选择优化效果更好的算子;使用移除-插入机制,对优质解区域进行探索,加速种群的收敛.在仿真实验中对标准数据集进行了测试,将实验结果和p-SA算法、DCS算法、VNS-BSTS算法和SA-ALNS算法进行了对比,实验表明DGWO算法能有效地解决带时间窗约束的同时送取货车辆路径问题.     

基于改进粒子群的双层规划求解算法

提出一种采用粒子群优化算法求解双层规划模型的算法。首先对粒子群优化算法作了改进,然后用改进后的算法求解双层规划模型,通过两个粒子群优化算法之间的协同迭代,同步优化双层规划的上下层,最终求得双层规划模型的最优解。此算法将求解一般双层规划问题转化为通过两个粒子群优化算法的交互迭代来求解上下两层规划问题。通过对几种典型函数的测试,验证了此算法的有效性。     

离散萤火虫优化算法求解概率旅行商问题

对随机组合优化问题中的概率旅行商问题(PTSP)的理论和方法进行了研究分析,采用现代进化算法中有代表性发展优势的萤火虫优化算法(FA),提出一种离散萤火虫优化算法(DFA)以求解.其中引入了新的学习机制使其相比原始的萤火虫优化算法,更容易搜索到全局最优解,有更好的收敛性能.实验中用TSPLIB中的经典实例进行测试来验证其可行性.考察了萤火虫数量和进化迭代次数对求解结果性能的影响,并将DFA与GA、PSO和ACO等其他著名的进化计算算法进行性能比较.实验结果证实了DFA无论对固定访问概率,还是访问概率为区间内随机数等不同情况,都具有良好的有效性和高效性,因此对求解随机组合优化系列问题的有效解决具有一定参考和借鉴价值.     

用于特征选择的BF*算法及其与B&B算法的比较

本文将模式识别中的特征选择问题转化为有向图上最佳路径搜索问题,并应用AI中的 Best First (简记BF*)策略搜索最佳路径,提出了特征选择GBFF*和TBFF*算法,证明了 用它们可不穷举而一定找到最佳子集,同目前被认为最好的全局最佳算法--B&B相比, TBFF*搜索的特征子集数目优于B&B.