Informatica

In this paper we focus on a specific class of XML schema inference approaches – so-called heuristic approaches. Contrary to grammar-inferring approaches, their result does not belong to any specific class of grammars and, hence, we cannot say anything about their features from the point of view of theory of languages. However, the heuristic approaches still form a wider and more popular set of approaches due to natural and user-friendly strategies. We describe a general framework of the inference algorithms and we show how its particular phases can be further enhanced and optimized to get more reasonable and realistic output. The aim of the paper is (1) to provide a general overview of the heuristic inference process and existing approaches, (2) to sum up the improvements and optimizations we have proposed so far in our research group, and (3) to discuss possible extensions and open problems which need to be solved. Hence, it enables the reader to get acquainted with the field fast.

Given a set of objects with profits (any, even negative, numbers) assigned not only to separate objects but also to pairs of them, the unconstrained binary quadratic optimization problem consists in finding a subset of objects for which the overall profit is maximized. In this paper, an iterated tabu search algorithm for solving this problem is proposed. Computational results for problem instances of size up to 7000 variables (objects) are reported and comparisons with other up-to-date heuristic methods are provided.

The quadratic assignment problem (QAP) is one of the well‐known combinatorial optimization problems and is known for its various applications. In this paper, we propose a modified simulated annealing algorithm for the QAP – M‐SA‐QAP. The novelty of the proposed algorithm is an advanced formula of calculation of the initial and final temperatures, as well as an original cooling schedule with oscillation, i.e., periodical decreasing and increasing of the temperature. In addition, in order to improve the results obtained, the simulated annealing algorithm is combined with a tabu search approach based algorithm. We tested our algorithm on a number of instances from the library of the QAP instances – QAPLIB. The results obtained from the experiments show that the proposed algorithm appears to be superior to earlier versions of the simulated annealing for the QAP. The power of M‐SA‐QAP is also corroborated by the fact that the new best known solution was found for the one of the largest QAP instances – THO150.

Many heuristics, such as simulated annealing, genetic algorithms, greedy randomized adaptive search procedures are stochastic. In this paper, we propose a deterministic heuristic algorithm, which is applied to the quadratic assignment problem. We refer this algorithm to as intensive search algorithm (or briefly intensive search). We tested our algorithm on the various instances from the library of the QAP instances – QAPLIB. The results obtained from the experiments show that the proposed algorithm appears superior, in many cases, to the well-known algorithm – simulated annealing.

In this paper, we present two heuristics for solving the unconstrained quadratic 0–1 programming problem. First heuristic realizes the steepest ascent from the centre of the hypercube, while the second constructs a series of solutions and chooses the best of them. In order to evaluate their worst-case behaviour We define the performance ratio K which uses the objective function value at the reference point x=1/2. We show for both heuristics that K is bounded by 1 from above and this bound is sharp. Finally, we report on the results of a computational study with proposed and local improvement heuristics.