LATNA lab. will take a part in the international scientific conference "Science of the Future"

17-20 September 2014, in St. Petersburg, the Ministry of education and science of the Russian Federation conducts the first international scientific conference "Science of the Future". Laboratory members will present their researches.

The following presetations will be made by LATNA members:

Pardalos P.M.: Knowledge discovery and Optimization Heuristics for Massive Networks

Abstract: In recent years, data mining and optimization heuristics have been used to analyze many large (and massive) data-sets that can be represented as a network. In these networks, certain attributes are associated with vertices and edges. This analysis  often provides useful information about the internal structure of the datasets they represent. We are going to discuss our work on several networks from telecommunications (call graph), financial networks (market graph), social networks, and neuroscience.

In addition, we are going to present recent results on critical element selection. In network analysis, the problem of detecting subsets of elements important to the connectivity of a network (i.e., critical elements) has become a fundamental task over the last few years. Identifying the nodes, arcs, paths, clusters, cliques, etc., that are responsible for network cohesion can be crucial for studying many fundamental properties of a network.

Kalyagin V.A.: Identification of Network Structures in Statistical Data Sets

Abstract: Network model for statistical data sets is a complete weighted graph where the nodes are represented by a random variables and weights of edges reflect interconnection between corresponding nodes (measure of similarity). Network structure in this model is a characteristic of some sub graphs of this graph. Identification of network structures from observations is an important problem in applied network analysis. Despite the growing number of publications on the subject there is a big gap in theoretical foundations of applied techniques. In the present paper we develop a new approach for identification of network structures based on the theory of multiple decision statistical procedures.  

Batsyn M.V.: On real-life vehicle routing problem
Abstract:   In this talk we present a real-life vehicle routing problem for delivering goods from a warehouse to stores of a big retail company. There are about 500 stores and 100 vehicles for one warehouse. This problem differs from the classical Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) by the following properties:

1. Each store has its limitations on vehicles which can serve it (Site Dependent VRP)

2. The company has a fleet of different vehicles with different capacities, fixed and variable costs (Heterogeneous Fleet VRP)

3. Vehicles have trailers (Truck and Trailer RP)

4. Each store can be served by two or more vehicles (VRP with Split Deliveries)

5. Each store has a soft time window defined by preffered time of delivery and a hard time window defined by its opening and closing times.

So instead of classical CVRPTW we have HFTTRPTWSD - Heterogeneous Fleet Truck and Trailer Routing Problem with Time Windows and Split Deliveries. We discuss how to model all these constraints and include it to exact and heuristic algorithms.

Nikolaev A.:  Maximum clique problem and its applications
Abstract:  People in social networks usually form cliques – groups in which every two persons interact with each other. The problem of finding the largest clique in a network is called the maximum clique problem. This problem can be exactly solved with a branch-and-bound algorithm in which the vertex coloring problem is used to compute upper bounds. In this talk we present a new approach to reduce the computational time spent on coloring in one of the recent branch-and-bound algorithms for the maximum clique problem. In this algorithm candidates to the maximum clique are colored in every search tree node. We suggest that the coloring computed in the parent node is reused for the child nodes when it does not lead to many new branches. So we reuse the same coloring only in the nodes for which the upper bound is greater than the current best solution only by a small value δ. The obtained increase in performance reaches 70% on benchmark instances.

Komosko L.F.: A fast greedy sequential heuristic for the vertex coloring problem
Abstract:  In the paper a fast greedy sequential heuristic for the vertex coloring problem is presented. Its high performance is based on two features. First, after coloring the current vertex we mark its color as forbidden for its neighbors. Second, we calculate a color for the current vertex and forbid it for its neighbors by means of bitwise operations with adjacency and color matrices. In the matrix of forbidden colors cij=0 if vertex j can be colored in color i and cij=1 if color i is forbidden for it. In comparison with the classical greedy heuristic the speedup reaches 28 times on DIMACS instances.

Utkina I.:  A branch-and-bound algorithm for the cell formation problem
Abstract:  In this talk we consider the cell formation problem with a fractional objective function. This problem consists in finding the optimal partitioning of machines and parts into groups (production cells, or shops), in order to minimize the inter-cell movement of parts from one cell to another and to maximize intra-cell processing operations. The problem belongs to the class of NP-hard combinatorial optimization problems. The number of feasible solutions of the problem is growing very rapidly with size (the number of machines and parts). In this talk we present a new branch-and-bound algorithm for the cell formation problem. We suggest a novel way of branching, and also an efficient upper bound, which allows us to reduce the search tree size significantly.