The Soft Happy Colouring (SHC) problem, a mathematical framework for identifying homophilic network structures, seeks to maximise the number of -happy vertices, i.e., vertices with at least a proportion of neighbours that share the same colour. Because this NP-hard problem makes finding exact solutions intractable for large networks, probabilistic metaheuristics such as the Cross-Entropy (CE) method are suitable candidates. However, pure CE frequently suffers from stagnation of the probability distributions and non-convergence in high-dimensional spaces. To address this, we introduce CE+LS , synergising CE’s adaptive learning with a fast, structure-aware local search ( LS ). By restricting the search exclusively to local optima, CE+LS learns from high-quality structural characteristics rather than raw random samples. We mathematically and empirically demonstrate that this search space reduction resolves CE’s stagnation, yielding a convergent algorithm. Evaluating CE+LS across 28,000 Stochastic Block Model graphs, validated by non-parametric statistical testing, demonstrates that it consistently outperforms existing heuristic and memetic algorithms. Furthermore, benchmarking against the commercial exact solver, CPLEX, on real-world networks confirms that CE+LS identifies near-optimal configurations in a fraction of the required computational time for CPLEX. Crucially, CE+LS remains highly efficient even in the tight constraint regime, where comparative algorithms usually fail.

Abstract Understanding the relationships between cryptocurrencies is important for making informed investment decisions in this financial market. Our study utilises Bayesian networks to examine the causal interrelationships among six major cryptocurrencies: Bitcoin, Binance Coin, Ethereum, Litecoin, Ripple, and Tether. Beyond understanding the connectedness, we also investigate whether these relationships evolve over time. This understanding is crucial for developing profitable investment strategies and forecasting methods. Therefore, we introduce an approach to investigate the dynamic nature of these relationships. Our observations reveal that Tether, a stablecoin, behaves distinctly compared to mining-based cryptocurrencies and stands isolated from the others. Furthermore, our findings indicate that Bitcoin and Ethereum significantly influence the price fluctuations of the other coins, except for Tether. This highlights their key roles in the cryptocurrency ecosystem. Additionally, we conduct diagnostic analyses on constructed Bayesian networks, emphasising that cryptocurrencies generally follow the same market direction as extra evidence for interconnectedness. Moreover, our approach reveals the dynamic and evolving nature of these relationships over time, offering insights into the ever-changing dynamics of the cryptocurrency market.

Covid19-twitter: A Twitter-based Dataset for Discourse Analysis in Sentence-level Sentiment Classification

Resource constrained job scheduling is a hard combinatorial optimisation problem that originates in the mining industry. Off-the-shelf solvers cannot solve this problem satisfactorily in reasonable time-frames, while other solution methods such as evolutionary computation methods and matheuristics cannot guarantee optimality and require low-level customisation and specialised heuristics to be effective. This paper addresses this gap by proposing a genetic programming algorithm to discover efficient search strategies of constraint programming for resource-constrained job scheduling. In the proposed algorithm, evolved programs represent variable selectors to be used in the search process of constraint programming, and their fitness is determined by the quality of solutions obtained by constraint programming for training instances. The novelties of this algorithm are (1) a new representation of variable selectors, (2) a new fitness evaluation scheme, and (3) a pre-selection mechanism. Tests with a large set of random and benchmark instances show that the evolved variable selectors can significantly improve the efficiency of constraining programming. Compared to highly customised metaheuristics and hybrid algorithms, evolved variable selectors can help constraint programming identify quality solutions faster and proving optimality is possible if sufficiently large run-times are allowed. The evolved variable selectors are especially helpful when solving instances with large numbers of machines.

Disseminating prior knowledge about a pattern recognition task in Deep Neural Networks (DNNs) is desirable, to enable them to learn some complex patterns or representations, that are otherwise difficult to learn via usual data-driven training. Several methods have been proposed for that purpose, but creating an end-to-end trainable DNN model, while keeping it informed with prior knowledge, remains a challenging task. In this paper, we propose a method to disseminate prior knowledge in DNN models. Specifically, we created a novel MAsk-based pRior Knowledge diSsemination mechanism (MARKS-mech), that transfers logical prior knowledge in DNN models via input data transformation. We utilize a recently constructed Twitter-based dataset to perform our experiments, which is specifically designed to test the logical prior knowledge dissemination ability of methods like ours. We find that our method provides superior knowledge dissemination performance compared to the baselines.

Constraint programming (CP) is a powerful technique for solving constraint satisfaction and optimization problems. In CP solvers, the variable ordering strategy used to select which variable to explore first in the solving process has a significant impact on solver effectiveness. To address this issue, we propose a novel variable ordering strategy based on supervised learning, which we evaluate in the context of job shop scheduling problems. Our learning-based methods predict the optimal solution of a problem instance and use the predicted solution to order variables for CP solvers. Unlike traditional variable ordering methods, our methods can learn from the characteristics of each problem instance and customize the variable ordering strategy accordingly, leading to improved solver performance. Our experiments demonstrate that training machine learning models is highly efficient and can achieve high accuracy. Furthermore, our learned variable ordering methods perform competitively compared to four existing methods. Finally, we showcase the benefits of integrating machine learning-based variable ordering methods with conventional domain-based approaches through tie-breaking.

Resource constraint job scheduling is an important combinatorial optimization problem with many practical applications. This problem aims at determining a schedule for executing jobs on machines satisfying several constraints (e.g., precedence and resource constraints) given a shared central resource while minimizing the tardiness of the jobs. Due to the complexity of the problem, several exact, heuristic, and hybrid methods have been attempted. Despite their success, scalability is still a major issue of the existing methods. In this study, we develop a new genetic programming algorithm for resource constraint job scheduling to overcome or alleviate the scalability issue. The goal of the proposed algorithm is to evolve effective and efficient multipass heuristics by a surrogate-assisted learning mechanism and self-competitive genetic operations. The experiments show that the evolved multipass heuristics are very effective when tested with a large dataset. Moreover, the algorithm scales very well as excellent solutions are found for even the largest problem instances, outperforming existing metaheuristic and hybrid methods.

Operational researchers and decision modelers have aspired to optimization technologies with a self-adaptive mechanism to cope with new problem formulations. Self-adaptive mechanisms not only free users from low-level and complex development tasks to enhance optimization efficiency but also allow them to focus on addressing high-level real-world operational requirements. In recent years, there has been a growing interest in applying machine learning and artificial intelligence techniques to improve self-adaptive mechanisms. However, learning to optimize hard combinatorial optimization problems remains a challenging task. This article proposes a new genetic programming approach to evolve efficient variable selectors to enhance the search mechanism in constraint programming. Starting with a set of training instances for a specific combinatorial optimization problem, the proposed approach evaluates variable selectors and evolves them to be more efficient over a number of generations. The novelties of our proposed approach are threefold: 1) a new representation of variable selectors; 2) a new mechanism for fitness evaluations; and 3) a preselection technique. We examine performance of the proposed approach on different job-shop scheduling problems, and the results show that variable selectors can be evolved efficiently. In particular, there are substantial reductions in the computational effort required for the search component of the constraint solver as well as increased chances of finding the optimal solutions. Further analyses also confirm the efficacy of our approach in respect to scalability, generalization, and interpretability of the evolved variable selectors.

Resource constrained job scheduling is a challenging combinatorial optimisation with many real-world applications. A number of exact methods and meta-heuristics have been proposed in the literature to solve this problem, but often encounter scalability issues. This paper investigates an automated heuristic design approach to deal with this problem. The aim of this approach is to generate heuristics that can quickly construct good solutions, which can be applied directly or used to initialise other meta-heuristics. A new adaptive genetic programming algorithm is proposed to coevolve a large set of reusable heuristics to solve the resource constrained job scheduling problem. There are three different aspects to the novelty behind our proposed algorithm: (a) a new phenotypic representation of heuristics, (b) an efficient mapping technique to monitor the evolutionary process, and (c) an adaptive fitness function to guide the search towards a diverse and competitive population. The experimental results show that evolved heuristics show promise and are able to outperform some existing meta-heuristics for large-scale instances. Analyses also show that the algorithm can be further improved if appropriate parameters are selected.

Balancing and sequencing of assembly lines is the process of partitioning the assembly work in terms of operations, and to assign and schedule them to workstations in an optimal way. In particular, in response to highly competitive market conditions, manufacturers face the problem of producing several models of a base product on the same assembly line, which leads to a mixed-model assembly line balancing problem. This problem is proven to be NP-hard and is computationally challenging. In addition to the usual problem constraints (e.g. precedences between operations and satisfying cycle times), we consider setup times between operations, which further complicates the problem. In this work, we present a novel ant colony optimisation approach, which is based on learning permutations of the operations. The permutations are then mapped to an assignment of operations to workstations in a greedy fashion. The numerical experiments demonstrate improvements both in the quality of solutions and significant improvements in computational time in comparison to the exact state of the art solution methods currently available in the literature.

This paper considers single-machine just-in-time scheduling of jobs that may be grouped into batches subject to a constraint on batches' weights. A job has a weight, due date, and earliness and tardiness penalties per unit time. A batch's processing time is determined by its jobs. Each job inherits its batch's completion time. The objective is to minimize the weighted sum of earliness and tardiness penalties of all jobs. This problem is challenging: Jobs-to-batch assignment changes the batch's processing time; thus, affects the structure of the entire solution and most importantly of its cost components. This problem is an excellent benchmark for testing linkage learning techniques, which exploit a problem's structure. We propose a matheuristic LTGA, which integrates evolutionary algorithms with mixed-integer programming (MIP). It builds a linkage tree that extracts the dependency among decision variables of MIP solutions. We compare its performance to a state of the art matheuristic CMSA, which combines the learning component of an ant colony system (ACS) with MIP within a construct, solve, merge, and adapt framework. It uses knowledge extracted from ACS' ants to construct a restricted MIP, solves it efficiently, and feeds it back to ACS. Computational tests indicate that LTGA outperforms MIP solvers and CMSA.

This study considers a resource constrained job scheduling problem. Jobs need to be scheduled on different machines satisfying a due time. If delayed, the jobs incur a penalty which is measured as a weighted tardiness. Furthermore, the jobs use up some proportion of an available resource and hence there are limits on multiple jobs executing at the same time. Due to complex constraints and a large number of decision variables, the existing solution methods, based on meta-heuristics and mathematical programming, are very time-consuming and mainly suitable for small-scale problem instances. We investigate a genetic programming approach to automatically design reusable scheduling heuristics for this problem. A new representation and evaluation mechanisms are developed to provide the evolved heuristics with the ability to effectively construct and refine schedules. The experiments show that the proposed approach is more efficient than other genetic programming algorithms previously developed for evolving scheduling heuristics. In addition, we find that the obtained heuristics can be effectively reused to solve unseen and large-scale instances and often find higher quality solutions compared to algorithms already known in the literature in significantly reduced time-frames.

Pit planning and long-term production scheduling are important tasks within the mining industry. This is a great opportunity for optimisation techniques, as the scale of a lot of mining operations means that a small percentage increase in efficiency can translate to millions of dollars in profit. The precedence constrained production scheduling problem (PCPSP) combines both of these aspects of mine optimisation and aims to find a solution which tells a mining company what part of the orebody to mine, and at what time during the life of the mine. This paper presents a GRASP-Mixed Integer Programming hybrid metaheuristic algorithm for solving the PCPSP which consists of two parts: a fast, period-by-period, random construction phase and a local improvement heuristic. It is compared to the current published state-of-the-art results on well known benchmark problems from minelib [5] and is shown to give better quality results in four of the six instances, and within 2% of the LP upper bound in the remaining two. The PCPSP is a good candidate for hybrid metaheuristics as the size of the problems make solving them with mathematical solvers alone intractable.

In this paper we present a parallel implementation of an existing Lagrangian heuristic for solving a project scheduling problem. The original implementation uses Lagrangian relaxation to generate useful upper bounds and provide guidance towards generating good lower bounds or feasible solutions. These solutions are further improved using Ant Colony Optimisation via loose and tight couplings. While this approach has proven to be effective, there are often large gaps for a number of the problem instances. Thus, we aim to improve the performance of this algorithm through a parallel implementation on a multicore shared memory architecture. However, the original algorithm is inherently sequential and is not trivially parallelisable due to the dependencies between the different components involved. Hence, we propose different approaches to carry out this parallelisation. Computational experiments show that the parallel version produces consistently better results given the same time limits.

Hybrid methods for solving combinatorial optimization problems have become increasingly popular recently. The present paper is concerned with hybrids of ant colony optimization and constraint programming which are typically useful for problems with hard constraints. However, the original algorithm suffered from large CPU time requirements. It was shown that such an integration can be made efficient via a further hybridization with beam search resulting in CP-Beam-ACO. The original work suggested this in the context of job scheduling. We show here that this algorithm type is also effective on another problem class, namely the car sequencing. We consider an optimization version, where we aim to optimize the utilization rates across the sequence. Car sequencing is a notoriously difficult problem, because it is difficult to obtain good bounds via relaxations. We show that stochastic sampling provides superior results to well known lower bounds for this problem when combined with CP-Beam-ACO.

This paper investigates the use of hybrid meta-heuristics based on ant colony optimization (ACO) for the strip packing problem. Here, a fixed set of rectangular items of fixed sizes have to be placed on a strip of fixed width and infinite height without overlaps and with the objective to minimize the height used. We analyze a commonly used basic placement heuristic (BLF) by itself and in a number of hybrid combinations with ACO. We compare versions that learn item order only, item rotation only, both independently, and rotations conditionally upon placement order. Our analysis shows that integrating a learning meta-heuristic provides a significant performance advantage over using the basic placement heuristic by itself. The experiments confirm that even just learning a placement order alone can provide significant performance improvements. Interestingly, learning item rotations provides at best a marginal advantage. The best hybrid algorithm presented in this paper significantly outperforms previously reported strip packing meta-heuristics.