Integrating local search techniques into mixed integer programming

We survey the main results of the authors PhD thesis that was supervised by Claude Le Pape (ILOG, France) and Philippe Michelon (Université dAvignon, France) and has been defended in June 2004. The dissertation is written in French and is available from the author. It introduces several strategies for integrating local search techniques into mixed integer programming, with an emphasis on generic algorithms.Received: June 2004, MSC classification: 90C11, 90C59     

An evolutionary algorithm with the partial sequential forward floating search mutation for large-scale feature selection problems

Several meta-heuristic algorithms, such as evolutionary algorithms (EAs) and genetic algorithms (GAs), have been developed for solving feature selection problems due to their efficiency for searching feature subset spaces in feature selection problems. Recently, hybrid GAs have been proposed to improve the performance of conventional GAs by embedding a local search operation, or sequential forward floating search mutation, into the GA. Existing hybrid algorithms may damage individuals’ genetic information obtained from genetic operations during the local improvement procedure because of a sequential process of the mutation operation and the local improvement operation. Another issue with a local search operation used in the existing hybrid algorithms is its inappropriateness for large-scale problems. Therefore, we propose a novel approach for solving large-sized feature selection problems, namely, an EA with a partial sequential forward floating search mutation (EAwPS). The proposed approach integrates a local search technique, that is, the partial sequential forward floating search mutation into an EA method. Two algorithms, EAwPS-binary representation (EAwPS-BR) for medium-sized problems and EAwPS-integer representation (EAwPS-IR) for large-sized problems, have been developed. The adaptation of a local improvement method into the EA speeds up the search and directs the search into promising solution areas. We compare the performance of the proposed algorithms with other popular meta-heuristic algorithms using the medium- and large-sized data sets. Experimental results demonstrate that the proposed EAwPS extracts better features within reasonable computational times.     

Interpretable machine learning for imbalanced credit scoring datasets

The class imbalance problem is common in the credit scoring domain, as the number of defaulters is usually much less than the number of non-defaulters. To date, research on investigating the class imbalance problem has mainly focused on indicating and reducing the adverse effect of the class imbalance on the predictive accuracy of machine learning techniques, while the impact of that on machine learning interpretability has never been studied in the literature. This paper fills this gap by analysing how the stability of Local Interpretable Model-agnostic Explanations (LIME) and SHapley Additive exPlanations (SHAP), two popular interpretation methods, are affected by class imbalance. Our experiments use 2016–2020 UK residential mortgage data collected from European Datawarehouse. We evaluate the stability of LIME and SHAP on datasets of progressively increased class imbalance. The results show that interpretations generated from LIME and SHAP are less stable as the class imbalance increases, which indicates that the class imbalance does have an adverse effect on machine learning interpretability. To check the robustness of our outcomes, we also analyse two open-source credit scoring datasets and we obtain similar results.     

A memetic algorithm for job shop scheduling using a critical-path-based local search heuristic

In this article, a new memetic algorithm has been proposed to solve job shop scheduling problems (JSSPs). The proposed method is a genetic-algorithm-based approach combined with a local search heuristic. The proposed local search heuristic is based on critical operations. It removes the critical operations and reassigns them to a new position to improve the fitness value of the schedule. Moreover, in this article, a new fitness function is introduced for JSSPs. The new fitness function called priority-based fitness function is defined in three priority levels to improve the selection procedure. To show the generality of our proposed method, we apply it to three different types of job scheduling problems including classical, flexible and multi-objective flexible JSSPs. The experiment results show the efficiency of the proposed fitness function. In addition, the results show that incorporating local search not only offers better solutions but also improves the convergence rate. Compared to the state-of-the-art algorithms, the proposed method outperforms the existing methods in classical JSSPs and offers competitive solutions in other types of scheduling problems.     

Local search intensified: Very large-scale variable neighborhood search for the multi-resource generalized assignment problem

We introduce a heuristic for the Multi-Resource Generalized Assignment Problem (MRGAP) based on the concepts of Very Large-Scale Neighborhood Search and Variable Neighborhood Search. The heuristic is a simplified version of the Very Large-Scale Variable Neighborhood Search for the Generalized Assignment Problem. Our algorithm can be viewed as a k-exchange heuristic; but unlike traditional k-exchange algorithms, we choose larger values of k resulting in neighborhoods of very large size with high probability. Searching this large neighborhood (approximately) amounts to solving a sequence of smaller MRGAPs either by exact algorithms or by heuristics. Computational results on benchmark test problems are presented. We obtained improved solutions for many instances compared to some of the best known heuristics for the MRGAP within reasonable running time. The central idea of our heuristic can be used to develop efficient heuristics for other hard combinatorial optimization problems as well.     

A new memetic algorithm based on cellular learning automata for solving the vertex coloring problem

Vertex coloring problem is a combinatorial optimization problem in graph theory in which a color is assigned to each vertex of graph such that no two adjacent vertices have the same color. In this paper a new hybrid algorithm which is obtained from combination of cellular learning automata (CLA) and memetic algorithm (MA) is proposed for solving the vertex coloring problem. CLA is an effective probabilistic learning model combining cellular automata and learning automaton (LA). Irregular CLA (ICLA) is a generalization of CLA in which the restriction of rectangular grid structure in CLA is removed. The proposed algorithm is based on the irregular open CLA (IOCLA) that is an extension of ICLA in which the evolution of CLA is influenced by both local and global environments. Similar to other IOCLA-based algorithms, in the proposed algorithm, local environment is constituted by neighboring LAs of any cell and the global environment consists of a pool of memes in which each meme corresponds to a certain local search method. Each meme is represented by a set of LAs from which the history of the corresponding local search method can be extracted. To show the superiority of the proposed algorithm over some well-known algorithms, several computer experiments have been conducted. The results show that the proposed algorithm performs better than other methods in terms of running time of algorithm and the required number of colors.     

A nonmonotone trust-region line search method for large-scale unconstrained optimization

We consider an efficient trust-region framework which employs a new nonmonotone line search technique for unconstrained optimization problems. Unlike the traditional nonmonotone trust-region method, our proposed algorithm avoids resolving the subproblem whenever a trial step is rejected. Instead, it performs a nonmonotone Armijo-type line search in direction of the rejected trial step to construct a new point. Theoretical analysis indicates that the new approach preserves the global convergence to the first-order critical points under classical assumptions. Moreover, superlinear and quadratic convergence are established under suitable conditions. Numerical experiments show the efficiency and effectiveness of the proposed approach for solving unconstrained optimization problems.     

Dual subgradient algorithms for large-scale nonsmooth learning problems

“Classical” First Order (FO) algorithms of convex optimization, such as Mirror Descent algorithm or Nesterov’s optimal algorithm of smooth convex optimization, are well known to have optimal (theoretical) complexity estimates which do not depend on the problem dimension. However, to attain the optimality, the domain of the problem should admit a “good proximal setup”. The latter essentially means that (1) the problem domain should satisfy certain geometric conditions of “favorable geometry”, and (2) the practical use of these methods is conditioned by our ability to compute at a moderate cost proximal transformation at each iteration. More often than not these two conditions are satisfied in optimization problems arising in computational learning, what explains why proximal type FO methods recently became methods of choice when solving various learning problems. Yet, they meet their limits in several important problems such as multi-task learning with large number of tasks, where the problem domain does not exhibit favorable geometry, and learning and matrix completion problems with nuclear norm constraint, when the numerical cost of computing proximal transformation becomes prohibitive in large-scale problems. We propose a novel approach to solving nonsmooth optimization problems arising in learning applications where Fenchel-type representation of the objective function is available. The approach is based on applying FO algorithms to the dual problem and using the accuracy certificates supplied by the method to recover the primal solution. While suboptimal in terms of accuracy guaranties, the proposed approach does not rely upon “good proximal setup” for the primal problem but requires the problem domain to admit a Linear Optimization oracle—the ability to efficiently maximize a linear form on the domain of the primal problem.     

A two-phase tabu search based evolutionary algorithm for the maximum diversity problem

In this paper, we study the maximum diversity problem (MDP) which is equivalent to the quadratic unconstrained binary optimization (QUBO) problem with cardinality constraint. The MDP aims to select a subset of elements with given cardinality such that the sum of pairwise distances between any two elements in the selected subset is maximized. For solving this computationally challenging problem, we propose a two-phase tabu search based evolutionary algorithm (TPTS/EA), which integrates several distinguishing features to ensure the diversity and the quality of the evolution, such as a two-phase tabu search algorithm which consists of a dynamic candidate list (DCL) strategy-based traditional tabu search in the first phase and a solution-based tabu search procedure to refine the search in the second phase, and two path-relinking based recombination operators to generate new offspring solutions. Tested on three sets of totally 140 public instances in the literature, the study demonstrates the efficacy of the proposed TPTS/EA algorithm in terms of both solution quality and computational efficiency. Specifically, our proposed TPTS/EA algorithm is able to improve the previous best known results for 2 instances, while matching the previous best-known solutions for 130 instances. We also provide experimental evidences to highlight the beneficial effect of several important components in our TPTS/EA algorithm.     

A memetic algorithm based on multiple learning procedures for global optimal design of composite structures

The mechanical properties of composite structures are sensitive to the choice of the material systems, the distribution of laminates on the structure, and the sizing at the laminate level. This sensitivity depends on many variables. To overcome the difficulties in attaining a global solution for the optimisation problem of composite structures, a new strategy is proposed based on the hybridisation of the memetic algorithm (MA) and the selfish gene (SG) algorithm. Instead of a local search, as performed in MAs, the selfish gene (SG) theory is applied, which follows a different learning scheme in which the conventional population of the individuals is replaced by a virtual population of alleles. The proposed approach, which is called the memetic-based selfish gene algorithm (MA + SG), is a mixed model that applies multiple learning procedures to explore the synergy of different cultural transmission rules in the evolutionary process. The principal aspects of the approach are as follows: co-evolution of multiple populations, species conservation, migration rules, self-adaptive multiple crossovers, local search in hybrid crossover with local genetic improvements, controlled mutation, individual age control, and feature-based allele statistical analysis. To discuss the capabilities of the proposed approach, numerical examples are represented to compare the results of MA + SG with those obtained using genetic algorithms (GA) and MA. The numerical results of the comparison tests showed that the GA and the MA maintained long periods without the evolution of the best-fitted individual/solutions. This behaviour during evolution is associated with the slow maturation of the elite group of populations in the GA and MA approaches. This behaviour is avoided when the MA + SG proposed approach is used with computational cost benefits.     

Improving the scalability of rule-based evolutionary learning

Evolutionary learning techniques are comparable in accuracy with other learning methods such as Bayesian Learning, SVM, etc. These techniques often produce more interpretable knowledge than, e.g. SVM; however, efficiency is a significant drawback. This paper presents a new representation motivated by our observations that Bioinformatics and Systems Biology often give rise to very large-scale datasets that are noisy, ambiguous and usually described by a large number of attributes. The crucial observation is that, in the most successful rules obtained for such datasets, only a few key attributes (from the large number of available ones) are expressed in a rule, hence automatically discovering these few key attributes and only keeping track of them contributes to a substantial speed up by avoiding useless match operations with irrelevant attributes. Thus, in effective terms this procedure is performing a fine-grained feature selection at a rule-wise level, as the key attributes may be different for each learned rule. The representation we propose has been tested within the BioHEL machine learning system, and the experiments performed show that not only the representation has competent learning performance, but that it also manages to reduce considerably the system run-time. That is, the proposed representation is up to 2–3 times faster than state-of-the-art evolutionary learning representations designed specifically for efficiency purposes.     

A memetic algorithm for the team orienteering problem

The team orienteering problem (TOP) is a generalization of the orienteering problem. A limited number of vehicles is available to visit customers from a potential set. Each vehicle has a predefined running-time limit, and each customer has a fixed associated profit. The aim of the TOP is to maximize the total collected profit. In this paper we propose a simple hybrid genetic algorithm using new algorithms dedicated to the specific scope of the TOP: an Optimal Split procedure for chromosome evaluation and local search techniques for mutation. We have called this hybrid method a memetic algorithm for the TOP. Computational experiments conducted on standard benchmark instances clearly show our method to be highly competitive with existing ones, yielding new improved solutions in at least 5 instances.     

Decentralized operation strategies for an integrated building energy system using a memetic algorithm

The emerging technology in net-zero building and smart grids drives research moving from centralized operation decisions on a single building to decentralized decisions on a group of buildings, termed a building cluster which shares energy resources locally and globally. However, current research has focused on developing an accurate simulation of single building energy usage which limits its application to building clusters as scenarios such as energy sharing and competition cannot be modeled and studied. We hypothesize that the study of energy usage for a group of buildings instead of one single building will result in a cost effective building system which in turn will be resilient to power disruption. To this end, this paper develops a decision model based on a building cluster simulator with each building modeled by energy consumption, storage and generation sub modules. Assuming each building is interested in minimizing its energy cost, a bi-level operation decision framework based on a memetic algorithm is proposed to study the tradeoff in energy usage among the group of buildings. Two additional metrics, measuring the comfort level and the degree of dependencies on the power grid are introduced for the analysis. The experimental result demonstrates that the proposed framework is capable of deriving the Pareto solutions for the building cluster in a decentralized manner. The Pareto solutions not only enable multiple dimensional tradeoff analysis, but also provide valuable insight for determining pricing mechanisms and power grid capacity.     

Stochastic local search for large-scale instances of the haplotype inference problem by pure parsimony

Haplotype Inference is a challenging problem in bioinformatics that consists in inferring the basic genetic constitution of diploid organisms on the basis of their genotype. This information allows researchers to perform association studies for the genetic variants involved in diseases and the individual responses to therapeutic agents. A notable approach to the problem is to encode it as a combinatorial problem (under certain hypotheses, such as the pure parsimony criterion) and to solve it using off-the-shelf combinatorial optimization techniques. The main methods applied to Haplotype Inference are either simple greedy heuristic or exact methods (Integer Linear Programming, Semidefinite Programming, SAT and pseudo-boolean encoding) that, at present, are adequate only for moderate size instances. In this paper, we present and discuss an approach based on the combination of local search metaheuristics and a reduction procedure based on an analysis of the problem structure. Some relevant design issues are first described, then a family of local search metaheuristics is defined to tackle the Haplotype Inference. Results on common Haplotype Inference benchmarks show that the approach achieves a good trade-off between solution quality and execution time.     

A quantum-behaved evolutionary algorithm based on the Bloch spherical search

In order to enhance the optimization ability of the quantum evolutionary algorithms, a new quantum-behaved evolutionary algorithm is proposed. In this algorithm, the search mechanism is established based on the Bloch sphere. First, the individuals are expressed by qubits described on the Bloch sphere, then the rotation axis is established by Pauli matrixes, and the evolution search is realized by rotating qubits on the Bloch sphere about the rotating axis. In order to avoid premature convergence, the mutation of individuals is achieved by the Hadamard gates. Such rotation can make the current qubit approximate the target qubit along with the great circle on the Bloch sphere, which can accelerate optimization process. Taking the function extreme value optimization as an example, the experimental results show that the proposed algorithm is obviously superior to other similar algorithms.     

Reinforcement learning enhanced multi-neighborhood tabu search for the max-mean dispersion problem

This paper presents a highly effective reinforcement learning enhancement of multi-neighborhood tabu search for the max-mean dispersion problem. The reinforcement learning component uses the Q-learning mechanism that incorporates the accumulated feedback information collected from the actions performed during the search to guide the generation of diversified solutions. The tabu search component employs 1-flip and reduced 2-flip neighborhoods to collaboratively perform the neighborhood exploration for attaining high-quality local optima. A learning automata method is integrated in tabu search to adaptively determine the probability of selecting each neighborhood. Computational experiments on 80 challenging benchmark instances demonstrate that the proposed algorithm is favorably competitive with the state-of-the-art algorithms in the literature, by finding new lower bounds for 3 instances and matching the best known results for the other instances. Key elements and properties are also analyzed to disclose the source of the benefits of our integration of learning mechanisms and tabu search.     

A memetic algorithm for the inventory routing problem

Journal of Heuristics - In this article, we study an Inventory Routing Problem with deterministic customer demand in a two-tier supply chain. The supply chain network consists of a supplier using a...     

A compromised large-scale neighborhood search heuristic for capacitated air cargo loading planning

Cost effectiveness is central to the air freight forwarders. In this work, we study how an air freight forwarder should plan its cargo loading in order to minimize the total freight cost given a limited number of rented containers. To solve the problem efficiently for practical implementation, we propose a new large-scale neighborhood search heuristic. The proposed large-scale neighborhood relaxes the subset-disjoint restriction made in the existing literature; the relaxation risks a possibility of infeasible exchanges while at the same time it avoids the potentially large amount of checking effort required to enforce the subset-disjoint restriction. An efficient procedure is then used to search for improvement in the neighborhood. We have also proposed a subproblem to address the difficulties caused by the fixed charges. The compromised large-scale neighborhood (CLSN) search heuristic has shown stably superior performance when compared with the traditional large-scale neighborhood search and the mixed integer programming model.     

A multi-start evolutionary local search for the one-commodity pickup and delivery traveling salesman problem

Annals of Operations Research - This article addresses the one-commodity pickup and delivery traveling salesman problem (1-PDTSP), which is a generalization of the well-known traveling salesman...