Journal:Informatica
Volume 26, Issue 1 (2015), pp. 17–32
Abstract
Abstract
In several areas like Global Optimization using branch-and-bound methods, the unit n-simplex is refined by bisecting the longest edge such that a binary search tree appears. This process generates simplices belonging to different shape classes. Having less simplex shapes facilitates the prediction of the further workload from a node in the binary tree, because the same shape leads to the same sub-tree. Irregular sub-simplices generated in the refinement process may have more than one longest edge when . The question is how to choose the longest edge to be bisected such that the number of shape classes is as small as possible. We develop a Branch-and-Bound (B&B) algorithm to find the minimum number of classes in the refinement process. The developed B&B algorithm provides a minimum number of eight classes for a regular 3-simplex. Due to the high computational cost of solving this combinatorial problem, future research focuses on using high performance computing to derive the minimum number of shapes in higher dimensions.
Journal:Informatica
Volume 11, Issue 3 (2000), pp. 281–296
Abstract
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.
Journal:Informatica
Volume 8, Issue 4 (1997), pp. 465–476
Abstract
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.
Journal:Informatica
Volume 8, Issue 3 (1997), pp. 377–400
Abstract
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.
Journal:Informatica
Volume 1, Issue 1 (1990), pp. 20–39
Abstract
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.