Informatica

This paper improves an infra-chromatic bound which is used by the exact branch-and-bound maximum clique solver BBMCX (San Segundo et al., 2015) as an upper bound on the clique number for every subproblem. The infra-chromatic bound looks for triplets of colour subsets which cannot contain a 3-clique. As a result, it is tighter than the bound obtained by widely used approximate-colouring algorithms because it can be lower than the chromatic number. The reported results show that our algorithm with the new bound significantly outperforms the state-of-the-art algorithms in a number of structured and uniform random graphs.

The iterative bisection of the longest edge of the unit simplex generates a binary tree, where the specific shape depends on the chosen longest edges to be bisected. In global optimization, the use of various distance norms may be advantageous for bounding purposes. The question dealt with in this paper is how the size of a binary tree generated by the refinement process depends on heuristics for longest edge selection when various distance norms are used. We focus on the minimum size of the tree that can be reached, how selection criteria may reduce the size of the tree compared to selecting the first edge, whether a predefined grid is covered and how unique are the selection criteria. The exact numerical values are provided for the unit simplex in 4 and 5-dimensional space.

The problem of parameter clustering on the basis of their correlation matrix is considered. The convergence in probability of parameter clustering based on the simulated annealing is investigated theoretically.

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.

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.