基于有限节点集的网络毁伤最大化问题研究

对网络实施攻击时,人们希望在有限的资源下获得最大的毁伤效果,而节点排序策略并不能实现毁伤最大.针对这种情况,定义攻击有限节点集的网络毁伤最大化问题,并给出问题的近似求解算法.由于近似求解算法计算复杂度较高,进一步提出基于重要节点的贪婪算法(greedy algorithm based on important nodes,GABIN).对无标度网络的实验表明:GABIN算法能够有效地减少计算时间,且效果接近于近似求解算法;当无标度网络的度指数$\gamma\geqslant2.5$时,GABIN算法的效果明显优于排序算法,所得节点集中超过30%的节点不同于排序算法.对Power网络的毁伤实验表明,GABIN算法适用于较大规模的实际网络,且效果显著优于度、介数、接近度、删除节点等排序算法.实验发现,利用GABIN算法获得的关键节点集包含大量的非中心性节点,这为网络攻击或网络防护提供了一个新的思路.     

Scheduling evacuation operations

In this paper, we consider a large-scale evacuation problem after a major disaster. The evacuation is assumed to occur by means of a fleet of buses, thus leading to scheduling the evacuation operations by buses [(bus evacuation problem (BEP)]. We propose time-indexed formulations as well as heuristic algorithms such as greedy algorithms and a matheuristic. This matheuristic uses the former formulation to improve the best solution obtained by the greedy heuristics. In computational experiments, we analyze and evaluate the efficiency of the proposed solution algorithms.     

The fixed set search applied to the power dominating set problem

In this article, we focus on solving the power dominating set problem and its connected version. These problems are frequently used for finding optimal placements of phasor measurement units in power systems. We present an improved integer linear program (ILP) for both problems. In addition, a greedy constructive algorithm and a local search are developed. A greedy randomised adaptive search procedure (GRASP) algorithm is created to find near optimal solutions for large scale problem instances. The performance of the GRASP is further enhanced by extending it to the novel fixed set search (FSS) metaheuristic. Our computational results show that the proposed ILP has a significantly lower computational cost than existing ILPs for both versions of the problem. The proposed FSS algorithm manages to find all the optimal solutions that have been acquired using the ILP. In the last group of tests, it is shown that the FSS can significantly outperform the GRASP in both solution quality and computational cost.     

移动传感器网络中路径扫描覆盖问题研究

扫描覆盖作为无线传感器网络中的重要应用之一,通过规划移动传感器对区域内兴趣点（POI）进行定期覆盖,因此相较于传统覆盖方法能以更低廉的成本监测POI。研究最少传感器数量-最小罚时路径扫描覆盖问题,即通过调度移动传感器扫描给定路径上的POI集合,使传感器使用数量及产生的POI总罚时成本之和最小。将该问题转换为整数规划,并基于该问题的特殊结构设计贪心算法和遗传算法,以求解大规模实例。在遗传算法基础上引入模拟退火操作,以设计一种遗传模拟退火算法,从而提高求解质量和算法局部寻优能力。实验结果表明,所提贪心算法、遗传算法及遗传模拟退火算法均有较好的收敛性,贪心算法求解质量相对较差,但求解速度快;遗传算法解的质量更好,但存在不稳定的问题,局部寻优能力较弱;遗传模拟退火算法的局部寻优能力和求解稳定性明显增强,解的质量优于其他两种算法。     

Metaheuristics for the single machine weighted quadratic tardiness scheduling problem

This paper considers the single machine scheduling problem with weighted quadratic tardiness costs. Three metaheuristics are presented, namely iterated local search, variable greedy and steady-state genetic algorithm procedures. These address a gap in the existing literature, which includes branch-and-bound algorithms (which can provide optimal solutions for small problems only) and dispatching rules (which are efficient and capable of providing adequate solutions for even quite large instances). A simple local search procedure which incorporates problem specific information is also proposed.The computational results show that the proposed metaheuristics clearly outperform the best of the existing procedures. Also, they provide an optimal solution for all (or nearly all, in the case of the variable greedy heuristic) the smaller size problems. The metaheuristics are quite close in what regards solution quality. Nevertheless, the iterated local search method provides the best solution, though at the expense of additional computational time. The exact opposite is true for the variable greedy procedure, while the genetic algorithm is a good all-around performer.     

一维下料问题的AB分类法

为了解决大规模的一维下料问题的计算困难, 根据一维下料问题的特点,把贪心算法和随机搜索技术有机地结合起来,利用随机搜索技术对贪心算法进行了有效的改进,提出了一种简单实用的AB分类法。 实验表明,该算法对规模较大的问题也能较快地获得问题最优解或精度较高的近似最优解。     

基于MRLT模型多关系社交网络影响力最大化研究

社交网络影响力最大化问题是基于特定的传播模型,在网络中寻找一组初始传播节点集合,通过其产生最终传播影响范围最大的一种最优化问题。已有的相关研究大多只是针对单关系社交网络,即在社交网络中只存在一种关系。但在现实中,社交网络的用户之间往往存在着多种关系,并且这多种关系共同影响着网络信息传播及其最终影响范围。在线性阈值模型的基础上,结合网络节点间存在的多种关系,提出MRLT传播模型来建模节点间的影响力传播过程,在此基础上提出基于反向可达集的MR-RRset算法,解决了传统影响力最大化问题研究过程中由于使用贪心算法所导致的计算性能较低的问题。最后通过在真实数据集上的实验对比,表明所提方法具有更好的影响力传播范围及较大的计算性能提升。     

Multiagent task allocation in social networks

This paper proposes a new variant of the task allocation problem, where the agents are connected in a social network and tasks arrive at the agents distributed over the network. We show that the complexity of this problem remains NP-complete. Moreover, it is not approximable within some factor. In contrast to this, we develop an efficient greedy algorithm for this problem. Our algorithm is completely distributed, and it assumes that agents have only local knowledge about tasks and resources. We conduct a broad set of experiments to evaluate the performance and scalability of the proposed algorithm in terms of solution quality and computation time. Three different types of networks, namely small-world, random and scale-free networks, are used to represent various social relationships among agents in realistic applications. The results demonstrate that our algorithm works well and also that it scales well to large-scale applications. In addition we consider the same problem in a setting where the agents holding the resources are self-interested. For this, we show how the optimal algorithm can be used to incentivize these agents to be truthful. However, the efficient greedy algorithm cannot be used in a truthful mechanism, therefore an alternative, cluster-based algorithm is proposed and evaluated.     

基于种子候选的贪心策略影响力最大化算法

爬山贪心算法的时间复杂度较高,不易扩展至大规模社会网络.为了解决此问题,文中从理论上分析节点集影响力评估可转化为局部概率解计算,能够提高算法运行效率.将局部概率解函数拓展到贪心算法中,提出基于种子候选的贪心影响力最大化算法和基于种子候选的偷懒贪心影响力最大化算法.在4个真实数据集上实验表明,文中算法与具有成本效益的惰性前向选择算法(CELF)性能一致,但在运行时间上快于CELF.     

The Virtue of Patience in Low-Complexity Scheduling of Packetized Media With Feedback

We consider streaming pre-encoded and packetized media over best-effort networks in the presence of acknowledgment feedbacks. We first review a rate-distortion (RD) optimization framework that can be employed in such scenarios. As part of the framework, a scheduling algorithm selects the data to send over the network at any given time, so as to minimize the end-to-end distortion, given an estimate of channel resources and a history of previous transmissions and received acknowledgements. In practice, a greedy scheduling strategy is often considered to limit the solution search space, and reduce the computational complexity associated to the RD optimization framework. Our work observes that popular greedy schedulers are strongly penalized by early retransmissions. Therefore, we propose a scheduling algorithm that avoids premature retransmissions, while preserving the low computational complexity aspect of the greedy paradigm. Such a scheduling strategy maintains close to optimal RD performance when adapting to network bandwidth fluctuations. Our experimental results demonstrate that the proposed patient greedy scheduler provides a reduction of up to 50% in transmission rate relative to conventional greedy approaches, and that it brings up to 2 dB of quality improvement in scheduling classical MPEG-based packet video streams     

A revised ant algorithm for solving location–allocation problem with risky demand in a multi-echelon supply chain network

This study addresses a capacitated facility location and task allocation problem of a multi-echelon supply chain against risky demands. Two and three-echelon networks are considered to maximize profit. The study represents the problem by a bi-level stochastic programming model. The revised ant algorithm proposed in the study improves the existing ant algorithm by using new design of heuristic desirability and efficient greedy heuristics to solve the problem. A set of computational experiments is reported to not only allow to fine-tune the parameters of the algorithm but also to evaluate its performance for solving the problem proposed. Experiments reveal that the proposed solution algorithm can reach 95–99% of the optimal solution against risky demands while consuming only 1000th of the computational time for large-sized problems as compared to an optimization-based tool.     

A redistricting problem applied to meter reading in power distribution networks

The capacitated redistricting problem (CRP) has the objective to redefine, under a given criterion, an initial set of districts of an urban area represented by a geographic network. Each node in the network has different types of demands and each district has a limited capacity. Real-world applications consider more than one criteria in the design of the districts, leading to a multicriteria CRP (MCRP). Examples are found in political districting, sales design, street sweeping, garbage collection and mail delivery. This work addresses the MCRP applied to power meter reading and two criteria are considered: compactness and homogeneity of districts. The proposed solution framework is based on a greedy randomized adaptive search procedure and multicriteria scalarization techniques to approximate the Pareto frontier. The computational experiments show the effectiveness of the method for a set of randomly generated networks and for a real-world network extracted from the city of São Paulo.     

Genetic local search and hardness of approximation for the server load balancing problem

We consider a well-known NP-hard server load balancing problem. We study the computational complexity of finding approximate solutions with guaranteed accuracy estimate. We show that this problem is Log-APX-hard with respect to PTAS reductions. To solve the problem, we develop an approximate method based on the ideas of genetic local search. We show results of computational experiments.     

Heuristic search for the stacking problem

This paper presents the Stacking Problem, a hard combinatorial optimization problem concerning handling and storage of items in a warehouse, where they are handled by a crane and organized into stacks. We define the problem, study its complexity class, and present a mathematical programming model to solve it. In order to tackle medium‐ or large‐scale instances, we propose a simulation‐based algorithm using semi‐greedy construction heuristics. This simple approach allows for multiple constructions, finding solutions within reasonable time even for large instances. Three semi‐greedy heuristics are proposed and compared in an extensive computational experiment, where we study the relation between the number of constructions and the best solution obtained using each heuristic.     

A GRASP with path‐relinking and restarts heuristic for the prize‐collecting generalized minimum spanning tree problem

Given a graph with its vertex set partitioned into a set of groups, nonnegative costs associated to its edges, and nonnegative prizes associated to its vertices, the prize‐collecting generalized minimum spanning tree problem consists in finding a subtree of this graph that spans exactly one vertex of each group and minimizes the sum of the costs of the edges of the tree less the prizes of the selected vertices. It is a generalization of the NP‐hard generalized minimum spanning tree optimization problem. We propose a GRASP (greedy randomized adaptive search procedure) heuristic for its approximate solution, incorporating path‐relinking for search intensification and a restart strategy for search diversification. The hybridization of the GRASP with path‐relinking and restarts heuristic with a data mining strategy that is applied along with the GRASP iterations, after the elite set is modified and becomes stable, contributes to making the heuristic more robust. The computational experiments show that the heuristic developed in this work found very good solutions for test problems with up to 439 vertices. All input data for the test instances and detailed numerical results are made available from Mendeley Data.     

自适应细菌觅食算法求解折扣{0-1}背包问题

针对确定性算法难以求解的大规模折扣{0-1}背包问题（D{0-1}KP）,提出了自适应细菌觅食算法（ABFO）求解D{0-1}KP的两种算法。首先,给出了D{0-1}KP的两种数学模型;然后,针对细菌觅食算法的趋化操作提出了自适应趋化策略;最后,利用两种贪心修复与优化策略处理两种数学模型中的不可行解,得到求解D{0-1}KP的FirABFO和SecABFO算法。仿真实验表明,FirABFO和SecABFO均能得到最优解或近似比几乎等于1的近似解,非常适于求解D{0-1}KP,并且SecABFO 的求解性能比FirABFO更优。     

QoS vs. energy: A traffic-aware topology management scheme for green heterogeneous networks

Increasing environmental awareness combined with the high energy prices has driven the network operators to reduce their carbon dioxide footprint by adopting energy efficient green methods. In this paper, we aim to save energy by both switching base stations on/off and adaptively adjusting their transmission power according to the present traffic conditions for heterogenous wireless cellular networks. We formulate a novel linear programming model for the Traffic-Aware Topology Management (TAM) problem to find the best possible topology which minimizes the overall power consumption of the network while satisfying a certain Quality of Service level in Wideband Code Division Multiple Access packet-switched cellular networks. Although the optimization tools provide the optimum solutions, it is not possible to handle large instances due to the space and computational complexity. Hence, we propose a Green TAM Algorithm to solve the large-scale realistic instances of the formulated problem and compare our results with the results of two previously proposed methods, a greedy heuristic and a commercial optimization tool. We show that the proposed TAM scheme helps to maintain an energy-aware network and saves significant amount of energy by adjusting the network topology to the current traffic conditions adaptively.     

Capacitated clustering problem in computational biology: Combinatorial and statistical approach for sibling reconstruction

The capacitated clustering problem (CCP) has been studied in a wide range of applications. In this study, we investigate a challenging CCP in computational biology, namely, sibling reconstruction problem (SRP). The goal of SRP is to establish the sibling relationship (i.e., groups of siblings) of a population from genetic data. The SRP has gained more and more interests from computational biologists over the past decade as it is an important and necessary keystone for studies in genetic and population biology. We propose a large-scale mixed-integer formulation of the CCP for SRP that is based on both combinatorial and statistical genetic concepts. The objective is not only to find the minimum number of sibling groups, but also to maximize the degree of similarity of individuals in the same sibling groups while each sibling group is subject to genetic constraints derived from Mendel's laws. We develop a new randomized greedy optimization algorithm to effectively and efficiently solve this SRP. The algorithm consists of two key phases: construction and enhancement. In the construction phase, a greedy approach with randomized perturbation is applied to construct multiple sibling groups iteratively. In the enhancement phase, a two-stage local search with a memory function is used to improve the solution quality with respect to the similarity measure. We demonstrate the effectiveness of the proposed algorithm using real biological data sets and compare it with state-of-the-art approaches in the literature. We also test it on larger simulated data sets. The experimental results show that the proposed algorithm provide the best reconstruction solutions.     

Evolutionary Optimization of File Assignment for a Large-Scale Video-on-Demand System

We present a genetic algorithm for tackling a file assignment problem for a large-scale video-on-demand system. The file assignment problem is to find the optimal replication and allocation of movie files to disks so that the request blocking probability is minimized subject to capacity constraints. We adopt a divide-and-conquer strategy, where the entire solution space of file assignments is divided into subspaces. Each subspace is an exclusive set of solutions sharing a common file replication instance. This allows us to utilize a greedy file allocation method for finding a good-quality heuristic solution within each subspace. We further design two performance indices to measure the quality of the heuristic solution on 1.) its assignment of multicopy movies and 2.) its assignment of single-copy movies. We demonstrate that these techniques, together with ad hoc population handling methods, enable genetic algorithms to operate in a significantly reduced search space and achieve good-quality file assignments in a computationally efficient way.     

Scalable influence maximization for independent cascade model in large-scale social networks

Influence maximization, defined by Kempe et al. (SIGKDD 2003), is the problem of finding a small set of seed nodes in a social network that maximizes the spread of influence under certain influence cascade models. The scalability of influence maximization is a key factor for enabling prevalent viral marketing in large-scale online social networks. Prior solutions, such as the greedy algorithm of Kempe et al. (SIGKDD 2003) and its improvements are slow and not scalable, while other heuristic algorithms do not provide consistently good performance on influence spreads. In this article, we design a new heuristic algorithm that is easily scalable to millions of nodes and edges in our experiments. Our algorithm has a simple tunable parameter for users to control the balance between the running time and the influence spread of the algorithm. Our results from extensive simulations on several real-world and synthetic networks demonstrate that our algorithm is currently the best scalable solution to the influence maximization problem: (a) our algorithm scales beyond million-sized graphs where the greedy algorithm becomes infeasible, and (b) in all size ranges, our algorithm performs consistently well in influence spread—it is always among the best algorithms, and in most cases it significantly outperforms all other scalable heuristics to as much as 100–260% increase in influence spread.