中药最优配方筛选的图论方法

中药在治疗有些疾病时有独特的疗效,疗效的好坏主要取决于方剂中各药物的适当配伍。但是由于中药各药物之间的排列组合方式数目巨大,再加上药物剂量的变化,它们之间的组合数更是难以计数,对这些组合一一进行药效学实验难以实现,这就制约了中药的进一步研发。针对这一问题,该文将中药最优配方筛选问题转化为求一顶点赋权图的最大权团问题,利用求图的最大权团的算法实现中药最优配方筛选。该方法工作量小、简便易学、容易使用。     

一种基于极大团的关键时间段挖掘方法

针对带有时间属性的海量事务处理问题,提出了一种求最大相关性的最小时间区间(关键时间段KTI)的算法。通过利用极大团把海量的数据项进行有效的划分,降低了后续数据挖掘和决策选择的复杂度。针对特定的含有时间参量的极大团,通过寻找关键时间段(KTI),提高了决策的准确度,同时可以减小分析数据的规模,降低对计算资源的需求。假设事务中各项出现的事件具有相同的概率分布,得到了一种寻找关键时间段(KTI)的算法。从理论上证明了算法的正确性,并对其进行了复杂度分析,通过实际数据验证了算法的可行性。     

A tutorial on branch and cut algorithms for the maximum stable set problem

This tutorial provides an overview of various characteristics of effective branch and cut type algorithms for the maximum stable set problem. We discuss several facet‐defining inequalities for the stable set polytope along with their separation routines. In particular, we review implementation tweaks for the separation routines and reference empirical studies, illustrating the performance of these cutting planes for benchmark graphs. In addition to the polyhedral study, we present basic preprocessing, discuss heuristic methods particularly suited within a branch and cut framework, and examine a branching rule.     

基于团结构的三维关节人手跟踪方法

针对传统图模型建模人手中约束函数冗余度高的问题,提出一种基于团的图模型表示关节人手。该模型充分利用人手特有的生理结构和运动约束表示人手,在一定程度上消除了传统人手图模型中的冗余信息,降低模型表示的复杂度。给出人手团势函数用于建模人手各个部分之间的约束关系。实验结果表明,该模型提高跟踪算法的效率,能够满足基于视觉的精细人手跟踪的要求。     

分层关联的多目标跟踪算法研究

检测跟踪(Tracking by detection)是近年来多目标跟踪领域的一个主要研究方向。遵循检测跟踪框架,提出一种基于分层关联的全局性的数据关联算法。首先利用目标检测器在整个视频上检测目标,得到检测响应;然后利用广义最小团图在视频片段中对检测响应进行数据关联,得到轨迹片段;最后再在整个视频中对轨迹片段进行分层关联,得到最终的轨迹。在公共数据集上的测试结果表明,该算法能够有效地对多个目标进行数据关联,具有较强的处理遮挡能力。     

Electric vehicle scheduling and optimal charging problem: complexity,exact and heuristic approaches

This paper deals with the Electric Vehicle (EV) Scheduling and Optimal Charging Problem. More precisely, given a fleet of EVs and Combustion Engine Vehicles (CVs), a set of tours to be processed by vehicles and a charging infrastructure, the problem aims to optimise the assignment of vehicles to tours and minimise the charging cost of EVs while considering several operational constraints mainly related to chargers, electricity grid and EVs driving range. We prove that the Electric Vehicle Scheduling and Charging Problem (EVSCP) is NP-hard in the ordinary sense. We provide a mixed-integer linear programming formulation to model the EVSCP and use CPLEX to solve small and medium instances. To solve large instances, we propose two heuristics: a Sequential Heuristic (SH) and a Global Heuristic (GH). The SH considers the EVs sequentially. To each EV, it assigns a set of tours and guarantees the feasibility of a charging schedule. Then, it generates an optimal charging schedule for this EV. However, the GH computes, in the first step, a feasible assignment of tours to all EVs. In the second step, it applies a global Min-Cost-Flow-based charging algorithm to minimise the charging cost of the EVs fleet. To evaluate the efficiency of our solving approaches, computational results on a large set of real and randomly generated test instances are reported and compared.     

联合能耗与负载均衡的虚拟网络映射方法

为解决弹性光网络中虚拟网络映射时能耗严重、资源分配不均的问题,该文提出一种联合能耗与负载均衡的虚拟网络映射（PC-LB-VONE）方法.在虚拟节点映射时,选择相邻链路长度短、光节点计算资源多与相邻链路带宽资源多的光节点映射.在虚拟链路映射时,提出一种基于极大团的候选光路资源匹配度单路径映射策略.当单路径映射失败时,设计基于链路负载均值的多路径映射策略.仿真结果表明,所提方法能在减少弹性光网络能耗的同时均衡网络负载.     

一种应用加权相容图的可测性寄存器分配算法

提出一种基于加权相容图的可测性寄存器分配模型,给出一个基于可测寄存器分配准则的相容图边的权值公式,并运用改进的加权团划分算法对加权相容图进行处理,从而实现了在寄存器分配过程中同时考虑4个可测性准则,达到提高设计可测性的目的.实验结果表明了算法在可测性方面的有效性.     

A scalable,parallel algorithm for maximal clique enumeration

The problem of maximal clique enumeration (MCE) is to enumerate all of the maximal cliques in a graph. Once enumerated, maximal cliques are widely used to solve problems in areas such as 3-D protein structure alignment, genome mapping, gene expression analysis, and detection of social hierarchies. Even the most efficient serial MCE algorithms require large amounts of time to enumerate the maximal cliques in networks arising from these problems that contain hundreds, thousands, or larger numbers of vertices. The previous attempts to provide practical solutions to the MCE problem through parallel implementation have had limited success, largely due to a number of challenges inherent to the nature of the MCE combinatorial search space. On the one hand, MCE algorithms often create a backtracking search tree that has a highly irregular and hard-or-impossible to predict structure; therefore, almost any static decomposition of the search tree by parallel processors results in highly unbalanced processor execution times. On the other hand, the data-intensive nature of the MCE problem often makes naive dynamic load distribution strategies that require extensive data movement prohibitively expensive. As a result, good scaling of the overall execution time of parallel MCE algorithms has been reported for only up to a couple hundred processors. In this paper, we propose a parallel, scalable, and memory-efficient MCE algorithm for distributed and/or shared memory high performance computing architectures, whose runtime scales linearly for thousands of processors on real-world application graphs with hundreds and thousands of nodes. Its scalability and efficiency are attributed to the proposed: (a) representation of the search tree decomposition to enable parallelization; (b) parallel depth-first backtracking search to both constrain the search space and minimize memory requirement; (c) least stringent synchronization to minimize data movement; and (d) on-demand work stealing intelligently coupled with work stack splitting to minimize computing elements’ idle time. To the best of our knowledge, the proposed parallel MCE algorithm is the first to achieve a linear scaling runtime using up to 2048 processors on Cray XT machines for a number of real-world biological networks.     

黑龙江垦区农业自然资源开发利用途径研究

本文为《黑龙江垦区发展高产优质高效农业途径研究》课题之二,任务是调查综合农业自然资源的数量、质量、分布、开发利用现状和存在问题,从宏观上分析研究资源的合理配置和开发利用途径,为垦区发展”两高一优”农业打好基础。