Informatica

In this paper we present an algorithm for generating quadratic assignment problem (QAP) instances with known provably optimal solution. The flow matrix of such instances is constructed from the matrices corresponding to special graphs whose size may reach the dimension of the problem. In this respect, the algorithm generalizes some existing algorithms based on the iterative selection of triangles only. The set of instances which can be produced by the algorithm is NP-hard. Using multi-start descent heuristic for the QAP, we compare experimentally such test cases against those created by several existing generators and against Nugent-type problems from the QAPLIB as well.

In this paper we are concerned with global optimization, which can be defined as the problem of finding points on a bounded subset of R^m, in which some real-valued function f(x) assumes its optimal value. We consider here a global optimization algorithm. We present a stochastic approach, which is based on the simulated annealing algorithm. The optimization function f(x) here is discrete and with noise.

In this paper we define a class of edge-weighted graphs having nonnegatively valued bisections. We show experimentally that complete such graphs with more than three vertices and also some special graphs with only positive edges can be applied to improve the existing lower bounds for a version of the quadratic assignment problem, namely with a matrix composed of rectilinear distances between points in the Euclidean space.

The problem is to discover knowledge in the correlation matrix of parameters (variables) about their groups. Results that deal with deterministic approaches of parameter clustering on the basis of their correlation matrix are reviewed and extended. The conclusions on both theoretical and experimental investigations of various deterministic strategies in solving the problem of extremal parameter grouping are presented. The possibility of finding the optimal number of clusters is considered. The transformation of a general clustering problem into the clustering on the sphere and the relation between clustering of parameters on the basis of their correlation matrix and clustering of vectors (objects, cases) of an n-dimensional unit sphere are analysed.

In this paper we deal with the problem of extremal parameter grouping. The problem formulation, the algorithms of parameter grouping and the fields of implementation are presented. The deterministic algorithms of extremal parameter grouping often find the local maximum of the functional, characterizing the quality of a partition. The problem has been formulated as a problem of combinatorial optimization and attempted to be solved using the simulated annealing strategy. The algorithms, realizing such a strategy and devoted to the solving of the problem concerned, are proposed and investigated.