_____________________________________________

Invited Talks

_____________________________________________

Systems of Containers and Enumeration Problems
Alexander Sapozhenko
(Moscow State University, Russia)

Abstract: We discuss a technique (named "the container method") for enumeration problems. It was applied for obtaining upper bounds and asymptotically sharp estimates for the number of independent sets, codes, antichains in posets, sum-free sets, monotone boolean functions and so on. The container method works even the appropriate recurrent equalities are absent and the traditional generating function method is not applicable. The idea of the method is to reduce a considered enumeration problem to evaluating the number of independent sets in the appropriate graph. We give some examples of such reduction and a survey of upper bounds for the number of independent sets in graphs. The method is usually successful if considered graphs are almost regular and expanders.



Recent Advances in Multiobjective Optimization
Christos D. Zaroliagis
(University of Patras, Greece)



Evolutionary Testing Techniques
Joachim Wegener
(DaimlerChrysler AG, Research and Technology, Germany)

Abstract: The development and testing of software-based systems is an essential activity for the automotive industry. 50-70 software-based systems with different complexities and developed by various suppliers are installed in today’s premium vehicles, communicating with each other via different bus systems. The integration and testing of systems of this complexity is a very challenging task. The aim of testing is to detect faults in the systems under test and to convey confidence in the correct functioning of the systems if no faults are found during comprehensive testing. Faults not found in the different testing phases could have significant consequences that range from customer dissatisfaction to damage of physical property or, in safety relevant areas, even to the endangering of human lives. Therefore, the thorough testing of developed systems is essential. Evolutionary Testing tries to improve the effectiveness and efficiency of the testing process by transforming testing objectives into search problems, and applying evolutionary computation in order to solve them.



Self-Replication, Evolvability and Asynchronicity in Stochastic Worlds
Chrystopher L. Nehaniv
(University of Hertfordshire, UK)

Abstract: We consider temporal aspects of self-replication and evolvability -- in particular, the massively asynchronous parallel and distributed nature of living systems. Formal views of self-reproduction and time are surveyed, and a general asynchronization construction for automata networks is presented. Evolution and evolvability are distinguished, and the evolvability characteristics of natural and artificial examples are overviewed. Minimal implemented evolvable systems achieving (1) asynchronous self-replication and evolution, as well as (2) proto-cultural transmission and evolution, are presented and analyzed for evolvability. Developmental genetic regulatory networks (DGRNs) are suggested as a novel paradigm for massive asynchronous computation and evolvability. An appendix classifies modes of life (with different degrees of aliveness) for natural and artificial living systems and possible transitions between them.



The Complexity of Classical and Quantum Branching Programs: A Communication Complexity Approach
Farid Ablayev
(Kazan State University, Russia)

Abstract: We present a survey of the communication point of view for a complexity lower bounds proof technique for classical (deterministic, nondeterministic and randomized) and quantum models of branching programs.

_____________________________________________

Contributions

_____________________________________________

Some Heuristic Analysis of Local Search Algorithms for SAT Problems
Osamu Watanabe
(Tokyo Institute of Technology, Japan)

Abstract: By using heuristic analysis proposed in [WSA03], we investigate the dynamical behavior of greedy local search algorithms for satisfiability (SAT) problems. We observe that the difference between hard and easy instances is relatively small while there are enough places to be improved locally, and that the difference becomes crucial when all such places are processed. We also show that a tabu search type restriction could be useful for improving the efficiency of greedy local search algorithms.



Clustering in Stochastic Asynchronous Algorithms for~Distributed Simulations
Anatoli Manita and Francois Simonot
(Moscow State University, Russia / Universite Henri Poincare Nancy I, France)

Abstract: We consider a cascade model of $N$ different processors performing a distributed parallel simulation. The main goal of the study is to show that the long-time dynamics of the system have a cluster behaviour. To attack this problem we combine two methods: stochastic comparison and Foster--Lyapunov functions.



On the Construction of the Set of Irreducible Partial Covers
Mikhail Ju. Moshkov
(University of Silesia, Poland)

Abstract: In the paper a totally polynomial algorithm for construction of the set of irreducible partial covers for the major part of set cover problems is considered.



Polynomial Time Checking for Generation of Finite Distributions of Rational Probabilities
Roman Kolpakov
(Moscow State University, Russia)

Abstract: We study the generation of finite probabilistic distributions by discrete transformations. By discrete transformation of distributions we mean the distribution of a random variable which is a function of the values of independent random variables with initial distributions. We propose an algorithm which allows to determine in polynomial time whether a given distribution is generated by a given set of finite distributions of rational probabilities. Moreover, we describe all sets of finite distributions of rational probabilities which are closed under the considered generation. Among these sets we find all finitely generated sets. We also determine the structure of the lattice formed of these sets.



FPL Analysis for Adaptive Bandits
Jan Poland
(Hokkaido University, Japan)

Abstract: A main problem of "Follow the Perturbed Leader" strategies for online decision problems is that regret bounds are typically proven against oblivious adversary. In partial observation cases, it was not clear how to obtain performance guarantees against adaptive adversary, without worsening the bounds. We propose a conceptually simple argument to resolve this problem. Using this, a regret bound of $O(t^{\frac{2}{3}})$ for FPL in the adversarial multi-armed bandit problem is shown. This bound holds for the common FPL variant using only the observations from designated exploration rounds. Using all observations allows for the stronger bound of $O(\sqrt{t})$, matching the best bound known so far (and essentially the known lower bound) for adversarial bandits. Surprisingly, this variant does not even need explicit exploration, it is self-stabilizing. However the sampling probabilities have to be either externally provided or approximated to sufficient accuracy, using $O(t^2\log t)$ samples in each step.



On Improved Least Flexibility First Heuristics Superior for Packing and Stock Cutting Problems
Yu-Liang Wu and Chi-Kong Chan
(The Chinese University of Hong Kong, Hong Kong)

Abstract: Two dimensional cutting and packing problems have applications in many manufacturing and job allocation problems. In particular, in VLSI floor planning problems and stock cutting problems, many simulated annealing and genetic algorithms based methods have been proposed in the last ten years. These researches have mainly been focused on finding efficient data structures for representing packing results so the search space and processing time of the underlying search engine can be minimized. In this paper, we tackle the problem from a different approach. Instead of using stochastic searches, we introduce an effective deterministic optimization algorithm for packing and cutting. By combining an improved Least Flexibility First principle and a greedy search based evaluation routine, we can obtain very encouraging results: In stock cutting problems, our algorithm achieved over 99% average packing density for a series of public rectangle packing data sets, which is significantly better than the 96% packing density obtained by meta-heuristics (simulated annealing) based results while using much less CPU time; whereas in rectangle packing applying the well-known MCNC and GSRC benchmarks, we achieved the best (over 96%) packing density among all known published results packed by other methods. Our encouraging results seem to suggesting a new experimental direction in designing efficient deterministic heuristics for some kind of hard combinatorial problems.



Optimal Fuzzy CLOS Guidance Law Design Using Ant Colony Optimization
Hadi Nobahari and Seid H. Pourtakdoust
(Sharif University of Technology, Iran)

Abstract: The well-known ant colony optimization meta-heuristic is applied to design a new command to line-of-sight guidance law. In this regard, the lately developed continuous ant colony system is used to optimize the parameters of a pre-constructed fuzzy sliding mode controller. The performance of the resulting guidance law is evaluated at different engagement scenarios.



On Some Bounds on the Size of Branching Programs (A Survey)
Elizaveta A. Okol'nishnikova
(Sobolev Institute of Mathematics, Russia)

Abstract: Previously it was shown by the author that it is possible to reduce obtaining of lower bounds on the complexity of Boolean functions for branching programs without restriction to obtaining of lower bounds on the complexity of minorants of the considered function for branching programs with restriction on the number of occurrences of a variable in a path (read-$k$-times branching programs). Theorems that reduce the problem of nonlinear lower bounds on the complexity of Boolean functions for branching programs to the problem of lower bounds on the complexity of covering of the set of ``ones'' of a Boolean function by functions of the defined type or to the problem of obtaining the upper bounds on the number of "ones" of a Boolean function in $i$-faces of a cube of the defined dimension are presented. A survey of bounds obtained by this method is given.



Two Metaheuristics for Multiobjective Stochastic Combinatorial Optimization
Walter J. Gutjahr
(University of Vienna, Austria)

Abstract: Two general-purpose metaheuristic algorithms for solving multiobjective stochastic combinatorial optimization problems are introduced: SP-ACO (based on the Ant Colony Optimization paradigm) which combines the previously developed algorithms S-ACO and P-ACO, and SPSA, which extends Pareto Simulated Annealing to the stochastic case. Both approaches are tested on random instances of a TSP with time windows and stochastic service times.



Scales in time synchronization model
Vadim Malyshev and Anatoli Manita
(Moscow State University, Russia)

Abstract: There are two types i = 1; 2 of particles on the line R, with Ni particles of type i . Each particle of type i moves with constant velocity vi. Moreover, any particle of type i = 1; 2 jumps to any particle of type j = 1; 2 with rates $N ^(-1)_j a_(ij)$ . We find phase transitions in the clusterization (synchronization) behaviour of this system of particles on different time scales t = t(N) relative to N = N1 + N2.



New Computation Paradigm for Modular Exponentiation Using a Graph Model
Chi Seong Park, Mun-Kyu Lee and Dong Kyue Kim
(Pusan National University, Korea / Inha University, Korea)

Abstract: Modular exponentiation is to compute $x^E \bmod N$ for positive integers $x$, $E$, and $N$. It is an essential operation for various public-key cryptographic algorithms such as RSA, ElGamal and DSA, and it is crucial to develop fast modular exponentiation methods for efficient implementation of the above algorithms. To accelerate modular exponentiation, one can either speed up each multiplication or reduce the number of required multiplications. We focus on the latter.

In this paper, we propose a general model to describe the behavior of modular exponentiation in terms of a graph. First, we show that the problem of finding the minimum number of multiplications for a modular exponentiation is equivalent to finding a shortest path in its corresponding graph. The previously known exponentiation algorithms including the binary method, the $M$-ary method and the sliding window method can be represented as a specific instance of our model. Next, we present a general method to reduce the number of required multiplications by modifying the pre-computation table which is used for the sliding window method. According to our experimental results, the new method significantly reduces the number of multiplications, especially in the cases that the exponent $E$ has a high Hamming weight.



Dynamic Facility Location with Stochastic Demands
Martin Romauch and Richard F. Hartl
(University of Vienna, Austria)

Abstract: In this paper, a Stochastic Dynamic Facility Location Problem (SDFLP) is formulated. In the first part, an exact solution method based on stochastic dynamic programming is given. It is only usable for small instances. In the second part a Monte Carlo based method for solving larger instances is applied, which is derived from the Sample Average Approximation (SAA) method.



On the Properties of Asymptotic Probability for Random Boolean Expression Values in Binary Bases
Alexey D. Yashunsky
(Moscow State University, Russia)

Abstract: The present paper deals with the problem of analyzing the value of a random Boolean expression. The expressions are constructed of Boolean operations and constants chosen independently at random with given probabilities. The dependence between the expression value probability and the constants' probabilities is investigated for different sets of operations. The asymptotic behavior of this dependence is given by a probability function, explicitly obtained through analysis of generating functions for expressions. Special attention is given to the case of binary Boolean operations.

The paper demonstrates some probability function properties and their connection with the properties of Boolean operations used in random expressions.



Solving a Dynamic Cell Formation Problem with Machine Cost and Alternative Process Plan by Memetic Algorithms
Reza Tavakkoli-Moghaddam, Nima Safaei, and Masoud Babakhani
(University of Tehran, Iran / Iran University of Science and Technology, Iran)

Abstract: In this paper, we present a new model of a cell formation problem (CFP) for a multi-period planning horizon where the product mix and demand are different in each period, but they are deterministic. As a consequence, the formed cells in the current period may be not optimal for the next period. This evolution results from reformulation of part families, manufacturing cells, and reconfiguration of the CFP as required. Reconfiguration consists of reforming part families, machine groups, and machine relocations. The objective of the model is to determine the optimal number of cells while minimizing the machine amortization/relocation costs as well as the inter-cell movements in each period. In the proposed model, parts have alternative process plans, operation sequence, and produce as batch. The machine capacity is also limited and machine duplication is allowed. The proposed model for real-world instances cannot be solved optimally within a reasonable amount of computational time. Thus, we propose an efficient memetic algorithm (MA) with a simulated annealing-based local search engine for solving the proposed model. This model is solved optimally by the Lingo software then the optimal solution is compared with the MA implementation.



Eco-grammar Systems as Models for Parallel Evolutionary Algorithms
Adrian Horia Dediu and Maria Adela Grando
(Rovira i Virgili University, Spain)

Abstract: Evolutionary Algorithms (EAs), biological inspired searching techniques, represent a research domain where theoretical proofs are still missing. Due to the lack of theoretical foundations, an extensive experimental work developed many variations of the basic model. Remarkable tendencies such as variable control parameters or parallel populations try to overcome the stagnation observed at the end of evolutions.

We tried to study from theoretical point of view the possibility of modelling parallel EAs using Eco-grammar systems. We expect that our research opens a new perspective over EAs behavior and our framework can bring theoretical results that will lead to new recommendations for EAs architectures as well as for specific details requested by practical problems.