Learning and Intelligent Optimization

In this paper we present a hybrid immunological inspired algorithm (Hybrid-IA) for solving the Minimum Weighted Feedback Vertex Set (M W F V S) problem. MWFVS is one of the most interesting and challenging combinatorial optimization problem, which finds application in many fields and in many real life tasks. The proposed algorithm is inspired by the clonal selection principle, and therefore it takes advantage of the main strength characteristics of the operators of (i) cloning; (ii) hypermutation; and (iii) aging. Along with these operators, the algorithm uses a local search procedure, based on a deterministic approach, whose purpose is to refine the solutions found so far. In order to evaluate the efficiency and robustness of Hybrid-IA several experiments were performed on different instances, and for each instance it was compared to three different algorithms: (1) a memetic algorithm based on a genetic algorithm (MA); (2) a tabu search metaheuristic (XTS); and (3) an iterative tabu search (ITS). The obtained results prove the efficiency and reliability of hybrid-IA on all instances in term of the best solutions found and also similar performances with all compared algorithms, which represent nowadays the state-of-the-art on for MWFVS problem.

Determining if a graph displays a clustered structure prior to subjecting it to any cluster detection technique has recently gained attention in the literature. Attempts to group graph vertices into clusters when a graph does not have a clustered structure is not only a waste of time; it will also lead to misleading conclusions. To address this problem, we introduce a novel statistical test, the $$\delta $$-test, which is based on comparisons of local and global densities. Our goal is to assess whether a given graph meets the necessary conditions to be meaningfully summarized by clusters of vertices. We empirically explore our test’s behavior under a number of graph structures. We also compare it to other recently published tests. From a theoretical standpoint, our test is more general, versatile and transparent than recently published competing techniques. It is based on the examination of intuitive quantities, applies equally to weighted and unweighted graphs and allows comparisons across graphs. More importantly, it does not rely on any distributional assumptions, other than the universally accepted definition of a clustered graph. Empirically, our test is shown to be more responsive to graph structure than other competing tests.

Over the last years, binary decision diagrams (BDDs) have become a powerful tool in the field of combinatorial optimization. They are directed acyclic multigraphs and represent the solution space of binary optimization problems in a recursive way. During their construction, merging of nodes in this multigraph is applied to keep the size within polynomial bounds resulting in a discrete relaxation of the original problem. The longest path length through this diagram corresponds then to an upper bound of the optimal objective value. The algorithm deciding which nodes to merge is called a merging heuristic. A commonly used heuristic for layer-wise construction is minimum longest path length (minLP) which sorts the nodes in a layer descending by the currently longest path length to them and subsequently merges the worst ranked nodes to reduce the width of a layer. A shortcoming of this approach is that it neglects the (dis-)similarity between states it merges, which we assume to have negative impact on the quality of the finally obtained bound. By means of a simple tie breaking procedure, we show a way to incorporate the similarity of states into minLP using different distance functions to improve dual bounds for the maximum independent set problem (MISP) and the set cover problem (SCP), providing empirical evidence for our assumption. Furthermore, we extend this procedure by applying similarity-based node merging also to nodes with close but not necessarily identical longest path values. This turns out to be beneficial for weighted problems where ties are substantially less likely to occur. We evaluate the method on the weighted MISP and tune parameters that control as to when to apply similarity-based node merging.

We consider one problem of partitioning a finite set of points in Euclidean space into clusters so as to minimize the sum over all clusters of the intracluster sums of the squared distances between clusters elements and their centers. The centers of some clusters are given as an input, while the other centers are unknown and defined as centroids (geometrical centers). It is known that the general case of the problem is strongly NP-hard. We show that there exists an exact polynomial algorithm for the one-dimensional case of the problem.

In the past, combinatorial structures have been used only to tune parameters of neural networks. In this paper, we employ for the first time, neural networks and Boltzmann machines for the construction of covering arrays (CAs). In past works, Boltzmann machines were successfully used to solve set cover instances. For the construction of CAs, we consider the equivalent set cover instances and use Boltzmann machines to solve these instances. We adapt an existing algorithm for solving general set cover instances, which is based on Boltzmann machines and apply it for CA construction. Furthermore, we consider newly designed versions of this algorithm, where we consider structural changes of the underlying Boltzmann machine, as well as a version with an additional feedback loop, modifying the Boltzmann machine. Last, one variant of this algorithm employs learning techniques based on neural networks to adjust the various connections encountered in the graph representation of the considered set cover instances. Supported by an experimental evaluation our findings can act as a beacon for future applications of neural networks in the field of covering array generation and related discrete structures.

We consider the three-dimensional Bin Packing Problem in which a set of boxes must be packed into the minimum number of identical bins. We present a heuristic that iteratively creates new sequences of boxes that defines the packing order used to generate a new solution. The sequences are generated retaining, adaptively, characteristics of previous sequences for search intensification and diversification. Computational experiments of the effectiveness of this approach are presented and discussed.

This paper proposes a Sequential Model Based Optimization framework for solving optimization problems characterized by a black-box, multi-extremal, expensive and partially defined objective function, under unknown constraints. This is a typical setting for simulation-optimization problems, where the objective function cannot be computed for some configurations of the decision/control variables due to the violation of some (unknown) constraint. The framework is organized in two consecutive phases, the first uses a Support Vector Machine classifier to approximate the boundary of the unknown feasible region within the search space, the second uses Bayesian Optimization to find a globally optimal (feasible) solution. A relevant difference with traditional Bayesian Optimization is that the optimization process is performed on the estimated feasibility region, only, instead of the entire search space. Some results on three 2D test functions and a real case study for the Pump Scheduling Optimization in Water Distribution Networks are reported. The proposed framework proved to be more effective and efficient than Bayesian Optimization approaches using a penalty for function evaluations outside the feasible region.

In this paper we propose an algorithm for training neural network architectures, called Hessian Free algorithm with Curvature Scaled Adaptive Momentum (HF-CSAM). The algorithm’s weight update rule is similar to SGD with momentum but with two main differences arising from the formulation of the training task as a constrained optimization problem: (i) the momentum term is scaled with curvature information (in the form of the Hessian); (ii) the coefficients for the learning rate and the scaled momentum term are adaptively determined. The implementation of the algorithm requires minimal additional computations compared to a classical SGD with momentum iteration since no actual computation of the Hessian is needed, due to the algorithm’s requirement for computing only a Hessian-vector product. This product can be computed exactly and very efficiently within any modern computational graph framework such as, for example, Tensorflow. We report experiments with different neural network architectures trained on standard neural network benchmarks which demonstrate the efficiency of the proposed method.

We introduce the following version of an “inefficient” bin packing problem: maximize the number of bins under the restriction that the total content of any two bins is larger than the bin capacity. There is a trivial upper bound on the optimum in terms of the total size of the items. We refer to the decision version of this problem with the number of bins equal to the trivial upper bound as Irreducible Bin Packing. We prove that this problem is NP-complete in an ordinary sense and derive a sufficient condition for its polynomial solvability. The problem has a certain connection to a routing open shop problem which is a generalization of the metric TSP and open shop, known to be NP-hard even for two machines on a 2-node network. So-called job aggregation at some node of a transportation network can be seen as an instance of a bin packing problem. We show that for a two-machine case a positive answer to the Irreducible Bin Packing problem question at some node leads to a linear algorithm of constructing an optimal schedule subject to some restrictions on the location of that node.

The problem of generating surgery schedules is formulated as a mathematical model with probabilistic constraints. The approach presented is a new method for tackling probabilistic constraints using machine learning. The technique is inspired by models that use slacks in capacity planning. Essentially support vector classification is used to learn a linear constraint that will replace the probabilistic constraint. The data used to learn this constraint is labeled using Monte Carlo simulations. This data is iteratively discovered, during the optimization procedure, and augmented to the training set. The linear support vector classifier is then updated during search, until a feasible solution is discovered. The stochastic surgery model presented is inspired by real challenges faced by many hospitals today and tested on real-life data.

We consider a problem of 2-partitioning a finite sequence of points in Euclidean space into two clusters of the given sizes with some additional constraints. The solution criterion is the minimum of the sum (over both clusters) of weighted intracluster sums of squared distances between the elements of each cluster and its center. The weights of the intracluster sums are equal to the cardinalities of the desired clusters. The center of one cluster is given as input, while the center of the other one is unknown and is determined as a geometric center, i.e. as a point of space equal to the mean of the cluster elements. The following constraints hold: the difference between the indices of two subsequent points included in the first cluster is bounded from above and below by given some constants. It is shown that the considered problem is the strongly NP-hard one. An exact algorithm is proposed for the case of integer-valued input of the problem. This algorithm has a pseudopolynomial running time if the space dimension is fixed.

This paper addresses a new optimization method for a variant of the category of orienteering problems (OP), which is well-known as the capacitated team orienteering problem (CTOP). The main objective of CTOP focuses on the maximization of the total collected profit from a set of candidate nodes or customers by taking into account the limitations of vehicle capacity and time upper boundary of a constructed route. To solve CTOP, we present a new optimization algorithm called the Similarity Hybrid Harmony Search. This methodology includes an innovative “similarity process” technique, which takes advantage the most profitable nodes/customers during the algorithmic procedure aiming to extend the diversification in the solution area. The experimental tests were conducted in the most popular set of instances and the obtained results are compared with most competitive algorithms in the literature.

This work proposes Adaptive General Variable Neighborhood Search metaheuristic algorithms for the efficient solution of Pollution Location Inventory Routing Problems (PLIRPs). A comparative computational study, between the proposed methods and their corresponding classic General Variable Neighborhood Search versions, illustrates the effectiveness of the intelligent mechanism used for automating the re-ordering of the local search operators in the improvement step of each optimization method. Results on 20 PLIRP benchmark instances show the efficiency of the proposed metaheuristics.

We propose a Relaxation Adaptive Memory Programming (RAMP) algorithm for the solution of the Single Source Capacitated Facility Location Problem (SSCFLP). This problem considers a set of possible locations for opening facilities and a set of clients whose demand must be satisfied. The objective is to minimize the cost of assigning the clients to the facilities, ensuring that all clients are served by only one facility without exceeding the capacity of the facilities. The RAMP framework efficiently explores the relation between the primal and the dual sides of combinatorial optimization problems. In our approach, the dual problem, obtained through a lagrangean relaxation, is solved by subgradient optimization. Computational experiments of the effectiveness of this approach are presented and discussed.

In large cities all around the world, individual and motorized traffic is still prevalent. This circumstance compromises the quality of living, and moreover, space inside cities for parking individual vehicles for movement is scarce and is becoming even scarcer. Thus, the need for a greener means of transportation and less individual vehicles inside the cities is demanded and rising. An already accepted and established solution possibility to these problems are public bike sharing systems (PBS). Such systems are often freely available to people for commuting within the city and utilize the available space in the city more efficiently than individual vehicles. When building or extending a PBS, a certain optimization goal is to place stations inside a city or a part of it, such that the number of bike trips per time unit is maximized under certain budget constraints. In this context, it is also important to consider rebalancing and maintenance costs as they introduce substantial supplementary costs in addition to the fixed and variable costs when building or extending a PBS. In contrast to the literature, this work introduces a novel approach which is particularly designed to scale well to large real-world instances. Based on our previous work, we propose a multilevel refinement heuristic operating on hierarchically clustered input data. This way, the problem is coarsened until a manageable input size is reached, a solution is derived, and then step by step extended and refined until a valid solution for the whole original problem instance is obtained. As an enhancement to our previous work, we introduce the following extensions. Instead of considering an arbitrary integral number of slots for stations, we now use sets of predefined station configurations. Moreover, a local search is implemented as refinement step in the multilevel refinement heuristic and we now consider real-world input data for the city of Vienna.

The Prize-Collecting Traveling Salesman Problem is a class of generalizations of the classic Traveling Salesman Problem (TSP) where it is not necessary to visit all the vertices. Given the edge costs and a certain profit associated with each vertex, the goal is to find a route which satisfies maximum collected profit and minimum traveling costs constraints. We show polynomial-time approximation algorithms for two variants of the problem and establish conditions under which the presented algorithms are asymptotically optimal on random inputs.

Artificial Bee Colony algorithm is a very powerful Swarm Intelligence Algorithm that has been applied in a number of different kind of optimization problems since the time that it was published. In recent years there is a growing number of optimization models that trying to reduce the energy consumption in routing problems. In this paper, a new variant of Artificial Bee Colony algorithm, the Parallel Multi-Start Multiobjective Artificial Bee Colony algorithm (PMS-ABC) is proposed for the solution of a Vehicle Routing Problem variant, the Multiobjective Energy Reduction Multi-Depot Vehicle Routing Problem (MERMDVRP). In the formulation four different scenarios are proposed where the distances between the customers and the depots are either symmetric or asymmetric and the customers have either demand or pickup. The algorithm is compared with three other multiobjective algorithms, the Parallel Multi-Start Non-dominated Sorting Differential Evolution (PMS-NSDE), the Parallel Multi-Start Non-dominated Sorting Particle Swarm Optimization (PMS-NSPSO) and the Parallel Multi-Start Non-dominated Sorting Genetic Algorithm II (PMS-NSGA II) in a number of benchmark instances.

The Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) is the well-known combinatorial optimization problem having numerous valuable applications in operations research. Unlike the classic CVRP (without time windows constraints), approximability of the CVRPTW (even in the Euclidean plane) in the class of algorithms with theoretical guarantees is much less studied. To the best of our knowledge, the family of such algorithms is exhausted by the Quasi-Polynomial Time Approximation Scheme (QPTAS) proposed by L. Song et al. for the general setting of the planar CVRPTW and two our recent approximation algorithms, which are Efficient Polynomial Time Approximation Schemes (EPTAS) for any fixed capacity q and number p of time windows and remain PTAS for slow-growing dependencies $$q=q(n)$$ and $$p=p(n)$$. In this paper, combining the well-known instance decomposition framework by A. Adamaszek et al. and QPTAS by L. Song et al. we propose a novel approximation scheme for the planar CVRPTW, whose running time remains polynomial for the significantly wider range of q and p.

It is generally accepted that cooperation-based strategies in parallel metaheuristics exhibit better performances in contrast with non-cooperative approaches. In this paper, we study how the cooperation between processes affects the performance and solution quality of parallel algorithms. The purpose of this study is to provide researchers with a practical starting point for designing better cooperation strategies in parallel metaheuristics. To achieve that, we propose two parallel models based on the general variable neighborhood search (GVNS) to solve the capacitated vehicle routing problem (CVRP). Both models scan the search space by using multiple search processes in parallel. The first model lacks communication, while on the other hand, the second model follows a strategy based on information exchange. The received solutions are utilized to guide the search. We conduct an experimental study using well-known benchmark instances of the CVRP, in which the usefulness of communication throughout the search process is assessed. The findings confirm that careful design of the cooperation strategy in parallel metaheuristics can yield better results.

Facility Location embodies a class of problems concerned with locating a set of facilities to serve a geographically distributed population of customers at minimum cost. We address the classical Capacitated Facility Location Problem (CFLP) in which the assignment of facilities to customers must ensure enough facility capacity and all the customers must be served. This is a well-known NP-hard problem in combinatorial optimization that has been extensively studied in the literature. Due to the difficulty of the problem, significant research efforts have been devoted to developing advanced heuristic methods aimed at finding high-quality solutions in reasonable computational times. We propose a Relaxation Adaptive Memory Programming (RAMP) approach for the CFLP. Our method combines lagrangean subgradient search with an improvement method to explore primal-dual relationships to create advanced memory structures that integrate information from both primal and dual solution spaces. The algorithm was tested on the standard ORLIB dataset and on other very large-scale instances for the CFLP. Our approach efficiently found the optimal solution for all ORLIB instances and very competitive results for the large-scale ones. Comparisons with current best-performing algorithms for the CFLP show that our RAMP algorithm exhibits excellent results.

In this paper, a tourist trip design problem is simulated by the Capacitated Team Orienteering Problem (CTOP). The objective of the CTOP is to form feasible solution, as a set of itineraries, that represent a sequence visit of nodes, that maximize the total prize collected from them. Each itinerary is constrained by the vehicle capacity and the total travelled time. The proposed algorithmic framework, the Distance Related Differential Algorithm (DRDE), is a combination of the widely-known Differential Evolution algorithm (DE) and a novel encoding/decoding process, namely the Distance Related (DR). The process is based on the representation of the solution vector by the Euclidean Distance of the included nodes and offers a data-oriented approach to apply the original DE to a discrete optimization problem, such as the CTOP. The efficiency of the proposed algorithm is demonstrated over computational experiments.

One of the upcoming categories of Computational Intelligence (CI) is meta-heuristic schemes, which derive their intelligence from strategies that are met in nature, namely Nature Inspired Algorithms. These algorithms are used in various optimization problems because of their ability to cope with multi-objective problems and solve difficult constraint optimization problems. In this work, the performance of Sonar Inspired Optimization (SIO) is tested in a non-smooth, non-convex multi-objective Energy problem, namely the Economic Emissions Load Dispatch (EELD) problem. The research hypothesis was that this new nature-inspired method would provide better solutions because of its mechanisms. The algorithm manages to deal with constraints, namely Valve-point Effect and Multi-fuel Operation, and produces only feasible solutions, which satisfy power demand and operating limits of the system examined. Also, with a lot less number of agents manages to be very competitive against other meta-heuristics, such as hybrid schemes and established nature inspired algorithms. Furthermore, the proposed scheme outperforms several methods derived from literature.

The optimal product line design is one of the most critical decisions for a firm to stay competitive, since it is related to the sustainability and profitability of a company. It is classified as an NP-hard problem since no algorithm can certify in polynomial time that the optimum it identifies is the overall optimum of the problem. The focus of this research is to propose a new hybrid optimization method (FAGA) combining Firefly algorithm (FA) and Genetic algorithm (GA). The proposed hybrid method is applied to the product line design problem and its performance is compared to those of previous approaches, like genetic algorithm (GA) and simulated annealing (SA), by using both actual and artificial consumer-related data preferences for specific products. The comparison results demonstrate that the proposed hybrid method is superior to both genetic algorithm and simulated annealing in terms of accuracy, efficiency and convergence speed.

Simulated annealing (SA) is a well-known metaheuristic commonly used to solve a great variety of $$\mathcal {NP}$$-hard problems such as the quadratic assignment problem (QAP). As commonly known, the choice and size of neighborhoods can have a considerable impact on the performance of SA. In this work, we investigate and propose a SA variant that considers variable neighborhood structures driven by the state of the search. In the computational experiments, we assess the contribution of this SA variant in comparison with the state-of-the-art SA for the QAP applied to printed circuit boards and conclude that our approach is able to report better solutions by means of short computational times.

In many Natural Language Processing problems the combination of machine learning and optimization techniques is essential. One of these problems is estimating the effort required to improve, under direct human supervision, a text that has been translated using a machine translation method. Recent developments in this area have shown that Gaussian Processes can be accurate for post-editing effort prediction. However, the Gaussian Process kernel has to be chosen in advance, and this choice influences the quality of the prediction. In this paper, we propose a Genetic Programming algorithm to evolve kernels for Gaussian Processes. We show that the combination of evolutionary optimization and Gaussian Processes removes the need for a-priori specification of the kernel choice, and achieves predictions that, in many cases, outperform those obtained with fixed kernels.

Deciding upon which algorithm would be the most efficient for a given set of linear programming problems is a significant step in linear programming solvers. CPLEX Optimizer supports primal and dual variants of the simplex algorithm and the interior point method. In this paper, we examine a prediction model using artificial neural networks for the performance of CPLEX’s interior point method on a set of benchmark linear programming problems (netlib, kennington, Mészáros, Mittelmann). Our study consists of the measurement of the execution time needed for the solution of 295 linear programming problems. Specific characteristics of the linear programming problems are examined, such as the number of constraints and variables, the nonzero elements of the constraint matrix and the right-hand side, and the rank of the constraint matrix of the linear programming problems. The purpose of our study is to identify a model, which could be used for prediction of the algorithm’s efficiency on linear programming problems of similar structure. This model can be used prior to the execution of the interior point method in order to estimate its execution time. Experimental results show a good fit of our model both on the training and test set, with the coefficient of determination value at 78% and 72%, respectively.

The cycle double cover conjecture is a famous longstanding unsolved conjecture in graph theory. It is related and can be reduced to the compatible circuit decomposition problem. Recently Fleischner et al. (2018) provided a sufficient condition for a compatible circuit decomposition, which is called SUD-$$K_5$$-minor freeness. In a previous work we developed an abstract mathematical model for finding SUD-$$K_5$$-minors and based on the model a mixed integer linear program (MIP). In this work we propose a respective boolean satisfiability (SAT) model and compare it with the MIP model in computational tests. Non-trivial symmetry breaking constraints are proposed, which improve the solving times of both models considerably. Compared to the MIP model the SAT approach performs significantly better. We use the faster algorithm to further test graphs of graph theoretic interest and were able to get new insights. Among other results we found snarks with 30 and 32 vertices that do not contain a perfect pseudo-matching, that is a spanning subgraph consisting of $$K_2$$ and $$K_{1,3}$$ components, whose contraction leads to a SUD-$$K_5$$-minor free graph.

In the problem of barrier monitoring using mobile sensors with circular coverage areas, it is required to move the sensors onto some line (barrier) so that each barrier point belongs to the coverage area of at least one sensor. One of the criteria for the effectiveness of coverage is the minimum of the total length of the paths traveled by sensors. If we give up the requirement to move the sensors onto the barrier, then the problem (which is NP-hard) will not be easier. But at the same time, the value of the objective function can be reduced significantly. In this paper, we propose a new pseudo-polynomial algorithm which in the case of equal disks builds an optimal solution in the $$ L_1 $$ metric and a $$\sqrt{2} $$-approximate solution in the Euclidean metric. This algorithm is an efficient implementation of the dynamic programming method in which at the stage of preliminary calculations for each sensor it is possible to find a finite number of analytical functions equal to the minimal length of the path traveled by the sensor depending on the positions of the circle and the barrier. The conducted numerical experiment showed that if we remove the requirement to move the sensors onto the barrier, then the value of the objective function may decrease several times.

We consider a Min-Power Bounded-Hops Symmetric Connectivity problem that consists in the construction of communication spanning tree on a given graph, where the total energy consumption spent for the data transmission is minimized and the maximum number of edges in a path in the tree between any pair nodes is bounded by some predefined constant. We focus on the planar Euclidian case of this problem where the power cost necessary for the communication between two network elements is proportional to the squared distance between them. Since this is an NP-hard problem, we propose different heuristics based on the following metaheuristics: genetic local search, variable neighborhood search, and ant colony optimization. We perform a posteriori comparative analysis of the proposed algorithms and present the obtained results in this paper.

Many practical applications such as multidimensional integration and quasi–Monte Carlo simulations rely on a uniform sampling of high–dimensional spaces. Halton sequences are d–dimensional quasirandom sequences that fill the d–dimensional hyperspace uniformly and can be generated with low computational costs. Generalized (scrambled) Halton sequences improve the properties of plain Halton sequences in higher dimensions by digit scrambling. Discrete nature–inspired optimization methods have been used to search for scrambling permutations of d–dimensional generalized Halton sequences that minimized the discrepancy of the generated point sets in the past. In this work, a continuous nature–inspired optimization method, the differential evolution, is used to optimize generalized Halton sequences.

The optimization of massively multi-modal functions is a challenging task, particularly for problems where the search space can lead the optimization process to local optima. While evolutionary algorithms have been extensively investigated for these optimization problems, Bayesian Optimization algorithms have not been explored to the same extent. In this paper, we study the behavior of Bayesian Optimization as part of a hybrid approach for solving several massively multi-modal functions. We use well-known benchmarks and metrics to evaluate how different variants of Bayesian Optimization deal with multi-modality.