两阶段特殊结构混合0-1规划的分解算法

本文介绍了一种用于求解具有特殊结构的两阶段混合0-1规划问题的原始-对偶分解算法,并以CPLEX软件作为核心求解器将算法实现.该算法将原问题分解成两个相对简单的子问题,较传统分解算法有更平衡的分解结构和收敛性.实验数据表明,该算法在求解较大规模、稀疏度较大、耦合度较大的复杂两阶段下三角结构混合0-1规划问题时,相比CPLEX提供的分枝剪枝法,在时间效率上有明显提高.算法最后通过固定0-1变量的取值可以得到满足管理精度要求的近似最优解.     

求解图像分割CV模型的BB算法

给出图像分割的一种新算法——BB算法.该方法的优点在于利用迭代过程中当前点和前一点的信息确定搜索步长,从而更有效地搜索最优解.为此,首先通过变分水平集方法将CV模型转化为最优化问题;其次,将BB算法引入该优化问题进行求解;然后,对BB算法进行收敛性分析,为该算法应用在CV模型中提供了理论依据;最后将该方法与已有的最速下降法、共轭梯度法的分割结果进行比较.结果表明,跟其他两种方法相比,BB算法在保证较好分割效果的前提下,提高了算法的速度和性能.     

凸多面体的分割

本文讨论一个凸多面体分割为单纯形的问题.给出一种分割方法,并就此法证明分割的可能性.如将得到最少数目的单纯形的分割方法称为对此多面体的最优分割,还讨论最优分割的一些性质,并给出当最优分割时所得到的单纯形个数的下界.     

不可分离凸背包问题的拉格朗日分解和区域分割方法

本文对线性约束不可分离凸背包问题给出了一种精确算法．该算法是拉格朗日分解和区域分割结合起来的一种分枝定界算法．利用拉格朗日分解方法可以得到每个子问题的一个可行解，一个不可行解，一个下界和一个上界．区域分割可以把一个整数箱子分割成几个互不相交的整数子箱子的并集，每个整数子箱子对应一个子问题．通过区域分割可以逐步减小对偶间隙并最终经过有限步迭代找到原问题的最优解．数值结果表明该算法对不可分离凸背包问题是有效的．     

Toeplitz型矩阵的逆矩阵的快速三角分解算法

针对有关“型”矩阵的三角分解问题 ,提出了一种 Toeplitz型矩阵的逆矩阵的快速三角分解算法 .首先假设给定 n阶非奇异矩阵 A,利用一组线性方程组的解 ,得到 A- 1的一个递推关系式 ,进而利用该关系式得到 A- 1的一种三角分解表达式 ,然后从 Toeplitz型矩阵的特殊结构出发 ,利用上述定理的结论 ,给出了Toeplitz型矩阵的逆矩阵的一种快速三角分解算法 ,算法所需运算量为 O( mn2 ) .最后 ,数值计算表明该算法的可靠性 .     

平面几何模型的EMD分解算法及其应用

经验模态分解(Empirical mode decomposition,简称EMD)算法是一种处理非线性非平稳信号的时频分析方法.该方法可以自适应地将输入信号分解成若干层本征模函数(Intrinsic mode function,简称IMF)和一层余项函数,通过对IMF的特定操作可以实现信号的滤波和去噪等功能.经典的EMD算法主要针对标量形式的函数信号,对于平面几何图形,EMD则按每一个坐标分量分别处理,其效果往往较差.文章提出一种向量形式的平面几何模型EMD算法,该算法将一个平面几何模型分解成若干层偏置向量和一个残差模型,其中偏置向量表示几何体不同尺度的特征,残差模型表示输入模型的大致形状.通过在极值点的定义中施加特征尺度的限制从而保证每次分解只分离出特定尺度的特征.实验表明,该方法可以有效地实现平面几何模型的分解,并应用在去噪、特征编辑以及特征迁移的领域.通过与经典方法以及标量函数信号EMD算法的比较,文章方法的有效性得到验证.     

灾后运输网络中的最短路修复合作博弈

在最短路修复合作博弈中,当灾后运输网络规模较大时,最优成本分摊问题难以直接求解。基于拉格朗日松弛理论,提出了一种最短路修复合作博弈成本分摊算法。该算法将最短路修复合作博弈分解为两个具有特殊结构的子博弈,进而利用两个子博弈的结构特性,可以{高效地}求解出二者的最优成本分摊,将这两个成本分摊相加,可以获得原博弈的一个近乎最优的稳定成本分摊。结果部分既包含运输网络的随机仿真,也包含玉树地震灾区的现实模拟,无论数据来源于仿真还是现实,该算法都能在短时间内为最短路修复合作博弈提供稳定的成本分摊方案。     

一种针对代谢网络多平衡态性质的强连通分解方法

针对反应速率满足一定条件的代谢网络,提出了一种强连通分解方法对网络进行分解,通过研究分解后的子网络来分析整体网络的多平衡态性质.基于代谢网络的拓扑结构,构造了其对应的代谢反应图和相互作用图,引入了紧缩运算的定义,构造了强连通分解算法;给出了该算法的计算复杂度,证明了分解的唯一性以及分解后子网络的强连通性,阐明了子网络与整体网络在多平衡态性质意义下的关系,举例说明了强连通算法和所得主要结果的有效性.     

基于复杂网络理论的防空节点攻击排序研究

应用图论将防空系统抽象成二维网络的拓扑结构图,通过指定点对间最小拦截概率的计算,得到防空拓扑图的子图,并应用复杂网络理论,综合考虑攻击节点的拦截概率及兵力需求量,建立了防空节点攻击价值的计算公式.在此基础上设计了防空节点攻击优化排序算法,给出了最优攻击路径.     

基于亮度均衡化的图像阈值分割技术在黄河冰凌监测中的应用

一种基于亮度均衡化的图像阈值分割算法被提出.该算法将冰凌图像亮度数据均衡化,以类间方差最大为标准,求得最佳阈值,并将冰凌图像转化为二值图像,通过冰凌像素统计,最终确定冰凌密度.该算法被应用于黄河河道冰凌图像密度的计算中,取得较好的效果.     

Optimal assignment of task modules with precedence for distributed processing by graph matching and state-space search

A graph matching approach to optimal assignment of task modules with varying lengths and precedence relationship in a distributed computing system is proposed. Inclusion of module precedence into the optimal solution is made possible by the use of topological module orderings. Two graphs are defined to represent the processor structure and the module precedence relationship, respectively. Assignment of the task modules to the system processors is transformed into a type of graph matching. The search of optimal graph matching corresponding to optimal task assignment is formulated as a state-space search problem which is then solved by theA* algorithm in artificial intelligence. Illustrative examples and experimental results are included to show the effectiveness of the proposed approach.     

Topological sweep of the complete graph

We present a novel, simple and easily implementable algorithm to report all intersections in an embedding of a complete graph. For graphs with N vertices and complexity K measured as the number of segments of the embedding, the running time of the algorithm is Θ(K+NM), where M is the maximum number of edges cut by any vertical line. Our algorithm handles degeneracies, such as vertical edges or multiply intersecting edges, without requiring numerical perturbations to achieve general position.The algorithm is based on the sweep line technique, one of the most fundamental techniques in computational geometry, where an imaginary line passes through a given set of geometric objects, usually from left to right. The algorithm sweeps the graph using a topological line, borrowing the concept of horizon trees from the topological sweep method [H. Edelsbrunner, L.J. Guibas, Topologically sweeping an arrangement, J. Comput. Syst. Sci. 38 (1989) 165-194; J. Comput. Syst. Sci. 42 (1991) 249-251 (corrigendum)].The novelty in our approach is to control the topological line through the use of the moving wall that separates at any time the graph into two regions: the region of known structure, in front of the moving wall, and the region that may contain intersections generated by edges-that have not yet been registered in the sweep process-behind the wall.Our method has applications to graph drawing and for depth-based statistical analysis, for computing the simplicial depth median for a set of N data points [G. Aloupis, S. Langerman, M. Soss, G. Toussaint, Algorithms for bivariate medians and a Fermat-Torricelli problem for lines, Comp. Geom. Theory Appl. 26 (1) (2003) 69-79].We present the algorithm, its analysis, experimental results and extension of the method to general graphs.     

Stochastic design optimization of asynchronous flexible assembly systems

This paper presents the application of the stochastic quasigradient method (SQG) of Ermoliev and Gaivaronski to the performance optimization of asynchronous flexible assembly systems (AFAS). These systems are subject to blocking and starvation effects that make complete analytic performance modeling difficult. A hybrid algorithm is presented in this paper which uses a queueing network model to set the number of pallets in the system and then an SQG algorithm is used to set the buffer spacings to obtain optimal system throughput. Different forms of the SQG algorithm are examined and the specification of optimal buffer sizes and pallet numbers for a variety of assembly systems with ten stations are discussed. The combined Network-SQG method appears to perform well in obtaining a near optimal solution in this discrete optimization example, even though the SQG method was primarily designed for application to differentiable performance functionals. While a number of both theoretical and practical problems remain to be resolved, a heuristic version of the SQG method appears to be a reasonable technique for analyzing optimization problems for certain complex manufacturing systems.     

Optimised crossover genetic algorithm for capacitated vehicle routing problem

This paper presents a genetic algorithm for solving capacitated vehicle routing problem, which is mainly characterised by using vehicles of the same capacity based at a central depot that will be optimally routed to supply customers with known demands. The proposed algorithm uses an optimised crossover operator designed by a complete undirected bipartite graph to find an optimal set of delivery routes satisfying the requirements and giving minimal total cost. We tested our algorithm with benchmark instances and compared it with some other heuristics in the literature. Computational results showed that the proposed algorithm is competitive in terms of the quality of the solutions found.     

An efficient genetic algorithm for the traveling salesman problem with precedence constraints

The traveling salesman problem with precedence constraints (TSPPC) is one of the most difficult combinatorial optimization problems. In this paper, an efficient genetic algorithm (GA) to solve the TSPPC is presented. The key concept of the proposed GA is a topological sort (TS), which is defined as an ordering of vertices in a directed graph. Also, a new crossover operation is developed for the proposed GA. The results of numerical experiments show that the proposed GA produces an optimal solution and shows superior performance compared to the traditional algorithms.     

Managing pharmaceuticals delivery service using a hybrid particle swarm intelligence approach

Medicines or drugs have unique characteristics of short life cycle, small size, light weight, restrictive distribution time and the need of temperature and humidity control (selected items only). Thus, logistics companies often use different types of vehicles with different carrying capacities, and considering fixed and variable costs in service delivery, which make the vehicle assignment and route optimization more complicated. In this study, we formulate the problem to a multi-type vehicle assignment and mixed integer programming route optimization model with fixed fleet size under the constraints of distribution time and carrying capacity. Given non-deterministic polynomial hard and optimal algorithm can only be used to solve small-size problem, a hybrid particle swarm intelligence (PSI) heuristic approach, which adopts the crossover and mutation operators from genetic algorithm and 2-opt local search strategy, is proposed to solve the problem. We also adapt a principle based on cost network and Dijkstra’s algorithm for vehicle scheduling to balance the distribution time limit and the high loading rate. We verify the relative performance of the proposed method against several known optimal or heuristic solutions using a standard data set for heterogeneous fleet vehicle routing problem. Additionally, we compare the relative performance of our proposed Hybrid PSI algorithm with two intelligent-based algorithms, Hybrid Population Heuristic algorithm and Improved Genetic Algorithm, using a real-world data set to illustrate the practical and validity of the model and algorithm.

     

On time optimal control of integrator switched systems with state constraints

In this paper, time optimal control problems of a class of integrator switched systems with polyhedral state constraint subsets are studied. We first develop a directed graph representation of the system discrete structure. Based on the graph representation, we generate candidate solution paths and propose an algorithm for seeking the optimal solution. A linear programming method for finding the optimal timing information for each path is then proposed. Finally, we report preliminary results on some sufficient conditions and techniques which help reduce the number of candidate paths.     

Edge partitions of optimal 2-plane and 3-plane graphs

A topological graph is a graph drawn in the plane. A topological graph is $k$-plane, $k>0$, if each edge is crossed at most $k$ times. We study the problem of partitioning the edges of a $k$-plane graph such that each partite set forms a graph with a simpler structure. While this problem has been studied for $k=1$, we focus on optimal 2-plane and on optimal 3-plane graphs, which are 2-plane and 3-plane graphs with maximum density. We prove the following results. (i) It is not possible to partition the edges of a simple (i.e., with neither self-loops nor parallel edges) optimal 2-plane graph into a 1-plane graph and a forest, while (ii) an edge partition formed by a 1-plane graph and two plane forests always exists and can be computed in linear time. (iii) There exist efficient algorithms to partition the edges of a simple optimal 2-plane graph into a 1-plane graph and a plane graph with maximum vertex degree at most 12, or with maximum vertex degree at most 8 if the optimal2-plane graph is such that its crossing-free edges form a graph with no separating triangles. (iv) There exists an infinite family of simple optimal 2-plane graphs such that in any edge partition composed of a 1-plane graph and a plane graph, the plane graph has maximum vertex degree at least 6 and the 1-plane graph has maximum vertex degree at least 12. (v) Every optimal 3-plane graph whose crossing-free edges form a biconnected graph can be decomposed, in linear time, into a 2-plane graph and two plane forests.     

Behavior of finite-nonstationary deterministic automata in a fuzzy environment

The paper presents a method of finding optimal control of generalized deterministic abstract automaton, the structure of which is given by an arbitrary finite graph in a fuzzy environment. The control is found in order to achieve a fuzzy goal, which is given as a fuzzy set in any fixed finite vertex of the automaton structural graph. The problem solution is divided into two stages. The first stage provides the greatest possible degree of achieving the fuzzy goal depending on the path from the initial graph vertex to the fixed one, while the second stage makes it possible to construct a set of input words that ensure the achievement of this goal on the selected path. The conclusion presents an example of the application of the proposed method for constructing a regular expression of control sequences for the given abstract finite-nonstationary deterministic automaton.     

Labeling algorithm for the shortest path problem with turn prohibitions with application to large-scale road networks

In real road networks, the presence of no-left, no-right or no U-turn signs, restricts the movement of vehicles at intersections. These turn prohibitions must be considered when calculating the shortest path between a starting and an ending point in a road network. We propose an extension of Dijkstra’s algorithm to solve the shortest path problem with turn prohibitions. The method uses arc labeling and a network structure with low memory requirements. We compare the proposed method with the dual graph approach in a set of randomly generated networks and Bogotá’s large-scale road network. Our computational experiments show that the performance of the proposed method is better than that of the dual graph approach, both in terms of computing time and memory requirements. We co-developed a Web-based decision support system for computing shortest paths with turn prohibitions that uses the proposed method as the core engine.