Differential Balanced Trees and (0,1) Matrices

* The research was supported by INTAS 00-397 and 00-626 Projects.

Implementation of a Heuristic Method of Decomposition of Partial Boolean Functions

An original heuristic algorithm of sequential two-block decomposition of partial Boolean functions is researched. The key combinatorial task is considered: finding of suitable partition on the set of arguments, i. e. such one, on which the function is separable. The search for suitable partition is essentially accelerated by preliminary detection of its traces. Within the framework of the experimental system the efficiency of the algorithm is evaluated, the boundaries of its practical application are determined.

An Adaptive Genetic Algorithm with Dynamic Population Size for Optimizing Join Queries

The problem of finding the optimal join ordering executing a query to a relational database management system is a combinatorial optimization problem, which makes deterministic exhaustive solution search unacceptable for queries with a great number of joined relations. In this work an adaptive genetic algorithm with dynamic population size is proposed for optimizing large join queries. The performance of the algorithm is compared with that of several classical non-deterministic optimization algorithms. Experiments have been performed optimizing several random queries against a randomly generated data dictionary. The proposed adaptive genetic algorithm with probabilistic selection operator outperforms in a number of test runs the canonical genetic algorithm with Elitist selection as well as two common random search strategies and proves to be a viable alternative to existing non-deterministic optimization approaches.

Комбинирование Алгоритмов Оптимизации Муравьиными Колониями и Н-Метода

* Исследования проведены при частичной поддержке INTAS (проект 06-1000017-8909)

Использование Алгоритма Ускоренного Вероятностного Моделирования в Схеме Табу-Поиска

Рассматривается метаэвристический метод комбинаторной оптимизации, основанный на использовании алгоритмов табу-поиска и ускоренного вероятностного моделирования. Излагается общая вычислительная схема предложенного метода, названного алгоритмом GS-tabu. Приведены результаты серии вычислительных экспериментов по решению известных задач коммивояжера и квадратичных задач о назначении.

О Классификации Приближенных Методов Комбинаторной Оптимизации

В работе предлагается классификация приближенных методов комбинаторной оптимизации, которая обобщает и дополняет существующие подходы.

A Metaheuristic Approach to Solving the Generalized Vertex Cover Problem

AMS Subj. Classification: 90C27, 05C85, 90C59

Solving the Task Assignment Problem with a Variable Neighborhood Search

In this paper a variable neighborhood search (VNS) approach for the task assignment problem (TAP) is considered. An appropriate neighborhood scheme along with a shaking operator and local search procedure are constructed specifically for this problem. The computational results are presented for the instances from the literature, and compared to optimal solutions obtained by the CPLEX solver and heuristic solutions generated by the genetic algorithm. It can be seen that the proposed VNS approach reaches all optimal solutions in a quite short amount of computational time.

An Electromagnetism Metaheuristic for the Uncapacitated Multiple Allocation Hub Location Problem

In this article, the results achieved by applying an electromagnetism (EM) inspired metaheuristic to the uncapacitated multiple allocation hub location problem (UMAHLP) are discussed. An appropriate objective function which natively conform with the problem, 1-swap local search and scaling technique conduce to good overall performance.Computational tests demonstrate the reliability of this method, since the EM-inspired metaheuristic reaches all optimal/best known solutions for UMAHLP, except one, in a reasonable time.

A Method for Classification of Doubly Resolvable Designs and Its Application

This article presents the principal results of the Ph.D. thesis Investigation and classification of doubly resolvable designs by Stela Zhelezova (Institute of Mathematics and Informatics, BAS), successfully defended at the Specialized Academic Council for Informatics and Mathematical Modeling on 22 February 2010.

Self-Avoiding Walks in the Plane

Румен Руменов Данговски, Калина Христова Петрова - Разглеждаме броя на несамопресичащите се разходки с фиксирана дължина върху целочислената решетка. Завършваме анализа върху случая за лента, с дължина едно. Чрез комбинаторни аргументи получаваме точна формула за броя на разходките върху лента, ограничена отляво и отдясно. Формулата я изследваме и асимптотично.

Evolution of Sets Systems and Homotopy Groups of Spheres

Симеон Т. Стефанов, Велика И. Драгиева - В работата е изследвана еволюцията на системи от множества върху n-мерната евклидова сфера S^n. Установена е връзката на такива системи с хомотопичните групи на сферите. Получени са някои комбинаторни приложения за многостени.

A Variable Neighborhood Search Approach for Solving the Maximum Set Splitting Problem

This paper presents a Variable neighbourhood search (VNS) approach for solving the Maximum Set Splitting Problem (MSSP). The algorithm forms a system of neighborhoods based on changing the component for an increasing number of elements. An efficient local search procedure swaps the components of pairs of elements and yields a relatively short running time. Numerical experiments are performed on the instances known in the literature: minimum hitting set and Steiner triple systems. Computational results show that the proposed VNS achieves all optimal or best known solutions in short times. The experiments indicate that the VNS compares favorably with other methods previously used for solving the MSSP. ACM Computing Classification System (1998): I.2.8.

Orthogonal Resolutions and Latin Squares

Resolutions which are orthogonal to at least one other resolution (RORs) and sets of m mutually orthogonal resolutions (m-MORs) of 2-(v, k, λ) designs are considered. A dependence of the number of nonisomorphic RORs and m-MORs of multiple designs on the number of inequivalent sets of v/k − 1 mutually orthogonal latin squares (MOLS) of size m is obtained. ACM Computing Classification System (1998): G.2.1.

Test, Teachers, Quorum (Pure Populations)

The “trial and error” method is fundamental for Master Minddecision algorithms. On the basis of Master Mind games and strategies weconsider some data mining methods for tests using students as teachers.Voting, twins, opposite, simulate and observer methods are investigated.For a pure data base these combinatorial algorithms are faster then manyAI and Master Mind methods. The complexities of these algorithms arecompared with basic combinatorial methods in AI. ACM Computing Classification System (1998): F.3.2, G.2.1, H.2.1, H.2.8, I.2.6.