Search

Abstract The problem of minimizing total quadratic completion time in flow shops presents a significant challenge in industries such as chemical, metallurgical, and ceramic manufacturing. Initially investigated by Ren and coauthors (2016) [1], this problem addresses the need to balance intermediate inventory reduction with maximizing resource utilization, particularly in multi-objective scenarios. We proposed two innovative metaheuristics (Covid and CHIO algorithms) and a mathematical optimization model. Evaluations were conducted across two industrial settings and three additional benchmarks from existing literature. Through the statistical analysis and performance profiling, our findings indicate that the Covid and CHIO algorithms outperform the Differential Evolution of Ren and coauthors (2016) [1] and the Iterated Greedy Algorithm of Pan and Ruiz (2012) [2], as well as other techniques. Notably, the proposed Covid and CHIO algorithms achieved an average relative deviation from the optimal solution of 0.41% and 0.23%, respectively. Furthermore, they consistently outperformed other methods, securing the best solution in at least 12.5% of instances across all benchmarks, with their worst solutions closer to the best solutions than those produced by alternative approaches.

The satisfiability (SAT) problem is a fundamental challenge in computing and has a broad range of applications. This problem is NP-complete, and many algorithmic and architectural improvements have aimed at accelerating the SAT solver. But most existing stochastic local search (SLS) hardware solvers still rely on the outdated WalkSAT algorithm, and they have a reduced performance when handling problems with a large number of literals per clause. In this paper, we present FYalSAT, a field-programmable gate array (FPGA) based SLS SAT solver designed for high throughput. We incorporate a conflict-free data rearrangement scheme and a novel synchronization method to increase the parallelism. We also apply various optimizations such as clause prefetching, module overlapping, and pipelining to improve the performance. Experimental results demonstrate that FYalSAT outperforms the throughput of existing SLS FPGA solvers by $9.07\times $ – $110\times $ for benchmarks with a large number of literals per clause.

We propose and implement an interpretable machine learning classification model for Explainable AI (XAI) based on expressive Boolean formulas. Potential applications include credit scoring and diagnosis of medical conditions. The Boolean formula defines a rule with tunable complexity (or interpretability) according to which input data are classified. Such a formula can include any operator that can be applied to one or more Boolean variables, thus providing higher expressivity compared to more rigid rule- and tree-based approaches. The classifier is trained using native local optimization techniques, efficiently searching the space of feasible formulas. Shallow rules can be determined by fast Integer Linear Programming (ILP) or Quadratic Unconstrained Binary Optimization (QUBO) solvers, potentially powered by special-purpose hardware or quantum devices. We combine the expressivity and efficiency of the native local optimizer with the fast operation of these devices by executing non-local moves that optimize over the subtrees of the full Boolean formula. We provide extensive numerical benchmarking results featuring several baselines on well-known public datasets. Based on the results, we find that the native local rule classifier is generally competitive with the other classifiers. The addition of non-local moves achieves similar results with fewer iterations. Therefore, using specialized or quantum hardware could lead to a significant speedup through the rapid proposal of non-local moves.

We propose and implement an interpretable machine learning classification model for Explainable AI (XAI) based on expressive Boolean formulas. Potential applications include credit scoring and diagnosis of medical conditions. The Boolean formula defines a rule with tunable complexity (or interpretability) according to which input data are classified. Such a formula can include any operator that can be applied to one or more Boolean variables, thus providing higher expressivity compared to more rigid rule- and tree-based approaches. The classifier is trained using native local optimization techniques, efficiently searching the space of feasible formulas. Shallow rules can be determined by fast Integer Linear Programming (ILP) or Quadratic Unconstrained Binary Optimization (QUBO) solvers, potentially powered by special-purpose hardware or quantum devices. We combine the expressivity and efficiency of the native local optimizer with the fast operation of these devices by executing non-local moves that optimize over the subtrees of the full Boolean formula. We provide extensive numerical benchmarking results featuring several baselines on well-known public datasets. Based on the results, we find that the native local rule classifier is generally competitive with the other classifiers. The addition of non-local moves achieves similar results with fewer iterations. Therefore, using specialized or quantum hardware could lead to a significant speedup through the rapid proposal of non-local moves. [ABSTRACT FROM AUTHOR]

The Algorithm Selection Problem (ASP) considers the use of previous knowledge regarding problem features and algorithm performance to recommend the best strategy to solve a previously unseen problem. In the application context, the usual ASP for optimization considers recommending the best heuristics, whenever it faces a new similar problem instance, also known as the Per-Instance ASP. Although ASP for heuristic recommendation is not new, selecting heuristics and also their parameters, or the Per-instance Algorithm Configuration Problem, is still considered a challenging task. This paper investigates the use of meta-learning to recommend six different stochastic local searches and their parameters to solve several instances of permutation flowshop problems. The proposed approach uses several problem features, including fitness landscape metrics, builds the performance database using irace, and trains different multi-label recommendation models on a data set with more than 6000 flowshop problem instances. Experiments show that decision tree-based machine learning models achieve good performance, and the quality of the recommendations is capable of outperforming the state-of-the-art algorithm with tuned configuration. [ABSTRACT FROM AUTHOR]

Scheduling problems are a subclass of combinatorial problems consisting of a set of tasks/activities/jobs to be processed by a set of resources usually to minimize a time criterion. Some optimization methods used to solve these problems are hybridized with knowledge discovery techniques to extract information during the optimization process and enhance it. However, most of these hybrid techniques are custom‐designed and lack generalization. In this paper, a module for knowledge extraction in Stochastic Local Searches is designed, aiming to be problem independent and plugged into optimization methods that relies on multiple Stochastic Local Search replications. The objective is to prune parts of the search space for which the exploration is likely to lead to poor solutions. This is performed through the extraction of high‐quality patterns occurring in locally optimal solutions. Benchmarked on two well‐known scheduling problems, the Job‐shop Problem and the Resource Constrained Project Scheduling Problem, the results show both a speed up in the convergence and the reaching of better local optima solutions. [ABSTRACT FROM AUTHOR]

Grammar‐based automatic algorithm design has been shown to generate stochastic local search algorithms that compete with or outperform state‐of‐the‐art methods. In such systems, algorithms are divided in components and a grammar is used to describe how to properly combine the components to create a working algorithm. In our approach, the grammar is converted into parameters and an automatic parameter configuration tool is used to find the best configuration. This approach allows us to consider and hybridize different metaheuristic templates producing combinations never tested before, but this flexibility leads to a very large configuration space to explore. Is such complexity really needed to achieve state‐of‐the‐art performance? In this paper, we investigate this question by creating grammars that allow the hybridization of stochastic local search algorithms at most two, one, or zero times. We use these grammars to generate algorithms for the three most studied objectives of the permutation flowshop problem: makespan, total completion time, and total tardiness. The generated algorithms are compared using benchmark sets from the literature as well as a quantitative measure of algorithm complexity using a metric based on concept directed acyclic graphs. The experiments show that our system tends to generate hybridized algorithms only when they can provide a substantial performance improvement. On the contrary, when such algorithms do not improve performance, the system generates simpler algorithms regardless of the grammar used. [ABSTRACT FROM AUTHOR]

This article continues the authors' research into cooperation between public and private investors in a resource region. In contrast to previous papers, an attempt is made here to take into account the institutional features of the process of forming the investment climate. To this end, transaction costs are introduced in the model and a mechanism for breach-of-contract risk insurance is formed. In the Russian mineral resource complex, costs and risks of this kind can be very appreciable. This work aims to analyze partnership mechanisms taking into account these circumstances and using the game-theoretic Stackelberg model. Such mechanisms determine the economic policy of the government and play an important role in stimulating private investment. The model is stated as a bilevel mathematical programming problem. Efficient solution algorithms based on metaheuristics are developed. This allows the practical study of the properties of Stackelberg equilibrium with real data. The equilibrium determines the design of the mechanism of economic policy making fully meeting the interests of society. [ABSTRACT FROM AUTHOR]

The Partial Max-SAT (PMSAT) problem is an optimization variant of the well-known Propositional Boolean Satisfiability (SAT) problem. It holds an important place in theory and practice, because a huge number of real-world problems, such as timetabling, planning, routing, bioinformatics, fault diagnosis, etc., could be encoded into it. Stochastic local search (SLS) methods can solve many real-world problems that often involve large-scale instances at reasonable computation costs while delivering good-quality solutions. In this work, we propose a novel SLS algorithm called adaptive variable depth SLS for PMSAT problem solving based on a dynamic local search framework. Our algorithm exploits two algorithmic components of an SLS method: parameter tuning and neighborhood search. Our first contribution is the design of an adaptive parameter tuner that searches for the best parameter setting for each instance by considering its features. The second contribution is a variable depth neighborhood search (VDS) algorithm adopted for PMSAT problem, which our empirical evaluation proves is a more efficient w.r.t. single neighborhood search. We conducted our experiments on the PMSAT benchmarks from MaxSAT Evaluation 2014 to 2019, including more than 3600 instances which have been encoded from a broad range of domains such as verification, optimization, graph theory, automated-reasoning, pseudo Boolean, etc. Our experimental evaluation results show that AVD-SLS solver, which is implemented based on our algorithm, outperforms state-of-the-art PMSAT SLS solvers in most benchmark classes, including random, crafted, and industrial instances. Furthermore, AVD-SLS reports remarkably better results on weighted benchmark, and shows competitive results with several well-known hybrid PMSAT solvers.

Stochastic local search algorithm with configuration check strategy can effectively solve random satisfiability instances, so configuration check strategy is widely used in combinatorial optimization problems. Inspired by this, we proposed an ISSATA algorithm to solve the 3-satisfiability problem. In this algorithm, a new initialization strategy is given, which can assign initial values to variables more efficiently. At the same time, a new variable selection strategy and a new neighbor priority strategy are proposed to improve the performance of selecting flipped variables. Comparative experiments conducted in public datasets show that ISSATA has better solution accuracy and efficiency. [ABSTRACT FROM AUTHOR]

Genetic improvement (GI) uses automated search to improve existing software. It has been successfully used to optimize various program properties, such as runtime or energy consumption, as well as for the purpose of bug fixing. GI typically navigates a space of thousands of patches in search for the program mutation that best improves the desired software property. While genetic programming (GP) has been dominantly used as the search strategy, more recently other search strategies, such as local search, have been tried. It is, however, still unclear which strategy is the most effective and efficient. In this article, we conduct an in-depth empirical comparison of a total of 18 search processes using a set of eight improvement scenarios. Additionally, we also provide new GI benchmarks and we report on new software patches found. Our results show that, overall, local search approaches achieve better effectiveness and efficiency than GP approaches. Moreover, improvements were found in all scenarios (between 15% and 68%). A replication package can be found online: https://github.com/bloa/tevc_2020_artefact. [ABSTRACT FROM AUTHOR]

Classification approaches that allow to extract logical rules such as decision trees are often considered to be more interpretable than neural networks. Also, logical rules are comparatively easy to verify with any possible input. This is an important part in systems that aim to ensure correct operation of a given model. However, for high-dimensional input data such as images, the individual symbols, i.e. pixels, are not easily interpretable. Therefore, rule-based approaches are not typically used for this kind of high-dimensional data. We introduce the concept of first-order convolutional rules, which are logical rules that can be extracted using a convolutional neural network (CNN), and whose complexity depends on the size of the convolutional filter and not on the dimensionality of the input. Our approach is based on rule extraction from binary neural networks with stochastic local search. We show how to extract rules that are not necessarily short, but characteristic of the input, and easy to visualize. Our experiments show that the proposed approach is able to model the functionality of the neural network while at the same time producing interpretable logical rules. Thus, we demonstrate the potential of rule-based approaches for images which allows to combine advantages of neural networks and rule learning.

The wide amount of data in the modern applications available on the Internet make it very complicated to deal with the knowledge behind these data. The data classification task is a useful tool that used to deal with a huge amount of data by classify these data into coherent groups. The data size decreases the performace of the classification technique, especially when contain uninformative data (i.e., irrelevant, noisy). The stochastic local search algorithm is an optimization approaches employed to find the informative data to build the classification model. These methods are used to search for the optimal patterns to construct the classification algorithm. Thus, this research introduces a stochastic local search algorithm for rule induction called Iterated-Miner (Iterated local search-based rule induction). The purpose of the algorithm is to construct classification rules from data. This classification algorithm is inspired by the concepts and principles of stochastic local search and rule induction. The performance of the proposed classifier evaluated with a well-known and state of art classification algorithms called, Ant-Miner, ACO/PSO2, PART FURIA, and ACO/GA on 10 UCI datasets. The results demonstrate that our classifier is superior compare with all classifiers respect to classification accuracy; and the model sizes by our classifier are considerably competitive with those discovered by other classifier. [ABSTRACT FROM AUTHOR]

In today's world, the data generated by many applications are increasing drastically, and finding an optimal subset of features from the data has become a crucial task. The main objective of this review is to analyze and comprehend different stochastic local search algorithms to find an optimal feature subset. Simulated annealing, tabu search, genetic programming, genetic algorithm, particle swarm optimization, artificial bee colony, grey wolf optimization, and bat algorithm, which have been used in feature selection, are discussed. This review also highlights the filter and wrapper approaches for feature selection. Furthermore, this review highlights the main components of stochastic local search algorithms, categorizes these algorithms in accordance with the type, and discusses the promising research directions for such algorithms in future research of feature selection. [ABSTRACT FROM AUTHOR]

Stochastic local search (SLS) methods are heuristic-based algorithms that have gained in popularity for their efficiency and robustness when solving very large and complex problems from various areas of artificial intelligence. This study aims to gain insights into SLS methods for solving the Partial Max-SAT (PMSAT) problem. The PMSAT is an NP-Hard problem, an optimization variant of the Propositional Boolean Satisfiability (SAT) problem, that has importance in theory and practice. Many real-world problems including timetabling, scheduling, planning, routing, and software debugging can be reduced to the PMSAT problem. Modern PMSAT solvers are able to solve practical instances with hundreds of thousands to millions of variables and clauses. However, performance of PMSAT solvers are still limited for solving some benchmark instances. In this paper, we present, investigate, and analyze state-of-the-art SLS methods for solving the PMSAT problem. An experimental evaluation is presented based on the MAX-SAT evaluations from 2014 to 2019. The results of this evaluation study show that the currently best performing SLS methods for the PMSAT problem fall into three categories: distinction-based, configuration checking-based, and dynamic local search methods. Very good performance was reported for the dynamic local search based method. The paper gives a detailed picture of the performance of SLS solvers for the PMSAT problem, aims to improve our understanding of their capabilities and limitations, and identifies future research directions. [ABSTRACT FROM AUTHOR]

The main objective of this paper is to provide a state-of-the-art review, analyze and discuss stochastic local search techniques used for solving hard combinatorial problems. It begins with a short introduction, motivation and some basic notation on combinatorial problems, search paradigms and other relevant features of searching techniques as needed for background. In the following a brief overview of the stochastic local search methods along with an analysis of the state-of-the-art stochastic local search algorithms is given. Finally, the last part of the paper present and discuss some of the most latest trends in application of stochastic local search algorithms in machine learning, data mining and some other areas of science and engineering. We conclude with a discussion on capabilities and limitations of stochastic local search algorithms. [ABSTRACT FROM AUTHOR]

Maximum vertex weight clique problem (MVWCP) and maximum edge weight clique problem (MEWCP) are two significant generalizations of maximum clique problem (MCP), and can be widely used in many real-world applications including molecular biology, broadband network design and pattern recognition. Recently, breakthroughs have been made for solving MVWCP in large graphs, resulting in several state-of-the-art algorithms, such as WLMC, FastWClq and LSCC + BMS. However, less attention has been paid to solving MEWCP in large graphs. In this paper, we present an efficient Stochastic Local Search (SLS) algorithm for MEWCP by combining clique construction, local search and graph reduction, resulting in a new algorithm named ReConSLS. We also propose a new upper bound function for edge weighted graphs which is essential for graph reduction. Extensive experiments on a wide range of large graphs demonstrate that ReConSLS surpasses state-of-the-art SLS competitors on the majority of testing graphs. [ABSTRACT FROM AUTHOR]

We develop a framework for the rigorous analysis of focused stochastic local search algorithms. These algorithms search a state space by repeatedly selecting some constraint that is violated in the current state and moving to a random nearby state that addresses the violation, while (we hope) not introducing many new violations. An important class of focused local search algorithms with provable performance guarantees has recently arisen from algorithmizations of the Lovász local lemma (LLL), a nonconstructive tool for proving the existence of satisfying states by introducing a background measure on the state space. While powerful, the state transitions of algorithms in this class must be, in a precise sense, perfectly compatible with the background measure. In many applications this is a very restrictive requirement, and one needs to step outside the class. Here we introduce the notion of measure distortion and develop a framework for analyzing arbitrary focused stochastic local search algorithms, recovering LLL algorithmizations as the special case of no distortion. Our framework takes as input an arbitrary algorithm of such type and an arbitrary probability measure and shows how to use the measure as a yardstick of algorithmic progress, even for algorithms designed independently of the measure. [ABSTRACT FROM AUTHOR]

Wireless ad hoc and sensor networks play an important role in providing flexible deployment and mobile connectivity for next generation network. Since there is no fixed physical backbone infrastructure, some of the nodes are selected to form a virtual backbone. Efficient algorithms for identifying the Minimum Connected Dominating Set (MCDS) have many practical applications in wireless sensor networks deployment and management. We propose two algorithms in this paper for solving the MCDS problem. The first algorithm called Memetic Algorithm for the MCDS problem, or MA-MCDS shortly. This is a new hybrid algorithm based on genetic algorithm in addition to local search strategies for the MCDS problem. In order to achieve fast performance, MA-MCDS algorithm uses local search and intensification procedures in addition to genetic operations. In the second algorithm, simulated annealing is used to enhance a stochastic local search with the ability to of run away from local solutions. In addition, we present a new objective function that effectively measure the quality of the solutions of our proposed algorithms. Both algorithms are tested using different benchmark test graph sets available in the literature, and shows good results in terms of solution quality. [ABSTRACT FROM AUTHOR]

For the treatment of multi-objective optimization problems (MOPs) sto-chas-tic search algorithms such as multi-objective evolutionary algorithms (MOEAs) are very popular due to their global set based approach. Multi-objective stochastic local search (MOSLS) represents a powerful tool within MOEAs which is crucial for the guidance of the populations' individuals. The success of variation operators in evolutionary algorithms is related to survival chances of their new generated individuals. Though individual feasibility determines directly the survival chances, in MOEAs, regular variation operators do not consider any information from the constraints. Recently, an initial study has been done for unconstrained MOPs revealing that a pressure both toward and along the Pareto front is inherent in MOSLS by which the behavior of many MOEAs in different stages of the search could be explained to a certain extent. In the present paper we go further to study the implications of MOSLS for the constrained case and propose the construction of subspace based movements during the search; we identify how neighborhood samples have to be chosen such that a movement along the Pareto front is achieved, for points near the Pareto set of a given constrained MOP. Next, we present two applications of these insights, namely (i) to explore the behavior of a population based algorithm that is merely using this proposed neighborhood sampling and (ii) to build a specialized mutation operator for effectively explore search regions on constrained MOPs, where the constraints are given explicitly. Numerical results indicate that these ideas yield competitive results in most cases. We conjecture that these insights are valuable for the future design of specialized search operators for memetic algorithms dealing with constrained multi-objective search spaces. [ABSTRACT FROM AUTHOR]

We propose a new model for the formation of a public-private partnership mechanism, formulated as a bilevel Boolean programming problem. We show that this task is ∑2P-hard in both optimistic and pessimistic forms. We develop a stochastic iterative algorithm for solving this problem. We also present computational experiments on real information that demonstrate the capabilities of the proposed approach. [ABSTRACT FROM AUTHOR]

The maximum satisfiability (MAX-SAT) problem is an important NP-hard problem in theory, and has a broad range of applications in practice. Stochastic local search (SLS) is becoming an increasingly popular method for solving MAX-SAT. Recently, a powerful SLS algorithm called CCLS shows efficiency on solving random and crafted MAX-SAT instances. However, the performance of CCLS on solving industrial MAX-SAT instances lags far behind. In this paper, we focus on experimentally analyzing the performance of SLS algorithms for solving industrial MAX-SAT instances. First, we conduct experiments to analyze why CCLS performs poor on industrial instances. Then we propose a new strategy called additive BMS (Best from Multiple Selections) to ease the serious issue. By integrating CCLS and additive BMS, we develop a new SLS algorithm for MAX-SAT called CCABMS, and related experiments indicate the efficiency of CCABMS. Also, we experimentally analyze the effectiveness of initialization methods on SLS algorithms for MAX-SAT, and combine an effective initialization method with CCABMS, resulting in an enhanced algorithm. Experimental results show that our enhanced algorithm performs better than its state-of-the-art SLS competitors on a large number of industrial MAX-SAT instances. [ABSTRACT FROM AUTHOR]

The Maximum Satisfiability (Maximum Satisfiability (MaxSAT)) approach is the choice, and perhaps the only one, to deal with most real-world problems as most of them are unsatisfiable. Thus, the search for a complete and consistent solution to a real-world problem is impractical due to computational and time constraints. As a result, MaxSAT problems and solving techniques are of exceptional interest in the domain of Satisfiability (Satisfiability (SAT)). Our research experimentally investigated the performance gains of extending the most recently developed SAT dynamic Initial Weight assignment technique (InitWeight) to handle the MaxSAT problems. Specifically, we first investigated the performance gains of dynamically assigning the initial weights in the Divide and Distribute Fixed Weights solver (DDFW+Initial Weight for Maximum Satisfiability (DDFW+InitMaxSAT)) over Divide and Distribute Fixed Weights solver (DDFW) when applied to solve a wide range of well-known unweighted MaxSAT problems obtained from DIMACS. Secondly, we compared DDFW+InitMaxSAT’s performance against three known state-of-the-art SAT solving techniques: YalSAT, ProbSAT, and Sparrow. We showed that the assignment of dynamic initial weights increased the performance of DDFW+InitMaxSAT against DDFW by an order of magnitude on the majority of problems and performed similarly otherwise. Furthermore, we showed that the performance of DDFW+InitMaxSAT was superior to the other state-of-the-art algorithms. Eventually, we showed that the InitWeight technique could be extended to handling partial MaxSAT with minor modifications.

Background and Purpose: The restructuring of human resources in an organization is addressed in this paper, because human resource planning is a crucial process in every organization. Here, a strict hierarchical structure of the organization is of concern here, for which a change in a particular class of the structure influences classes that follow it. Furthermore, a quick adaptation of the structure to the desired state is required, where oscillations in transitions between classes are not desired, because they slow down the process of adaptation. Therefore, optimization of such a structure is highly complex, and heuristic methods are needed to approach such problems to address them properly.