Lateness minimization with Tabu search for job shop scheduling problem with sequence dependent setup times

We tackle the job shop scheduling problem with sequence dependent setup times and maximum lateness minimization by means of a tabu search algorithm. We start by defining a disjunctive model for this problem, which allows us to study some properties of the problem. Using these properties we define a new local search neighborhood structure, which is then incorporated into the proposed tabu search algorithm. To assess the performance of this algorithm, we present the results of an extensive experimental study, including an analysis of the tabu search algorithm under different running conditions and a comparison with the state-of-the-art algorithms. The experiments are performed across two sets of conventional benchmarks with 960 and 17 instances respectively. The results demonstrate that the proposed tabu search algorithm is superior to the state-of-the-art methods both in quality and stability. In particular, our algorithm establishes new best solutions for 817 of the 960 instances of the first set and reaches the best known solutions in 16 of the 17 instances of the second set.     

Learning dataset representation for automatic machine learning algorithm selection

The algorithm selection problem is defined as identifying the best-performing machine learning (ML) algorithm for a given combination of dataset, task, and evaluation measure. The human expertise required to evaluate the increasing number of ML algorithms available has resulted in the need to automate the algorithm selection task. Various approaches have emerged to handle the automatic algorithm selection challenge, including meta-learning. Meta-learning is a popular approach that leverages accumulated experience for future learning and typically involves dataset characterization. Existing meta-learning methods often represent a dataset using predefined features and thus cannot be generalized across different ML tasks, or alternatively, learn a dataset’s representation in a supervised manner and therefore are unable to deal with unsupervised tasks. In this study, we propose a novel learning-based task-agnostic method for producing dataset representations. Then, we introduce TRIO, a meta-learning approach, that utilizes the proposed dataset representations to accurately recommend top-performing algorithms for previously unseen datasets. TRIO first learns graphical representations for the datasets, using four tools to learn the latent interactions among dataset instances and then utilizes a graph convolutional neural network technique to extract embedding representations from the graphs obtained. We extensively evaluate the effectiveness of our approach on 337 datasets and 195 ML algorithms, demonstrating that TRIO significantly outperforms state-of-the-art methods for algorithm selection for both supervised (classification and regression) and unsupervised (clustering) tasks.

     

Multi-view constrained clustering with an incomplete mapping between views

Multi-view learning algorithms typically assume a complete bipartite mapping between the different views in order to exchange information during the learning process. However, many applications provide only a partial mapping between the views, creating a challenge for current methods. To address this problem, we propose a multi-view algorithm based on constrained clustering that can operate with an incomplete mapping. Given a set of pairwise constraints in each view, our approach propagates these constraints using a local similarity measure to those instances that can be mapped to the other views, allowing the propagated constraints to be transferred across views via the partial mapping. It uses co-EM to iteratively estimate the propagation within each view based on the current clustering model, transfer the constraints across views, and then update the clustering model. By alternating the learning process between views, this approach produces a unified clustering model that is consistent with all views. We show that this approach significantly improves clustering performance over several other methods for transferring constraints and allows multi-view clustering to be reliably applied when given a limited mapping between the views. Our evaluation reveals that the propagated constraints have high precision with respect to the true clusters in the data, explaining their benefit to clustering performance in both single- and multi-view learning scenarios.     

A comparative study of stochastic optimization methods in electric motor design

The efficiency of universal electric motors that are widely used in home appliances can be improved by optimizing the geometry of the rotor and the stator. Expert designers traditionally approach this task by iteratively evaluating candidate designs and improving them according to their experience. However, the existence of reliable numerical simulators and powerful stochastic optimization techniques make it possible to automate the design procedure. We present a comparative study of six stochastic optimization algorithms in designing optimal rotor and stator geometries of a universal electric motor where the primary objective is to minimize the motor power losses. We compare three methods from the domain of evolutionary computation, generational evolutionary algorithm, steady-state evolutionary algorithm and differential evolution, two particle-based methods, particle-swarm optimization and electromagnetism-like algorithm, and a recently proposed multilevel ant stigmergy algorithm. By comparing their performance, the most efficient method for solving the problem is identified and an explanation of its success is offered.     

Approximate algorithms for the container loading problem

In this paper we develop several algorithms for solving three–dimensional cutting/packing problems. We begin by proposing an adaptation of the approach proposed in Hifi and Ouafi (1997) for solving two–staged unconstrained two–dimensional cutting problems. We show how the algorithm can be polynomially solved for producing a constant approximation ratio. We then extend this algorithm for developing better approximate algorithms. By using hill–climbing strategies, we construct some heuristics which produce a good trade–off between the computational time and the solution quality. The performance of the proposed algorithms is evaluated on different problem instances of the literature, with different sizes and densities (a total of 144 problem instances).     

A memetic algorithm for the capacitated m-ring-star problem

The Capacitated m-Ring-Star Problem (CmRSP) models a network topology design problem in the telecommunications industry. In this paper, we propose to solve this problem using a memetic algorithm that includes a crossover operation, a mutation operation, a local search involving three neighborhood operators, and a population selection strategy that maintains population diversity. Our approach generates the best known solutions for 131 out of 138 benchmark instances, improving on the previous best solutions for 24 of them, and exhibits more advantages on large benchmark instances when compared with the best existing approach. Additionally, all existing algorithms for this problem in literature assume that the underlying graph of the problem instance satisfies the triangle inequality rule; our approach does not require this assumption. We also generated a new set of 36 larger test instances based on a digital data service network price structure to serve as a new benchmark data set for future researchers.     

A new parallel tabu search algorithm for the optimization of the maximum vertex weight clique problem

The efficiency of metaheuristic algorithms depends significantly on the number of fitness value evaluations performed on candidate solutions. In addition to various intelligent techniques used to obtain better results, parallelization of calculations can substantially improve the solutions in cases where the problem is NP-hard and requires many evaluations. This study proposes a new parallel tabu search method for solving the Maximum Vertex Weight Clique Problem (MVWCP) on the Non-Uniform Memory Access (NUMA) architectures using the OpenMP parallel programming paradigm. Achieving scalability in the NUMA architectures presents significant challenges due to the high complexity of their memory systems, which can lead to performance loss. However, our proposed Tabu-NUMA algorithm provides up to $18\times$ speed-up with 64 cores for ten basic problem instances in DIMACS-W and BHOSLIB-W benchmarks. And it improves the performance of the serial Multi Neighborhood Tabu Search (MN/TS) algorithm for 38 problem instances in DIMACS-W and BHOSLIB-W benchmarks. We further evaluate our algorithm on larger datasets with thousands of edges and vertices from Network Data Repository benchmark problem instances, and we report significant improvements in terms of speed up. Our results confirm that the Tabu-NUMA algorithm is among the best recent algorithms for solving MVWCP on the NUMA architectures.     

Parallelizing Feature Selection

Classification is a key problem in machine learning/data mining. Algorithms for classification have the ability to predict the class of a new instance after having been trained on data representing past experience in classifying instances. However, the presence of a large number of features in training data can hurt the classification capacity of a machine learning algorithm. The Feature Selection problem involves discovering a subset of features such that a classifier built only with this subset would attain predictive accuracy no worse than a classifier built from the entire set of features. Several algorithms have been proposed to solve this problem. In this paper we discuss how parallelism can be used to improve the performance of feature selection algorithms. In particular, we present, discuss and evaluate a coarse-grained parallel version of the feature selection algorithm FortalFS. This algorithm performs well compared with other solutions and it has certain characteristics that makes it a good candidate for parallelization. Our parallel design is based on the master--slave design pattern. Promising results show that this approach is able to achieve near optimum speedups in the context of Amdahl's Law.     

On the performance of multiple-objective genetic local search onthe 0/1 knapsack problem - a comparative experiment

Multiple-objective metaheuristics, e.g., multiple-objective evolutionary algorithms, constitute one of the most active fields of multiple-objective optimization. Since 1985, a significant number of different methods have been proposed. However, only few comparative studies of the methods were performed on large-scale problems. We continue two comparative experiments on the multiple-objective 0/1 knapsack problem reported in the literature. We compare the performance of two multiple-objective genetic local search (MOGLS) algorithms to the best performers in the previous experiments using the same test instances. The results of our experiment indicate that our MOGLS algorithm generates better approximations to the nondominated set in the same number of functions evaluations than the other algorithms     

Optimization strategies for discrete multi-material stiffness optimization

Design of composite laminated lay-ups are formulated as discrete multi-material selection problems. The design problem can be modeled as a non-convex mixed-integer optimization problem. Such problems are in general only solvable to global optimality for small to moderate sized problems. To attack larger problem instances we formulate convex and non-convex continuous relaxations which can be solved using gradient based optimization algorithms. The convex relaxation yields a lower bound on the attainable performance. The optimal solution to the convex relaxation is used as a starting guess in a continuation approach where the convex relaxation is changed to a non-convex relaxation by introduction of a quadratic penalty constraint whereby intermediate-valued designs are prevented. The minimum compliance, mass constrained multiple load case problem is formulated and solved for a number of examples which numerically confirm the sought properties of the new scheme in terms of convergence to a discrete solution.     

A problem reduction based approach to discrete optimization algorithm design

The paper presents a novel approach to formal algorithm design for a typical class of discrete optimization problems. Using a concise set of program calculation rules, our approach reduces a problem into subproblems with less complexity based on function decompositions, constructs the problem reduction graph that describes the recurrence relations between the problem and subproblems, from which a provably correct algorithm can be mechanically derived. Our approach covers a large variety of algorithms and bridges the relationship between conventional methods for designing efficient algorithms (including dynamic programming and greedy) and some effective methods for coping with intractability (including approximation and parameterization).     

Multiobjective firefly algorithm for continuous optimization

Design problems in industrial engineering often involve a large number of design variables with multiple objectives, under complex nonlinear constraints. The algorithms for multiobjective problems can be significantly different from the methods for single objective optimization. To find the Pareto front and non-dominated set for a nonlinear multiobjective optimization problem may require significant computing effort, even for seemingly simple problems. Metaheuristic algorithms start to show their advantages in dealing with multiobjective optimization. In this paper, we extend the recently developed firefly algorithm to solve multiobjective optimization problems. We validate the proposed approach using a selected subset of test functions and then apply it to solve design optimization benchmarks. We will discuss our results and provide topics for further research.     

A hybrid TP+PLS algorithm for bi-objective flow-shop scheduling problems

This paper presents a new, carefully designed algorithm for five bi-objective permutation flow shop scheduling problems that arise from the pairwise combinations of the objectives (i) makespan, (ii) the sum of the completion times of the jobs, and (iii) both, the weighted and non-weighted total tardiness of all jobs. The proposed algorithm combines two search methods, two-phase local search and Pareto local search, which are representative of two different, but complementary, paradigms for multi-objective optimization in terms of Pareto-optimality. The design of the hybrid algorithm is based on a careful experimental analysis of crucial algorithmic components of these two search methods. We compared our algorithm to the two best algorithms identified, among a set of 23 candidate algorithms, in a recent review of the bi-objective permutation flow-shop scheduling problem. We have reimplemented carefully these two algorithms in order to assess the quality of our algorithm. The experimental comparison in this paper shows that the proposed algorithm obtains results that often dominate the output of the two best algorithms from the literature. Therefore, our analysis shows without ambiguity that the proposed algorithm is a new state-of-the-art algorithm for the bi-objective permutation flow-shop problems studied in this paper.     

A restart local search algorithm for solving maximum set k-covering problem

The maximum set k-covering problem (MKCP) is a famous combinatorial optimization problem with widely many practical applications. In our work, we design a restart local search algorithm for solving MKCP, which is called RNKC. This algorithm effectively makes use of several advanced ideas deriving from the random restart mechanism and the neighborhood search method. RNKC designs a new random restart method to deal with the serious cycling problem of local search algorithms. Thanks to the novel neighborhood search method that allows a neighborhood exploration of as many feasible search areas as possible, the RNKC can obtain some greatly solution qualities. Comprehensive results on the classical instances show that the RNKC algorithm competes very favorably with a famous commercial solver CPLEX. In particular, it discovers some improved and great results and matches the same solution quality for some instances.

     

A heuristic algorithm based on Monte Carlo methods for the Rural Postman Problem

In Routing Problems the aim is to determine a minimum cost traversal over a graph satisfying some specified constraints. Most of them are NP-hard problems and many different heuristic solution algorithms have been proposed. The name Monte Carlo, MC, applies to a set of heuristic procedures with the common feature of using random numbers to simulate a given process. MC approach has not been applied to the framework of Routing Problems in the literature. The purpose of this paper is to demonstrate that MC methods could be useful in implementing heuristic algorithms for Routing Problems. In particular, we design an efficient MC heuristic algorithm for the well known Rural Postman Problem (RPP), for which we have a set of instances with known optimal solution taken from the literature.The Rural Postman Problem (RPP) consists of finding a minimum cost traversal of a specified arc subset of a graph. Given that the RPP is a NP-hard problem, heuristic algorithms are interesting both to handle large size instances and to provide upper bounds that could be used in branch and cut procedures. In this paper we propose a heuristic algorithm for the RPP based on Monte Carlo methods. We simulate a vehicle travelling randomly over the graph, jumping from one node to another on the basis of certain probabilities. Monte Carlo methods provide a simple approach to many different Routing Problems and they are easily implemented in a computer code. The application of this algorithm to a set of RPP instances taken from the literature demonstrates that, using the appropriate probabilities, they are also efficient.     

The SR-GCWS hybrid algorithm for solving the capacitated vehicle routing problem

The capacitated vehicle routing problem (CVRP) is a well known problem which has long been tackled by researchers for several decades now, not only because of its potential applications but also due to the fact that CVRP can be used to test the efficiency of new algorithms and optimization methods. The objective of our work is to present SR-GCWS, a hybrid algorithm that combines a CVRP classical heuristic with Monte Carlo simulation using state-of-the-art random number generators. The resulting algorithm is tested against some well-known benchmarks. In most cases, our approach is able to compete or even outperform much more complex algorithms, which is especially interesting if we consider that our algorithm does not require any previous parameter fine-tuning or set-up process. Moreover, our algorithm has been able to produce high-quality solutions almost in real-time for most tested instances. Another important feature of the algorithm worth mentioning is that it uses a randomized constructive heuristic, capable of generating hundreds or even thousands of alternative solutions with different properties. These alternative solutions, in turn, can be really useful for decision-makers in order to satisfy their utility functions, which are usually unknown by the modeler. The presented methodology may be a fine framework for the development of similar algorithms for other complex combinatorial problems in the routing arena as well as in some other research fields.     

Global optima for the Zhou–Rozvany problem

We consider the minimum compliance topology design problem with a volume constraint and discrete design variables. In particular, our interest is to provide global optimal designs to a challenging benchmark example proposed by Zhou and Rozvany. Global optimality is achieved by an implementation of a local branching method in which the subproblems are solved by a special purpose nonlinear branch-and-cut algorithm. The convergence rate of the branch-and-cut method is improved by strengthening the problem formulation with valid linear inequalities and variable fixing techniques. With the proposed algorithms, we find global optimal designs for several values on the available volume. These designs can be used to validate other methods and heuristics for the considered class of problems.     

Generation of Particle Swarm Optimization algorithms: An experimental study using Grammar-Guided Genetic Programming

Particle Swarm Optimization (PSO) is largely used to solve optimization problems effectively. Nonetheless, the PSO performance depends on the fine tuning of different parameters. To make the algorithm design process more independent from human intervention, some researchers have treated this task as an optimization problem. Grammar-Guided Genetic Programming (GGGP) algorithms, in particular, have been widely studied and applied in the context of algorithm optimization. GGGP algorithms produce customized designs based on a set of production rules defined in the grammar, differently from methods that simply select designs in a pre-defined limited search space. Although GGGP algorithms have been largely used in other contexts, they have not been deeply investigated in the generation of PSO algorithms. Thus, this work applies GGGP algorithms in the context of PSO algorithm design problem. Herein, we performed an experimental study comparing different GGGP approaches for the generation of PSO algorithms. The main goal is to perform a deep investigation aiming to identify pros and cons of each approach in the current task. In the experiments, a comparison between a tree-based GGGP approach and commonly used linear GGGP approaches for the generation of PSO algorithms was performed. The results showed that the tree-based GGGP produced better algorithms than the counterparts. We also compared the algorithms generated by the tree-based technique to state-of-the-art optimization algorithms, and it achieved competitive results.     

A graph-based immune-inspired constraint satisfaction search

We propose an artificial immune algorithm to solve constraint satisfaction problems (CSPs). Recently, bio-inspired algorithms have been proposed to solve CSPs. They have shown to be efficient in solving hard problem instances. Given that recent publications indicate that immune-inspired algorithms offer advantages to solve complex problems, our main goal is to propose an efficient immune algorithm which can solve CSPs. We have calibrated our algorithm using relevance estimation and value calibration (REVAC), which is a new technique recently introduced to find the parameter values for evolutionary algorithms. The tests were carried out using randomly generated binary constraint satisfaction problems and instances of the three-colouring problem with different constraint networks. The results suggest that the technique may be successfully applied to solve CSPs.