This article proposes a novel constructive heuristic approach, Hyper-GRASP, that integrates the hypervolume indicator and GRASP principles to solve multiobjective combinatorial optimization problems. The approach constructs solutions iteratively by generating and evaluating candidate extensions of the current partial solution, guided by an optimistic bound on the hypervolume contribution of the future complete solution. The most promising extension is selected from a pool according to a parameter α, which balances greediness and exploration during the solution construction phase. Throughout the procedure, only feasible and nondominated solutions are retained. The proposed approach is tested on the multiobjective knapsack problem and the biobjective minimum spanning tree problem to assess its performance. The results show that the best-performing Hyper-GRASP variant effectively approximates the Pareto front across various instances. Moreover, it can also outperform state-of-the-art exact algorithms for the multiobjective knapsack problem as the problem size increases and across various time budgets.

Given a simple undirected graph G, the Multiobjective Subgraph (MOS) problem aims to find a subgraph in G that maximizes the number of edges while minimizing the number of vertices. Addressing the MOS problem allows to solve the related Multiobjective Quasi-clique problem, which seeks a quasi-clique with maximum density and number of vertices and has many real-life applications. These problems have only been addressed using exact methods, which can be computationally intensive due to their NP-hard nature. In this paper, we introduce a heuristic method for solving the MOS problem. We show that a subset of optimal MOS subgraphs exhibits a nestedness property, meaning they satisfy an inclusion-wise relation. We explore this property to develop a path-relinking-based heuristic, where subgraphs from this subset serve as starting and ending points of a path to find new high-quality subgraphs. Additionally, we derive an upper bound on the number of edges for MOS subgraphs, which is used to evaluate the quality of the subgraphs generated by our heuristic. Experimental results on synthetic and real-life sparse graphs indicate that our heuristic produces high-quality subgraphs, with an average error of 2.3 edges compared to the exact method, while spending only 6.2% of its runtime.

No abstract available.

Experimental research is an essential component in the field of evolutionary computation (EC). The scientific method requires that empirical results are reproducible. Reproducibility of experiments also helps later researchers build upon the work of previous researchers. Interest in improving reproducibility in computer science and other empirical sciences has grown in recent years and there is a growing number of works analyzing current and best practices, obstacles and guidelines, effectiveness of journal policies, etc. Reproducibility issues in the context of EC have been a topic of discussion for a long time in the context of best practices for empirical research, but there are few studies analyzing reproducibility in EC research, and reproducibility studies themselves are extremely rare. There is room for improvement to attain the minimum standards for reproducibility encouraged in other scientific fields. Reproducibility goes beyond making implementation of algorithms publicly available. Challenges for reproducibility in EC research arise from the stochastic nature of the algorithms and, sometimes, the problems, which require multiple runs to analyze expected behavior and variance; sensitivity of the results to the computational environment, parameter settings, or implementation details; and the generalizability of conclusions to different instances of the same or related problems.This special issue of Evolutionary Computation on reproducibility features three exceptional papers that highlight different aspects of reproducibility and how to achieve it in practice.In “Using Decomposed Error for Reproducing Implicit Understanding of Algorithms” (10.1162/evco_a_00321), Caitlin A. Owen, Grant Dick, and Peter A. Whigham propose an error decomposition framework to improve the reproducibility of experiments in evolutionary machine learning. This framework takes into account information about bias, variance due to internal algorithmic choices, and variance due to training data, from multiple runs. The authors examine the behavior of three evolutionary machine learning approaches with this framework, which provides a fine-grained analysis on the decomposition of errors, and allow them to pinpoint mismatched expectations about algorithm behavior.In “The Importance of Being Constrained: Dealing with Infeasible Solutions in Differential Evolution and Beyond” (10.1162/evco_a_00333), Anna V. Kononova, Diederick Vermetten, Fabio Caraffini, Madalina-A. Mitran, and Daniela Zaharie argue that the strategy for dealing with infeasible solutions in constrained optimization problems has a significant impact on the reproducibility of experiments in heuristic optimization, and this impact grows with the dimensionality of the problem.In “A Practical Methodology for Reproducible Experimentation: An Application to the Double-Row Facility Layout Problem” (10.1162/evco_a_00317), Raúl Martín-Santamaría, Sergio Cavero, Alberto Herrán, Abraham Duarte, and J. Manuel Colmenar provide a methodology, and the software implementing it, for carrying out experiments with stochastic optimization methods. They illustrate the methodology on the double-row facility layout problem, reproducing previous results and ensuring that their own new results are fully reproducible.We believe that there is an ongoing cultural shift within computer science in general and within EC in particular, with both reviewers and funding agencies expecting and rewarding reproducibility efforts. The submission guidelines of Evolutionary Computation encourage authors to “ensure reproducibility.” Other journals have adopted “reproducibility boards” and “reproducibility badges.” Some conferences and journals have already gone a step further and require that experiments are reproducible by reviewers before publication. As a result of these efforts, we expect that the good practice standards in EC regarding reproducibility will improve in the next decade.

Building upon the exact methods presented in our earlier work [J. Complexity, 2022], we introduce a heuristic approach for the star discrepancy subset selection problem. The heuristic gradually improves the current-best subset by replacing one of its elements at a time. While the heuristic does not necessarily return an optimal solution, we obtain very promising results for all tested dimensions. For example, for moderate sizes 30≤n≤240, we obtain point sets in dimension 6 with L∞ star discrepancy up to 35% better than that of the first n points of the Sobol' sequence. Our heuristic works in all dimensions, the main limitation being the precision of the discrepancy calculation algorithms. We provide a comparison with a recent energy functional introduced by Steinerberger [J. Complexity, 2019], showing that our heuristic performs better on all tested instances. Finally, our results and complementary experiments also give further empirical information on inverse star discrepancy conjectures.

The L∞ star discrepancy is a measure for the regularity of a finite set of points taken from [0, 1)d. Low discrepancy point sets are highly relevant for Quasi-Monte Carlo methods in numerical integration and several other applications. Unfortunately, computing the L∞ star discrepancy of a given point set is known to be a hard problem, with the best exact algorithms falling short for even moderate dimensions around 8. However, despite the difficulty of finding the global maximum that defines the L∞ star discrepancy of the set, local evaluations at selected points are inexpensive. This makes the problem tractable by black-box optimization approaches.

Fog computing emerged to ease the load of resource-constrained devices on the Internet. It provides services and computational devices closer to the users to reduce latency and improve quality of service. For this paradigm to be used in practice, certain optimization tasks need to be solved: to allocate the resources that are available to the users and to perform service placement and routing on the communications executed by them. In this paper, we develop a framework that allows users to offload services and perform communications in a Fog environment. For this, we propose a Mixed Integer Linear Programming (MILP) formulation and a heuristic to map Virtual Networks (VNs) into the substrate network, maximizing fairness of energy and bandwidth usage on the system. Moreover, we propose a MILP formulation and a heuristic to route and offload services of an application in each VN, minimizing energy and latency. We extend both heuristics to be used in dynamic settings with increasing number of users and applications and consider a reconfiguration approach when nodes or links fail in the substrate network. To evaluate the proposed approaches, we use the YAFS simulator and several instances of VNs and services with both randomly generated values and referenced parameters. We observed that the heuristics are able to obtain results close to the optimal value in most settings.

Motivated by applications in instance selection, we introduce the star discrepancy subset selection problem, which consists of finding a subset of m out of n points that minimizes the star discrepancy. First, we show that this problem is NP-hard. Then, we introduce a mixed integer linear formulation (MILP) and a combinatorial branch-and-bound (BB) algorithm for the star discrepancy subset selection problem and we evaluate both approaches against random subset selection and a greedy construction on different use-cases in dimension two and three. Our results show that the MILP and BB are efficient in dimension two for large and small m/n ratio, respectively, and for not too large n. However, the performance of both approaches decays strongly for larger dimensions and set sizes. As a side effect of our empirical comparisons we obtain point sets of discrepancy values that are much smaller than those of common low-discrepancy sequences, random point sets, and of Latin Hypercube Sampling. This suggests that subset selection could be an interesting approach for generating point sets of small discrepancy value.

In this article, we propose an indicator-based branch and bound (I-BB) approach for multi-objective combinatorial optimization that uses a best-first search strategy. In particular, assuming maximizing objectives, the next node to be processed is chosen with respect to the quality of its upper bound. This quality is given by a binary quality indicator, such as the binary hypervolume or the ε-indicator, with respect to the archive of solutions maintained by the branch and bound algorithm. Although the I-BB will eventually identify the efficient set, we are particularly interested in analyzing its anytime behavior as a heuristic. Our experimental results, conducted on a multi-objective knapsack problem with 2, 3, 5, and 7 objectives, indicate that the I-BB can often outperform the naive depth-first and breadth-first search strategies, both in terms of runtime and anytime performance. The improvement is especially significant when the branching order for the decision variables is random, which suggests that the I-BB is particularly relevant when more favorable (problem-dependent) branching orders are not available.

Experimental studies are prevalent in Evolutionary Computation (EC), and concerns about the reproducibility and replicability of such studies have increased in recent times, reflecting similar concerns in other scientific fields. In this article, we discuss, within the context of EC, the different types of reproducibility and suggest a classification that refines the badge system of the Association of Computing Machinery (ACM) adopted by ACM Transactions on Evolutionary Learning and Optimization (https://dlnext.acm.org/journal/telo). We identify cultural and technical obstacles to reproducibility in the EC field. Finally, we provide guidelines and suggest tools that may help to overcome some of these reproducibility obstacles.

Anytime algorithms for optimization problems are of particular interest since they allow to trade off execution time with result quality. However, the selection of the best anytime algorithm for a given problem instance has been focused on a particular budget for execution time or particular target result quality. Moreover, it is often assumed that these anytime preferences are known when developing or training the algorithm selection methodology. In this work, we study the algorithm selection problem in a context where the decision maker's anytime preferences are defined by a general utility function, and only known at the time of selection. To this end, we first examine how to measure the performance of an anytime algorithm with respect to this utility function. Then, we discuss approaches for the development of selection methodologies that receive a utility function as an argument at the time of selection. Then, to illustrate one of the discussed approaches, we present a preliminary study on the selection between an exact and a heuristic algorithm for a bi-objective knapsack problem. The results show that the proposed methodology has an accuracy greater than 96% in the selected scenarios, but we identify room for improvement.

With the increase of small devices with networking capabilities, Fog Computing emerged as a paradigm to improve Quality of Service. Yet, since these devices are resource constrained, there is a need to offload computational services and to maintain connectivity while moving. In this work, we aim to improve users experience by creating a new path after mobility occurs and the connection to their resources cannot be used anymore. We propose a MILP formulation and a heuristic to minimize energy consumption and latency to obtain a tradeoff solution between these objectives. These approaches find a single path composed by migration of resources to a new device and data communication path to that device. We compare both approaches, formulation and heuristic, and a baseline first-fit approach on randomly generated topologies, resources and users. The results show that the heuristic obtains solutions that are closer to the optimal, while rejecting less users and using the same number of hops than the baseline.

Due to the large increase of Internet of Things (IoT) devices in the last years, the cloud has been proved unsuitable to deal with the high demand of requests generated by them. To deal with this, fog computing was proposed in order to provide closer computing services in a distributed manner, acting as a middle layer between IoT devices and the cloud. However, these devices have low energy and low computational power. Therefore, strategies to distribute requested services, bundled in a set of applications, are of particular interest. Furthermore, these applications have deadlines that may be short, which have to be met. Hence, models and algorithms are needed to place the requested services in order to meet the deadlines while using the fog as distributed as possible. In this paper, we present a Mixed Integer Linear Programming (MILP) formulation with two main objectives: maximize the fog usage and maximize the fairness throughout the system (fog and cloud). We also propose an heuristic that obtains approximate solutions as fast as possible. We compare both approaches using a set of randomly generated applications composed by different deadlines and services.

Local search algorithms have shown good performance for several multi-objective combinatorial optimization problems. These approaches naturally stop at a local optimal set (LO-set) under given definitions of neighborhood and preference relation among subsets of solutions, such as set-based dominance relation, hypervolume or epsilon indicator. It is an open question how LO-sets under different set preference relations relate to each other. This paper reports an in-depth experimental analysis on multi-objective nk-landscapes. Our results reveal that, whatever the preference relation, the number of LO-sets typically increases with the problem non-linearity, and decreases with the number of objectives. We observe that strict LO-sets of bounded cardinality under set-dominance are LO-sets under both epsilon and hypervolume, and that LO-sets under hyper-volume are LO-sets under set-dominance, whereas LO-sets under epsilon are not. Nonetheless, LO-sets under set-dominance are more similar to LO-sets under epsilon than under hypervolume. These findings have important implications for multi-objective local search. For instance, a dominance-based approach with bounded archive gets more easily trapped and might experience difficulty to identify an LO-set under epsilon or hypervolume. On the contrary, a hypervolume-based approach is expected to perform more steps before converging to better approximations.

Given a nondominated point set [Formula: see text] of size [Formula: see text] and a suitable reference point [Formula: see text], the Hypervolume Subset Selection Problem (HSSP) consists of finding a subset of size [Formula: see text] that maximizes the hypervolume indicator. It arises in connection with multiobjective selection and archiving strategies, as well as Pareto-front approximation postprocessing for visualization and/or interaction with a decision maker. Efficient algorithms to solve the HSSP are available only for the 2-dimensional case, achieving a time complexity of [Formula: see text]. In contrast, the best upper bound available for [Formula: see text] is [Formula: see text]. Since the hypervolume indicator is a monotone submodular function, the HSSP can be approximated to a factor of [Formula: see text] using a greedy strategy. In this article, greedy [Formula: see text]-time algorithms for the HSSP in 2 and 3 dimensions are proposed, matching the complexity of current exact algorithms for the 2-dimensional case, and considerably improving upon recent complexity results for this approximation problem.

The hypervolume subset selection problem consists of finding a subset, with a given cardinality k, of a set of nondominated points that maximizes the hypervolume indicator. This problem arises in selection procedures of evolutionary algorithms for multiobjective optimization, for which practically efficient algorithms are required. In this article, two new formulations are provided for the two-dimensional variant of this problem. The first is a (linear) integer programming formulation that can be solved by solving its linear programming relaxation. The second formulation is a k-link shortest path formulation on a special digraph with the Monge property that can be solved by dynamic programming in [Formula: see text] time. This improves upon the result of [Formula: see text] in Bader ( 2009 ), and slightly improves upon the result of [Formula: see text] in Bringmann et al. ( 2014b ), which was developed independently from this work using different techniques. Numerical results are shown for several values of n and k.

Unemployment has been a major concern in recent years. This is particular true for young people and in the case of Portugal for youngsters with a Higher Education degree. In this paper we describe the program “Acertar o Rumo”, a two years program to reconvert unemployed graduates in Engineering and Exact and Natural Science in experienced Java programmers. Particularly, we focus on the Programming courses of the program, where the two main programming paradigms, the procedural and the object-oriented, as well as principles and technologies for developing enterprise systems were taught. We describe the main methodologies and approaches followed and report the very positive results obtained with the first edition of the program till now. We finish the paper by proposing some recommendations and improvements for further editions.

Given a non-dominated point set X ⊂ Rd of size n and a suitable reference point r ∈ Rd, the Hypervolume Subset Selection Problem (HSSP) consists of finding a subset of size k > n that maximizes the hypervolume indicator. It arises in connection with multiobjective selection and archiving strategies, as well as Pareto-front approximation post-processing for visualization and/or interaction with a decision maker. Efficient algorithms to solve the HSSP are available only for the 2-dimensional case, achieving a time complexity of O(n(k+log n)). In contrast, the best upper bound available for d>2 is O(nd/2 log n + nn-k). Since the hypervolume indicator is a monotone submodular function, the HSSP can be approximated to a factor of (1-1/e) using a greedy strategy. Such a greedy algorithm for the 3-dimensional HSSP is proposed in this paper. The time complexity of the algorithm is shown to be O(n2), which considerably improves upon recent complexity results for this approximation problem.

MOTIVATION: In this article, we consider the bicriteria pairwise sequence alignment problem and propose extensions of dynamic programming algorithms for several problem variants with a novel pruning technique that efficiently reduces the number of states to be processed. Moreover, we present a method for the construction of phylogenetic trees based on this bicriteria framework. Two exemplary cases are discussed. RESULTS: Numerical results on a real dataset show that this approach is very fast in practice. The pruning technique saves up to 90% in memory usage and 80% in CPU time. Based on this method, phylogenetic trees are constructed from real-life data. In addition of providing complementary information, some of these trees match those obtained by the Maximum Likelihood method. AVAILABILITY AND IMPLEMENTATION: Source code is freely available for download at URL http://eden.dei.uc.pt/paquete/MOSAL, implemented in C and supported on Linux, MAC OS and MS Windows.

In this article, a local search approach is proposed for three variants of the bi-objective binary knapsack problem, with the aim of maximizing the total profit and minimizing the total weight. First, an experimental study on a given structural property of connectedness of the efficient set is conducted. Based on this property, a local search algorithm is proposed and its performance is compared to exact algorithms in terms of runtime and quality metrics. The experimental results indicate that this simple local search algorithm is able to find a representative set of optimal solutions in most of the cases, and in much less time than exact algorithms.

High failure rates are common in many programming courses worldwide. Many causes for the learning problems have already been identified and different solutions have been proposed. However, the situation remains mostly unchanged. So, new pedagogical approaches are necessary, looking to create learning contexts that motivate students, increase their involvement with course activities, and maximize their learning possibilities. In this paper we present the changes made in the structure of a non-majors introductory programming course, and discuss the results obtained. We also present the results obtained in the first implementation of the new course structure.

The goal of multiobjective optimization is to find a set of best compromise solutions for typically conflicting objectives. Due to the complex nature of most real-life problems, only an approximation to such an optimal set can be obtained within reasonable (computing) time. To compare such approximations, and thereby the performance of multiobjective optimizers providing them, unary quality measures are usually applied. Among these, thehypervolume indicator(orS-metric) is of particular relevance due to its favorable properties. Moreover, this indicator has been successfully integrated into stochastic optimizers, such as evolutionary algorithms, where it serves as a guidance criterion for finding good approximations to the Pareto front. Recent results show that computing the hypervolume indicator can be seen as solving a specialized version of Klee's Measure Problem. In general, Klee's Measure Problem can be solved with${\cal O}(n \log n + n^{d/2}\log n)$comparisons for an input instance of size$n$in$d$dimensions; as of this writing, it is unknown whether a lower bound higher than$\Omega (n \log n)$can be proven. In this paper, we derive a lower bound of$\Omega (n\log n)$for the complexity of computing the hypervolume indicator in any number of dimensions$d≫1$by reducing the so-calleduniformgapproblem to it. For the 3-D case, we also present a matching upper bound of${\cal O}(n\log n)$comparisons that is obtained by extending an algorithm for finding the maxima of a point set.

This paper presents a recursive, dimension-sweep algorithm for computing the hypervolume indicator of the quality of a set of n non-dominated points in d > 2 dimensions. It improves upon the existing HSO (Hypervolume by Slicing Objectives) algorithm by pruning the recursion tree to avoid repeated dominance checks and the recalculation of partial hypervolumes. Additionally, it incorporates a recent result for the three-dimensional special case. The proposed algorithm achieves O(nd−2log n) time and linear space complexity in the worst-case, but experimental results show that the pruning techniques used may reduce the time complexity exponent even further.