A filter-and-fan algorithm for the capacitated minimum spanning tree problem

The capacitated minimum spanning tree (CMST) is a notoriously difficult problem in combinatorial optimization. Extensive investigation has been devoted to developing efficient algorithms to find optimal or near-optimal solutions. This paper proposes a new CMST heuristic algorithm that effectively combines the classical node-based and tree-based neighborhoods embodied in a filter-and-fan (F&F) approach, a local search procedure that generates compound moves in a tree search fashion. The overall algorithm is guided by a multi-level oscillation strategy used to trigger each type of neighborhood while allowing the search to cross feasibility boundaries. Computational results carried out on a standard set of 135 benchmark problems show that a simple F&F design competes effectively with prior CMST metaheuristics, rivaling the best methods, which are significantly more complex.     

Rough‐fuzzy quadratic minimum spanning tree problem

A quadratic minimum spanning tree problem determines a minimum spanning tree of a network whose edges are associated with linear and quadratic weights. Linear weights represent the edge costs whereas the quadratic weights are the interaction costs between a pair of edges of the graph. In this study, a bi‐objective rough‐fuzzy quadratic minimum spanning tree problem has been proposed for a connected graph, where the linear and the quadratic weights are represented as rough‐fuzzy variables. The proposed model is formulated by using rough‐fuzzy chance‐constrained programming technique. Subsequently, three related theorems are also proposed for the crisp transformation of the proposed model. The crisp equivalent models are solved with a classical multi‐objective solution technique, the epsilon‐constraint method and two multi‐objective evolutionary algorithms: (a) nondominated sorting genetic algorithm II (NSGA‐II) and (b) multi‐objective cross‐generational elitist selection, heterogeneous recombination, and cataclysmic mutation (MOCHC) algorithm. A numerical example is provided to illustrate the proposed model when solved with different methodologies. A sensitivity analysis of the example is also performed at different confidence levels. The performance of NSGA‐II and MOCHC are analysed on five randomly generated instances of the proposed model. Finally, a numerical illustration of an application of the proposed model is also presented in this study.     

Variations of the maximum leaf spanning tree problem for bipartite graphs

The maximum leaf spanning tree problem is known to be NP-complete. In [M.S. Rahman, M. Kaykobad, Complexities of some interesting problems on spanning trees, Inform. Process. Lett. 94 (2005) 93-97], a variation on this problem was posed. This variation restricts the problem to bipartite graphs and asks, for a fixed integer K, whether or not the graph contains a spanning tree with at least K leaves in one of the partite sets. We show not only that this problem is NP-complete, but that it remains NP-complete for planar bipartite graphs of maximum degree 4. We also consider a generalization of a related decision problem, which is known to be polynomial-time solvable. We show the problem is still polynomial-time solvable when generalized to weighted graphs.     

A GRASP with path‐relinking and restarts heuristic for the prize‐collecting generalized minimum spanning tree problem

Given a graph with its vertex set partitioned into a set of groups, nonnegative costs associated to its edges, and nonnegative prizes associated to its vertices, the prize‐collecting generalized minimum spanning tree problem consists in finding a subtree of this graph that spans exactly one vertex of each group and minimizes the sum of the costs of the edges of the tree less the prizes of the selected vertices. It is a generalization of the NP‐hard generalized minimum spanning tree optimization problem. We propose a GRASP (greedy randomized adaptive search procedure) heuristic for its approximate solution, incorporating path‐relinking for search intensification and a restart strategy for search diversification. The hybridization of the GRASP with path‐relinking and restarts heuristic with a data mining strategy that is applied along with the GRASP iterations, after the elite set is modified and becomes stable, contributes to making the heuristic more robust. The computational experiments show that the heuristic developed in this work found very good solutions for test problems with up to 439 vertices. All input data for the test instances and detailed numerical results are made available from Mendeley Data.     

Minimum common string partition: on solving large‐scale problem instances

Minimum common string partition is an NP‐hard combinatorial optimization problem from the bioinformatics field. The current state‐of‐the‐art algorithm is a hybrid technique known as construct, merge, solve, and adapt (CMSA). This algorithm combines two main algorithmic components: generating solutions in a probabilistic way and solving reduced subinstances obtained from the tackled problem instances, if possible, to optimality. However, the CMSA algorithm was not intended for application to very large problem instances. Therefore, in this paper we present a technique that makes CMSA, and other available algorithms for this problem, applicable to problem instances that are about one order of magnitude larger than the largest problem instances considered so far. Moreover, a reduced variable neighborhood search (RVNS) for solving the tackled problem, based on integer programming, is introduced. The experimental results show that the modified CMSA algorithm is very strong for problem instances based on rather small alphabets. With growing alphabet size, it turns out that RVNS has a growing advantage over CMSA.     

A novel local search algorithm with configuration checking and scoring mechanism for the set k‐covering problem

The set k‐covering problem, an extension of the classical set covering problem, is an important NP‐hard combinatorial optimization problem with extensive applications, including computational biology and wireless network. The aim of this paper is to design a new local search algorithm to solve this problem. First, to overcome the cycling problem in local search, the set k‐covering configuration checking (SKCC) strategy is proposed. Second, we use the cost scheme of elements to define the scoring mechanism so that our algorithm can find different possible good‐quality solutions. Having combined the SKCC strategy with the scoring mechanism, a subset selection strategy is designed to decide which subset should be selected as a candidate solution component. After that, a novel local search framework, as we call DLL_ccsm (diversion local search based on configuration checking and scoring mechanism), is proposed. DLL_ccsm is evaluated against two state‐of‐the‐art algorithms. The experimental results show that DLL_ccsm performs better than its competitors in terms of solution quality in most classical instances.     

A biased random-key genetic algorithm for the capacitated minimum spanning tree problem

This paper focuses on the capacitated minimum spanning tree (CMST) problem. Given a central processor and a set of remote terminals with specified demands for traffic that must flow between the central processor and terminals, the goal is to design a minimum cost network to carry this demand. Potential links exist between any pair of terminals and between the central processor and the terminals. Each potential link can be included in the design at a given cost. The CMST problem is to design a minimum-cost network connecting the terminals with the central processor so that the flow on any arc of the network is at most Q. A biased random-key genetic algorithm (BRKGA) is a metaheuristic for combinatorial optimization which evolves a population of random vectors that encode solutions to the combinatorial optimization problem. This paper explores several solution encodings as well as different strategies for some steps of the algorithm and finally proposes a BRKGA heuristic for the CMST problem. Computational experiments are presented showing the effectiveness of the approach: Seven new best-known solutions are presented for the set of benchmark instances used in the experiments.     

An evolutionary implicit enumeration procedure for solving the resource‐constrained project scheduling problem

This paper presents a procedure for solving the resource‐constrained project scheduling problem. It consists of an implicit enumeration module and a genetic algorithm. If the procedure is provided access to all of its required computational resources of the problem at hand, it guarantees the optimality of the produced solution. In contrast, and in the case of limited access to computational resources, the procedure gradually moves the root of the search‐tree downward, and consequently prunes part of the search space, trading speed with precision effectively. In the cases where speed has been traded with precision, and the guarantee of optimality has been lost, the final schedule created by the implicit enumeration module is used as a template whose modified instances fill an initial pool of a genetic algorithm to improve the proposed solution. The procedure has been applied to 2040 benchmark instances. The results are promising; whereas for all small‐ and some medium‐sized instances, the procedure has found and guaranteed optimal solutions, for other instances, whose optimal solutions cannot be guaranteed within the limit of computational resources, it has produced high‐quality solutions.     

Variable neighborhood search algorithms for the vehicle routing problem with two‐dimensional loading constraints and mixed linehauls and backhauls

In this paper, we explore a vehicle routing problem with two‐dimensional loading constraints and mixed linehauls and backhauls. The addressed problem belongs to a subclass of general pickup and delivery problems. Two‐dimensional loading constraints are also considered. These constraints arise in many real‐world situations and can improve efficiency since backhaul customers do not need to be delayed in a route when it is possible to load their items earlier and without rearrangements of the items. To tackle this problem, we report extensive computational experiments to assess the performance of different variants of the variable neighborhood search approaches. The initial solution relies on an insertion heuristic. Both shaking and local search phases resort to 10 neighborhood structures. Some of those structures were specially developed for this problem. The feasibility of routes is heuristically obtained with a classical bottom‐left based method to tackle the explicit consideration of loading constraints. All the strategies were implemented and exhaustively tested on instances adapted from the literature. The results of this computational study are discussed at the end of this paper.     

Exact formulations for the minimum interference problem in k‐connected ad hoc wireless networks

Energy consumption is one of the most critical issues in wireless ad hoc and sensor networks. A considerable amount of energy is dissipated due to radio transmission power and interference (message collisions). A typical topology control technique aims at reducing energy consumption while ensuring specific desired properties to the established wireless network (such as biconnectivity). Energy minimization can be achieved by reducing the transmission power and selecting edges that suffer or cause less interference. We propose four integer programming formulations for the k‐connected minimum wireless ad hoc interference problem, which consists in a topology control technique to find a power assignment to the nodes of an ad hoc wireless network such that the resulting network topology is k‐vertex connected and the radio interference is minimum. Interference is measured by three different models: Boolean, protocol, and physical. We report computational experiments comparing the formulations and interference models. Optimal solutions for moderately sized networks are obtained using a commercial solver.     

The nested k‐means method: A new approach for detecting lost persons in aerial images acquired by unmanned aerial vehicles

A new method, named as the nested k‐means, for detecting a person captured in aerial images acquired by an unmanned aerial vehicle (UAV), is presented. The nested k‐means method is used in a newly built system that supports search and rescue (SAR) activities through processing of aerial photographs taken in visible light spectra (red‐green‐blue channels, RGB). First, the k‐means classification is utilized to identify clusters of colors in a three‐dimensional space (RGB). Second, the k‐means method is used to verify if the automatically selected class of colors is concurrently spatially clustered in a two‐dimensional space (easting‐northing, EN), and has human‐size area. The UAV images were acquired during the field campaign carried out in the Izerskie Mountains (SW Poland). The experiment aimed to observe several persons using an RGB camera, in spring and winter, during various periods of day, in uncovered terrain and sparse forest. It was found that the nested k‐means method has a considerable potential for detecting a person lost in the wilderness and allows to reduce area to be searched to 4.4 and 7.3% in spring and winter, respectively. In winter, land cover influences the performance of the nested k‐means method, with better skills in sparse forest than in the uncovered terrain. In spring, such a relationship does not hold. The nested k‐means method may provide the SAR teams with a tool for near real‐time detection of a person and, as a consequence, to reduce search area to approximately 0.5–7.3% of total terrain to be visited, depending on season and land cover.     

Engineering an efficient two‐phase local search algorithm for the co‐rotating twin‐screw extruder configuration problem

The twin‐screw configuration problem arises during polymer extrusion and compounding. It consists in defining the location of a set of pre‐defined screw elements along the screw axis in order to optimize different, typically conflicting objectives. In this paper, we present a simple yet effective stochastic local search (SLS) algorithm for this problem. Our algorithm is based on efficient single‐objective iterative improvement algorithms, which have been developed by studying different neighborhood structures, neighborhood search strategies, and neighborhood restrictions. These algorithms are embedded into a variation of the two‐phase local search framework to tackle various bi‐objective versions of this problem. An experimental comparison with a previously proposed multi‐objective evolutionary algorithm shows that a main advantage of our SLS algorithm is that it converges faster to a high‐quality approximation to the Pareto front.     

Parallel matheuristics for the discrete unit commitment problem with min‐stop ramping constraints

The discrete unit commitment problem with min‐stop ramping constraints optimizes the daily production of thermal power plants, subject to an operational reactivity of thermal units in a 30‐minute delay. Previously, mixed integer programming (MIP) formulations aimed at an exact optimization approach. This paper derives matheuristics to face the short time limit imposed by the operational constraints. Continuous relaxations guide the search for feasible solutions exploiting tailored variable fixing strategies. Parallel matheuristics are derived considering complementary strategies in parallel. Tests were performed on more than 600 real‐life instances. Our parallel matheuristic provides high‐quality solutions and outperforms the MIP approach in the time limits imposed by the industrial application. This paper illustrates a special interest for matheuristics in industrial highly constrained problems: many tailored neighborhood searches can be derived from an MIP formulation, and their combination in a parallel scheme improves the solution quality as well as the consistency of the heuristic.     

Robust Kalman filter and smoother for errors‐in‐variables state space models with observation outliers based on the minimum‐covariance determinant estimator

In this paper, we propose a robust Kalman filter and smoother for the errors‐in‐variables (EIV) state space models subject to observation noise with outliers. We introduce the EIV problem with outliers and then present the minimum covariance determinant (MCD) estimator which is a highly robust estimator in terms of protecting the estimate from the outliers. Then, we propose the randomized algorithm to find the MCD estimate. However, the uniform sampling method has a high computational cost and may lead to biased estimates, therefore we apply the sub‐sampling method. A Monte Carlo simulation result shows the efficiency of the proposed algorithm. Copyright © 2011 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society     

EASYLOCAL++: an object‐oriented framework for the flexible design of local‐search algorithms

Local search is a paradigm for search and optimization problems, which has recently evidenced to be very effective for a large number of combinatorial problems. Despite the increasing interest of the research community in this subject, there is still a lack of a widely‐accepted software tools for local search. We propose EASY LOCAL , an object‐oriented framework for the design and the analysis of local‐search algorithms. The abstract classes that compose the framework specify and implement the invariant part of the algorithm and are meant to be specialized by concrete classes that supply the problem‐dependent part. The framework provides the full control structures of the algorithms, and the user has only to write the problem‐specific code. Furthermore, the framework comes with some tools that simplify the analysis of the algorithms. The architecture of EASY LOCAL provides a principled modularization for the solution of combinatorial problems by local search and helps the user by deriving a neat conceptual scheme of the application. It also supports the design of combinations of basic techniques and/or neighborhood structures. The framework has been tested in some applicative domains and has proved to be flexible enough in the implementation of algorithms for the solution of various scheduling problems. Copyright © 2003 John Wiley & Sons, Ltd.