Informatica

Wireless Mesh Networks (WMNs) have become an important networking infrastructure due to their low cost for providing broadband connectivity. Issues for achieving the network connectivity and user coverage are related to the node placement problem. Several optimization problems are showing their usefulness to the efficient design of WMNs. These problems are related to optimizing network connectivity, user coverage and stability. In this paper, we formulate the optimization problems using a multi-objective optimization model. For the mesh router nodes placement, the bi-objective optimization problem is obtained consisting in the maximization of the size of the giant component in the mesh routers network (for measuring network connectivity) and that of user coverage. We evaluate the performance of WMN-GA system for node placement problem in WMNs. For evaluation, we consider Normal, Exponential and Weibull Distribution of mesh clients and different selection and mutation operators. The population size is considered 64 and the number of generation 200. The simulation results show that WMN-GA system performs better for Single Mutation, Linear Ranking selection and Normal distribution of mesh clients.

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.

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.

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.

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.

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.

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.

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.

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.

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.