Variable Neighborhood Decomposition Search

The recent Variable Neighborhood Search (VNS) metaheuristic combines local search with systematic changes of neighborhood in the descent and escape from local optimum phases. When solving large instances of various problems, its efficiency may be enhanced through decomposition. The resulting two level VNS, called Variable Neighborhood Decomposition Search (VNDS), is presented and illustrated on the p-median problem. Results on 1400, 3038 and 5934 node instances from the TSP library show VNDS improves notably upon VNS in less computing time, and gives much better results than Fast Interchange (FI), in the same time that FI takes for a single descent. Moreover, Reduced VNS (RVNS), which does not use a descent phase, gives results similar to those of FI in much less computing time.     

A Note on Distance Matrices Yielding Elementary Landscapes for the TSP

Symmetric and antisymmetric distance matrices in the single agent traveling salesman problem (TSP) are not the only distance matrices to generate elementary landscapes for swap and 2-opt neighborhoods.     

Reconstruction of the Neighborhood Deck of an Ordered Set

We show that the neighborhood deck of an ordered set can be reconstructed from the deck of one point deleted subsets. As a consequence of the above results we reconstruct some maximal cards and present short new proofs of the reconstructibility of ordered sets of width 2 and of the recognizability of N-free ordered sets. We also reconstruct the maximal cards of N-free ordered sets.     

A three-phase method for identifying functionally related protein groups in weighted PPI networks

Identifying significant protein groups is of great importance for further understanding protein functions. This paper introduces a novel three-phase heuristic method for identifying such groups in weighted PPI networks. In the first phase a variable neighborhood search (VNS) algorithm is applied on a weighted PPI network, in order to support protein complexes by adding a minimum number of new PPIs. In the second phase proteins from different complexes are merged into larger protein groups. In the third phase these groups are expanded by a number of 2-level neighbor proteins, favoring proteins that have higher average gene co-expression with the base group proteins. Experimental results show that: (i) the proposed VNS algorithm outperforms the existing approach described in literature and (ii) the above-mentioned three-phase method identifies protein groups with very high statistical significance.     

An algorithm to solve a quantile optimization problem with loss function having a separable structure,and its application to an aerospace problem

A quantile minimization problem with loss function having separable structure is considered. The distribution of the random parameters is assumed to be normal. To solve the problem, the confidence method and the sample average approximation method are used. Thus, the problem is reduced to a combinatorial one, which is solved by using the variable neighborhood search. The suggested algorithm is applied to optimization of runway area. Parameters of the runway are selected to minimize the area taking into account random wind speed.     

An integer linear programming approach and a hybrid variable neighborhood search for the car sequencing problem

In this paper we present two major approaches to solve the car sequencing problem, in which the goal is to find an optimal arrangement of commissioned vehicles along a production line with respect to constraints of the form “no more than l_ccars are allowed to require a component c in any subsequence of m_cconsecutive cars”. The first method is an exact one based on integer linear programming (ILP). The second approach is hybrid: it uses ILP techniques within a general variable neighborhood search (VNS) framework for examining large neighborhoods. We tested the two methods on benchmark instances provided by CSP_LIB and the automobile manufacturer RENAULT for the ROADEF Challenge 2005. These tests reveal that our approaches are competitive to previous reported algorithms. For the CSP_LIB instances we were able to shorten the required computation time for reaching and proving optimality. Furthermore, we were able to obtain tight bounds on some of the ROADEF instances. For two of these instances the proposed ILP-method could provide new optimality proofs for already known solutions. For the VNS, the individual contributions of the used neighborhoods are also experimentally analyzed. Results highlight the significant impact of each structure. In particular the large ones examined using ILP techniques enhance the overall performance significantly, so that the hybrid approach clearly outperforms variants including only commonly defined neighborhoods.     

A Selection Theorem for Strongly Regular Multivalued Mappings

We prove the following generalization of a theorem of Ferry concerning selections of strongly regular multivalued maps onto the class of paracompact spaces: Let : X (Z, ) be a map of a paracompact space X into a metric space (Z, ) whose values (x) are complete subspaces of Z and absolute extensors (AE), for every x X. Suppose that can be represented as = , where : X Y is a continuous singlevalued map of X onto some finite-dimensional paracompact space Y and : Y (Z, ) is a strongly regular map. Then for every closed subset A X and every selection r : A Z of the map |A : A Z, there exists an extension : X Z of r such that is a selection of the map . We also prove a local version of this theorem.     

Variable neighborhood search for harmonic means clustering

Harmonic means clustering is a variant of minimum sum of squares clustering (which is sometimes called K-means clustering), designed to alleviate the dependance of the results on the choice of the initial solution. In the harmonic means clustering problem, the sum of harmonic averages of the distances from the data points to all cluster centroids is minimized. In this paper, we propose a variable neighborhood search heuristic for solving it. This heuristic has been tested on numerous datasets from the literature. It appears that our results compare favorably with recent ones from tabu search and simulated annealing heuristics.     

QUANTIFIED MODAL LOGIC WITH NEIGHBORHOOD SEMANTICS

The paper presents a semantics for quantified modal logic which has a weaker axiomatization than the usual Kripke semantics. In particular, the Barcan Formula (BF) and its converse are not valid with the proposed semantics. Subclasses of models which validate BF and other interesting formulas are presented. A completeness theorem is proved, and the relation between this result and completeness with respect to Kripke models is investigated.     

拓扑空间的若干分离性及关于杨忠道定理的两个等价条件

在一般拓扑学中，有一个著名的杨忠道定理，拓扑空间X的任意子集的导集是闭集的充分必要条件是每个单点集的导集是闭集，本文给出另外两个等价条件，并讨论了T0，T1空间与我们称之为T0．5空间之间的关系。