Informatica - Volume 27, issue 2

Authors: Žilinskas, Antanas | Zhigljavsky, Anatoly

Article Type: Research Article

Abstract: This is a survey of the main achievements in the methodology and theory of stochastic global optimization. It comprises two complimentary directions: global random search and the methodology based on the use of stochastic models about the objective function. The main attention is paid to theoretically substantiated methods and mathematical results proven in the last 25 years.

Keywords: global optimization, statistical models, extreme value statistics, random search, kriging

Citation: Informatica, vol. 27, no. 2, pp. 229-256, 2016

Authors: Karbauskaitė, Rasa | Dzemyda, Gintautas

Article Type: Research Article

Abstract: The estimation of intrinsic dimensionality of high-dimensional data still remains a challenging issue. Various approaches to interpret and estimate the intrinsic dimensionality are developed. Referring to the following two classifications of estimators of the intrinsic dimensionality – local/global estimators and projection techniques/geometric approaches – we focus on the fractal-based methods that are assigned to the global estimators and geometric approaches. The computational aspects of estimating the intrinsic dimensionality of high-dimensional data are the core issue in this paper. The advantages and disadvantages of the fractal-based methods are disclosed and applications of these methods are presented briefly.

Keywords: high-dimensional data, intrinsic dimensionality, topological dimension, fractal dimension, fractal-based methods, box-counting dimension, information dimension, correlation dimension, packing dimension

Citation: Informatica, vol. 27, no. 2, pp. 257-281, 2016

Authors: Kaminskas, Vytautas | Vidugirienė, Aušra

Article Type: Research Article

Abstract: A comparison of two nonlinear input-output models describing the relationship between human emotion (excitement, frustration and engagement/boredom) signals and a virtual 3D face feature (distance-between-eyes) is introduced in this paper. A method of least squares with projection to stability domain for the building of stable models with the least output prediction error is proposed. Validation was performed with seven volunteers, and three types of inputs. The results of the modelling showed relatively high prediction accuracy of excitement, frustration and engagement/boredom signals.

Keywords: 3D face, human emotions, Hammerstein-type model, parameter estimation, model validation

Citation: Informatica, vol. 27, no. 2, pp. 283-297, 2016

Authors: Brunato, Mauro | Battiti, Roberto

Article Type: Research Article

Abstract: We propose a heuristic global optimization technique which combines combinatorial and continuous local search. The combinatorial component, based on Reactive Search Optimization, generates a trajectory of binary strings describing search districts. Each district is evaluated by random sampling and by selective runs of continuous local search. A reactive prohibition mechanisms guarantees that the search is not stuck at locally optimal districts. The continuous stochastic local search is based on the Inertial Shaker method: candidate points are generated in an adaptive search box and a moving average of the steps filters out evaluation noise and high-frequency oscillations. The …overall subdivision of the input space in a tree of non-overlapping search districts is adaptive, with a finer subdivision in the more interesting input zones, potentially leading to lower local minima. Finally, a portfolio of independent CoRSO search streams (P-CoRSO ) is proposed to increase the robustness of the algorithm. An extensive experimental comparison with Genetic Algorithms and Particle Swarm demonstrates that CoRSO and P-CoRSO reach results which are fully competitive and in some cases significantly more robust. Show more

Keywords: global optimization, reactive search optimization, algorithm portfolios

Citation: Informatica, vol. 27, no. 2, pp. 299-322, 2016

Authors: Calvin, James M.

Article Type: Research Article

Abstract: This paper reviews the interplay between global optimization and probability models, concentrating on a class of deterministic optimization algorithms that are motivated by probability models for the objective function. Some complexity results are described for the univariate and multivariate cases.

Keywords: optimization, statistical models, convergence

Citation: Informatica, vol. 27, no. 2, pp. 323-334, 2016

Authors: Rudolph, Günter | Wessing, Simon

Article Type: Research Article

Abstract: We investigate the problem of detecting a point set’s deviation from uniformity in the unit hypercube. High uniformity is for example desirable in Monte Carlo methods for numerical integration, but also for obtaining a good worst-case bound in global optimization. In high dimensions, many points are required to get reliable results, so the point sets are preferably generated by fast methods such as quasirandom sequences. Unfortunately, assessing their uniformity often requires quadratic time. So, we present several numerical summary characteristics of point sets that can be computed in linear time. They do not measure uniformity directly, but by comparing them …to reference values for the uniform distribution, deviations from uniformity can be quickly detected. The necessary reference values are also derived here, if possible exactly, else approximately. Show more

Keywords: uniformity, measure, linear time, hypercube

Citation: Informatica, vol. 27, no. 2, pp. 335-349, 2016

Authors: Salmerón, Jose M.G. | Casado, Leocadio G. | Hendrix, Eligius M.T.

Article Type: Research Article

Abstract: The iterative bisection of the longest edge of the unit simplex generates a binary tree, where the specific shape depends on the chosen longest edges to be bisected. In global optimization, the use of various distance norms may be advantageous for bounding purposes. The question dealt with in this paper is how the size of a binary tree generated by the refinement process depends on heuristics for longest edge selection when various distance norms are used. We focus on the minimum size of the tree that can be reached, how selection criteria may reduce the size of the tree compared …to selecting the first edge, whether a predefined grid is covered and how unique are the selection criteria. The exact numerical values are provided for the unit simplex in 4 and 5-dimensional space. Show more

Keywords: simplex, Branch-and-Bound, longest edge bisection, norm, selection heuristics

Citation: Informatica, vol. 27, no. 2, pp. 351-366, 2016

Authors: Strekalovskiy, Alexander | Musatova, Elena

Article Type: Research Article

Abstract: In the paper we address the classical problem of solving one equation given by (d.c.) function represented by the difference of two convex functions. This problem is initiated by the optimization problems with constraints in the form of inequalities and/or equalities given by d.c. functions when one needs to descent from an unfeasible point to the boundary of a constraint improving, at the same time, the value of the objective function. We propose a new numerical procedure which allows to do this. Further, for the developed algorithm we provide the convergence results and numerical results of computational testing which look …rather promising and competitive. Show more

Keywords: d.c. functions, nonlinear equation, numerical method, nonconvex optimization

Citation: Informatica, vol. 27, no. 2, pp. 367-386, 2016

Authors: Van Dijk, Diana | Hendrix, Eligius M.T.

Article Type: Research Article

Abstract: Operators of underground water supply networks are challenged with pipe replacement decisions, because pipes are subject to increased failure rates as they age and financial resources are often limited. We study the optimal replacement time and optimal number of pipe replacements such that the expected failure cost and replacement cost are minimized, while satisfying a budget constraint and incorporating uncoordinated and coordinated replacement. Results show that coordinated replacement is economically preferred to uncoordinated replacement. It depends on the size of the budget whether the increase in the number of pipe replacements is sufficient to reduce the total expected failure cost.

Keywords: water supply network, pipe replacement, pipe failure, coordinated replacement

Citation: Informatica, vol. 27, no. 2, pp. 387-403, 2016

Authors: Fan, Wenjuan | Pei, Jun | Ding, Shuai | Pardalos, Panos M. | Kong, Min | Yang, Shanlin

Article Type: Research Article

Abstract: In this paper, we propose a novel trust inference framework in the web-based scenarios which are assumed to have a Web of Trust pre-established, and take the contexts of the trust relationships into account when inferring the recommendation trust. For alleviating the problem of sparse matrix in the Web of Trust, we also incorporate the users’ profile and relationship information on the associated social networks into the framework. Based on the Web of Trust established in the discussed web-based scenario (i.e. epinions.com in this paper), and the social relationship information in the associated social networks, the users are classified into …four classes. Then different information is used to infer the users’ recommendation trust value based on the classifications. The simulation experiments show that our approach has good coverage of inferred trust values, and the accurate rate of the predicted trust relationship is higher than the traditional PCC (Pearson Correlation Co-efficiency). According to the computation results of adjusted parameters, it can be concluded that the threshold which is used to filter the inferred trust values can be removed, i.e. all the inferred trust values should be kept. Show more

Keywords: trust relationship inference, Web of Trust, recommendation trust, social network

Citation: Informatica, vol. 27, no. 2, pp. 405-432, 2016

Authors: He, Xueqi | Hartman, Joseph C. | Pardalos, Panos M.

Article Type: Research Article

Abstract: We propose a new hybrid approach to solve the unbounded integer knapsack problem (UKP), where valid inequalities are generated based on intermediate solutions of an equivalent forward dynamic programming formulation. These inequalities help tighten the initial LP relaxation of the UKP, and therefore improve the overall computational efficiency. We also extended this approach to solve the multi-dimensional unbounded knapsack problem (d-UKP). Computational results demonstrate the effectiveness of our approach on both problems.

Keywords: integer programming, dynamic programming, unbounded knapsack problem, valid inequalities

Citation: Informatica, vol. 27, no. 2, pp. 433-450, 2016

Authors: Lančinskas, Algirdas | Fernández, Pascual | Pelegrín, Blas | Žilinskas, Julius

Article Type: Research Article

Abstract: A new heuristic algorithm for solution of bi-objective discrete competitive facility location problems is developed and experimentally investigated by solving different instances of a facility location problem for firm expansion. The proposed algorithm is based on ranking of candidate locations for the new facilities, where rank values are dynamically adjusted with respect to behaviour of the algorithm. Results of the experimental investigation show that the proposed algorithm is suitable for the latter facility location problems and provides good results in sense of accuracy of the approximation of the true Pareto front.

Keywords: facility location, multi-objective optimization, heuristic algorithms

Citation: Informatica, vol. 27, no. 2, pp. 451-462, 2016

Authors: San Segundo, Pablo | Nikolaev, Alexey | Batsyn, Mikhail | Pardalos, Panos M.

Article Type: Research Article

Abstract: This paper improves an infra-chromatic bound which is used by the exact branch-and-bound maximum clique solver BBMCX (San Segundo et al., 2015) as an upper bound on the clique number for every subproblem. The infra-chromatic bound looks for triplets of colour subsets which cannot contain a 3-clique. As a result, it is tighter than the bound obtained by widely used approximate-colouring algorithms because it can be lower than the chromatic number. The reported results show that our algorithm with the new bound significantly outperforms the state-of-the-art algorithms in a number of structured and uniform random graphs.

Keywords: maximum clique, approximate-colouring, branch-and-bound, combinatorial optimization, exact search, maximum satisfiability

Citation: Informatica, vol. 27, no. 2, pp. 463-487, 2016