Optimization of ATM Telecommunication Networks

ATM network optimization problems defined as combinatorial optimization problems are considered. Several approximate algorithms for solving such problems are developed. Results of their comparison by experiments on a set of problems with random input data are presented.

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. Приведены результаты серии вычислительных экспериментов по решению известных задач коммивояжера и квадратичных задач о назначении.

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

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

Fractional Powers of Almost Non-Negative Operators

Mathematics Subject Classification: Primary 47A60, 47D06.

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

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

Classification of the Maximal Subsemigroups of the Semigroup of all Partial Order-Preserving Transformations

Илинка А. Димитрова, Цветелина Н. Младенова - Моноида P Tn от всички частични преобразования върху едно n-елементно множество относно операцията композиция на преобразования е изучаван в различни аспекти от редица автори. Едно частично преобразование α се нарича запазващо наредбата, ако от x ≤ y следва, че xα ≤ yα за всяко x, y от дефиниционното множество на α. Обект на разглеждане в настоящата работа е моноида P On състоящ се от всички частични запазващи наредбата преобразования. Очевидно P On е под-моноид на P Tn. Направена е пълна класификация на максималните подполугрупи на моноида P On. Доказано е, че съществуват пет различни вида максимални подполугрупи на разглеждания моноид. Броят на всички максимални подполугрупи на POn е точно 2^n + 2n − 2.

Evolution of Sets Systems and Homotopy Groups of Spheres

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