A genetic algorithm approach to solving the anti-covering location problem

Abstract: In this paper we address the problem of locating a maximum weighted number of facilities such that no two are within a specified distance from each other. A natural process of evolution approach, more specifically a genetic algorithm, is proposed to solve this problem. It is shown that through the use of a commercially available spreadsheet-based genetic algorithm software package, the decision-maker with a fundamental knowledge of spreadsheets can easily set up and solve this optimization problem. Also, we report on our extensive computational experience using three different data sets.     

A convex programming with nested constraints on the amount of resources

This paper investigates the resource allocation problem of maximizing a strictly concave objective function under nested constraints on a weighted amount of resources. The resources are distributed in a multi-dimensional space and the distribution gives a planner some reward. The constraints on the resources are set in such a way that a weighted amount of resources is limited in each level of subspace as well as in the whole space. We call such constraints nested. The purpose of this paper is to devise efficient methods for an optimal distribution of resources under the constraints. For the concave maximization problem, first we derive necessary and sufficient conditions for an optimal solution and, secondly, propose two methods to solve the problem. Both methods manipulate the so-called Lagrangian multipliers and make a sequence of feasible solutions so as to satisfy all the necessary and sufficient conditions. Numerical examination confirms that the proposed methods perform better than some well-known methods of nonlinear programming in terms of computational time.     

Set Packing问题的研究进展

Set Packing问题起源于分割问题的应用,是在强约束条件对元素进行划分。在复杂性理论中,此问题是一类重要的NP难问题,被广泛应用于调度、代码优化和生物信息学等领域。特别是在参数计算理论产生后,此问题再次成为研究的热点问题。依据所研究问题的差异,本文将Set Packing问题分成5类,并给出了具体的定义。在此基础上,分别介绍了求解这5类问题的相关算法,着重分析和比较了参数算法中所运用的各项技术,并提出了该问题算法研究的一些发展方向。     

Iterative Dutch combinatorial auctions

The combinatorial auction problem can be modeled as a weighted set packing problem. Similarly the reverse combinatorial auction can be modeled as a weighted set covering problem. We use the set packing and set covering formulations to suggest novel iterative Dutch auction algorithms for combinatorial auction problems. We use generalized Vickrey auctions (GVA) with reserve prices in each iteration. We prove the convergence of the algorithms and show that the solutions obtained using the algorithms lie within provable worst case bounds. We conduct numerical experiments to show that in general the solutions obtained using these algorithms are much better than the theoretical bounds.     

A Tabu Search Algorithm for application placement in computer clustering

This paper presents and analyzes a model for the problem of placing applications on computer clusters (APP). In this problem, organizations requesting a set of software applications have to be assigned to computer clusters such that the costs of opening clusters and installing the necessary applications are minimized. This problem is related to known OR problems such as the multiproduct facility location problem and the generalized bin packing problem. We show that APP is NP-hard, and then propose a simple Tabu Search heuristic to solve it. The performance of the Tabu Search heuristic is assessed via extensive computational experiments, which indicate the promise of the proposed Tabu Search.     

Deciding implication for functional dependencies in complex-value databases

Modern applications increasingly require the storage of data beyond relational structure. The challenge of providing well-founded data models that can handle complex objects such as lists, sets, multisets, unions and references has not been met yet in a completely satisfactory way. The success of such data models will greatly depend on the existence of automated database design techniques that generalise achievements from relational databases. In this paper, we study the implication problem of functional dependencies (FDs) in the presence of records, sets, multisets and lists. Database schemata are defined as nested attributes, database instances as nested relations and FDs are defined in terms of subattributes of the database schema. The expressiveness of FDs deviates fundamentally from previous approaches in different data models including the nested relational data model and XML.     

Hierarchical Structures on Multigranulation Spaces

Though many hierarchical structures have been proposed to analyze the finer or coarser relationships between two granulation spaces,these structures can only be used to compare the single granulation spaces.However,it should be noticed that the concept of multigranulation plays a fundamental role in the development of granular computing.Therefore,the comparison between two multigranulation spaces has become a necessity.To solve such problem,two types of the multigranulation spaces are considered:one is the partition-based multigranulation space,the other is the covering-based multigranulation space.Three different hierarchical structures are then proposed on such two multigranulation spaces,respectively.Not only the properties about these hierarchical structures are discussed,but also the relationships between these hierarchical structures and the multigranulation rough sets are deeply investigated.It is shown that the first hierarchical structure is consistent with the monotonic varieties of optimistic multigranulation rough set,and the second hierarchical structure is consistent to the monotonic varieties of pessimistic multigranulation rough set,the third hierarchical structure is consistent to the monotonic varieties of both optimistic and pessimistic multigranulation rough sets.     

On verification of nested workflows with extra constraints: From theory to practice

Workflows are used to formally describe processes of various types such as business and manufacturing processes. One of the critical tasks of workflow management is automated discovery of possible flaws in the workflow – workflow verification. In this paper, we formalize the problem of workflow verification as the problem of verifying that there exists a feasible process for each task in the workflow. This problem is tractable for nested workflows that are the workflows with a hierarchical structure similar to hierarchical task networks in planning. However, we show that if extra synchronization, precedence, or causal constraints are added to the nested structure, the workflow verification problem becomes NP-complete. We present a workflow verification algorithm for nested workflows with extra constraints that is based on constraint satisfaction techniques and exploits an incremental temporal reasoning algorithm. We then experimentally demonstrate efficiency of the proposed techniques on randomly generated workflows with various structures and sizes. The paper is concluded by notes on exploiting the presented techniques in the application FlowOpt for modeling, optimizing, visualizing, and analyzing production workflows.     

Variable neighbourhood search for the variable sized bin packing problem

The variable sized bin packing problem is a generalisation of the one-dimensional bin packing problem. Given is a set of weighted items, which must be packed into a minimum-cost set of bins of variable sizes and costs. This problem has practical applications, for example, in packing, transportation planning, and cutting. In this work we propose a variable neighbourhood search metaheuristic for tackling the variable sized bin packing problem. The presented algorithm can be seen as a hybrid metaheuristic, because it makes use of lower bounding techniques and dynamic programming in various algorithmic components. An extensive experimentation on a diverse set of problem instances shows that the proposed algorithm is very competitive with current state-of-the-art approaches.     

Guided Local Search for Solving SAT and Weighted MAX-SAT Problems

In this paper, we show how Guided Local Search (GLS) can be applied to the SAT problem and show how the resulting algorithm can be naturally extended to solve the weighted MAX-SAT problem. GLS is a general, penalty-based meta-heuristic, which sits on top of local search algorithms to help guide them out of local minima. GLS has been shown to be successful in solving a number of practical real-life problems, such as the traveling salesman problem, BT"s workforce scheduling problem, the radio link frequency assignment problem, and the vehicle routing problem. We present empirical results of applying GLS to instances of the SAT problem from the DIMACS archive and also a small set of weighted MAX-SAT problem instances and compare them with the results of other local search algorithms for the SAT problem.     

Genetic algorithm for the personnel assignment problem with multiple objectives

The assignment problem is a well-known graph optimization problem defined on weighted-bipartite graphs. The objective of the standard assignment problem is to maximize the summation of the weights of the matched edges of the bipartite graph. In the standard assignment problem, any node in one partition can be matched with any node in the other partition without any restriction. In this paper, variations of the standard assignment problem are defined with matching constraints by introducing structures in the partitions of the bipartite graph, and by defining constraints on these structures. According to the first constraint, the matching between the two partitions should respect the hierarchical-ordering constraints defined by forest and level graph structures produced by using the nodes of the two partitions respectively. In order to define the second constraint, the nodes of the partitions of the bipartite graph are distributed into mutually exclusive sets. The set-restriction constraint enforces the rule that in one of the partitions all the elements of each set should be matched with the elements of a set in the other partition. Even with one of these constraints the assignment problem becomes an NP-hard problem. Therefore, the extended assignment problem with both the hierarchical-ordering and set-restriction constraints becomes an NP-hard multi-objective optimization problem with three conflicting objectives; namely, minimizing the numbers of hierarchical-ordering and set-restriction violations, and maximizing the summation of the weights of the edges of the matching. Genetic algorithms are proven to be very successful for NP-hard multi-objective optimization problems. In this paper, we also propose genetic algorithm solutions for different versions of the assignment problem with multiple objectives based on hierarchical and set constraints, and we empirically show the performance of these solutions.     

Modeling and manipulating the structure of hierarchical schemas for the web

The Semantic Web is the next step of the current Web where information will become more machine-understandable to support effective data discovery and integration. Hierarchical schemas, either in the form of tree-like structures (e.g., DTDs, XML schemas), or in the form of hierarchies on a category/subcategory basis (e.g., thematic hierarchies of portal catalogs), play an important role in this task. They are used to enrich semantically the available information. Up to now, hierarchical schemas have been treated rather as sets of individual elements, acting as semantic guides for browsing or querying data. Under that view, queries like “find the part of a portal catalog which is not present in another catalog” can be answered only in a procedural way, specifying which nodes to select and how to get them. For this reason, we argue that hierarchical schemas should be treated as full-fledged objects so as to allow for their manipulation. This work proposes models and operators to manipulate the structural information of hierarchies, considering them as first-class citizens. First, we explore the algebraic properties of trees representing hierarchies, and define a lattice algebraic structure on them. Then, turning this structure into a boolean algebra, we present the operators S-union, S-intersection and S-difference to support structural manipulation of hierarchies. These operators have certain algebraic properties to provide clear semantics and assist the transformation, simplification and optimization of sequences of operations using laws similar to those of set theory. Also, we identify the conditions under which this framework is applicable. Finally, we demonstrate an application of our framework for manipulating hierarchical schemas on tree-like hierarchies encoded as RDF/s files.     

基于语义标签生成和偏序结构的图像层级分类

智能电子设备和互联网的普及,使得图像数据爆炸性膨胀.为了有效管理复杂图像资源,本文提出了一种基于加权语义邻近集和形式概念偏序结构的图像层级分类方法.首先,根据图像语义相关分数,对不同程度语义设定自适应权系数,从训练图库中构建加权语义邻近集,通过对语义邻近集中图像的词频分布进行判决,自动生成图像的多个语义标签;然后,以每幅图像为对象,以每幅图像自动生成的语义标签为属性,构建形式背景,通过偏序结构算法对复杂图像集进行有效的层级分类.本文方法可以得到图像库中图像之间明确的结构关系和图像类别之间的从属关系,为复杂图像大数据进行层级分类管理提供了有效的思路.本文对Corel5k、EspGame和Iaprtc12三个数据库进行了图像标注实验,证明了标注的语义完整性和主要语义的准确性;并对Corel5k数据库进行了图像的层级分类实验,结果表明层级分类效果显著.     

A hierarchical algorithm for the planar single-facility location routing problem

Location routing problem (LRP) is an important logistical problem that comprises two of the main logistical drivers namely facility location and vehicle routing. In this paper, we focus on the planar single-facility LRP with Euclidean distance where the location of the facility can be anywhere in the space and not restricted to a given set of potential sites only as in the discrete case. A hierarchical heuristic-based method is put forward which continuously takes into account the information from the routing results while systematically improving the location using the end-points of the obtained routes. In addition, some enhancement schemes that include a set of local searches as well as diversification and intensification mechanisms are also incorporated into the search. The proposed method outperformed the existing approaches when tested on the data sets taken from the literature. Our approach produced nine new best results out of the fifteen in the literature besides being relatively robust when compared to the existing methods.     

Scaling step-wise refinement

Step-wise refinement is a powerful paradigm for developing a complex program from a simple program by adding features incrementally. We present the AHEAD (algebraic hierarchical equations for application design) model that shows how step-wise refinement scales to synthesize multiple programs and multiple noncode representations. AHEAD shows that software can have an elegant, hierarchical mathematical structure that is expressible as nested sets of equations. We review a tool set that supports AHEAD. As a demonstration of its viability, we have bootstrapped AHEAD tools from equational specifications, refining Java and nonJava artifacts automatically; a task that was accomplished only by ad hoc means previously.     

RDBMS中层次查询结果的XML文档生成

数据库应用系统中相当多的数据都呈现出相应的层次特征,对这类数据,常常需要生成元素间保持层次特征的XML文档,用一般的查询机制来解决这个问题比较繁琐,以Oracle9i数据库第2版为例,应用层次查询,并结合OracleXML DB,对层次查询结果相对应的保持层次特征的XML文档的生成机制进行了研究,并将其应用于税务信息综合查询系统之中.结果表明,该方法简单、效率高、应用效果良好.     

Semantic analysis of role mining results and shadowed roles detection

The use of role engineering has grown in importance with the expansion of highly abstracted access control frameworks in organizations. In particular, the use of role mining techniques for the discovery of roles from previously deployed authorizations has facilitated the configuration of such frameworks. However, the literature lacks from a clear basis for appraising and leveraging the learning outcomes of the role mining process. In this paper, we provide such a formal basis. We compare sets of roles by projecting roles from one set into the other set. This approach is useful to measure how comparable the two configurations of roles are, and to interpret each role. We formally define the problem of comparing sets of roles, and prove that the problem is NP-complete. Then, we propose an algorithm to map the inherent relationship between the sets based on Boolean expressions. We demonstrate the correctness and completeness of our solution, and investigate some further issues that may benefit from our approach, such as detection of unhandled perturbations or source misconfiguration. In particular, we emphasize that the presence of shadowed roles in the role configuration increases the time complexity of sets of roles comparison. We provide a definition of the shadowed roles problem and propose a solution that detects different cases of role shadowing.     

一种自适应优化松弛量的装箱算法

装箱问题是物流系统和生产系统中的一个经典而重要的数学优化问题。装箱指把一系列物品按照一定顺序放进具有固定容量的箱子中,并最小化所使用的箱子数量,以最大限度地获取装箱问题的近似最优解。然而,现有的装箱算法存在明显的缺陷。遗传算法计算量过大,甚至无法求出所需解,启发式算法无法处理极端值问题,而现有的改进算法即使在引入松弛量的情况下,也极易陷入局部最小值。文中提出的Adaptive-MBS算法采用自适应权重来改进原有方法,即允许方法有一定的松弛量,并具有捕捉物体样本空间随时间变化的直觉,以使用更好的松弛量策略来装箱。Adaptive-MBS算法首先以当前箱子为中心,使用Adaptive_Search搜索算法迭代找到适合箱子容量的集合中所有物体的子集,Adaptive_Search搜索算法不要求完全装满箱子,而是允许箱子具有一定的松弛量,在训练过程中根据当前状态的变化,实现自动地调整松弛量,在找到完全填满箱子的子集后迭代至下轮搜索直至遍历完成。该方法不易陷入局部最优,具有较强的发现全局最优解的能力。文中使用装箱问题中经典的BINDATA和SCH_WAE数据集进行实验,结果表明,数据集中多达991例问题可以通过Adaptive-MBS算法得到最优解。在没有求解出最优解的实例上,所提算法也在所有对比算法上具有最低的相对偏移量百分比。数值实验结果表明,相较于其他经典的装箱算法,Adaptive-MBS算法有更好的效果,其收敛速度也显著优于其他算法。