Using a facility location algorithm to solve large set covering problems

Erlenkotter has developed an efficient exact (guarantees optimality) algorithm to solve the uncapacitated facility location problem (UFLP). In this paper, we use his algorithm to solve large instances of an important subset of the UFLP; the set covering problem (SCP). In addition, we present further empirical evidence that a heuristic algorithm developed by Vasko and Wilson for the SCP is capable of quickly generating good solutions to large SCP's.     

Exact hybrid algorithms for solving a bi-objective vehicle routing problem

The paper investigates a capacitated vehicle routing problem with two objectives: (1) minimization of total travel cost and (2) minimization of the length of the longest route. We present algorithmic variants for the exact determination of the Pareto-optimal solutions of this bi-objective problem. Our approach is based on the adaptive ε-constraint method. For solving the resulting single-objective subproblems, we apply a branch-and-cut technique, using (among others) a novel implementation of Held-Karp-type bounds. Incumbent solutions are generated by means of a single-objective genetic algorithm and, alternatively, by the multi-objective NSGA-II algorithm. Experimental results for a benchmark of 54 test instances from the TSPLIB are reported.     

Algorithms for the Set Covering Problem

The Set Covering Problem (SCP) is a main model for several important applications, including crew scheduling in railway and mass-transit companies. In this survey, we focus our attention on the most recent and effective algorithms for SCP, considering both heuristic and exact approaches, outlining their main characteristics and presenting an experimental comparison on the test-bed instances of Beasley's OR Library.     

A branch-and-bound-based local search method for the flow shop problem

It is well-known that exact branch and bound methods can only solve small or moderately sized ????-hard combinatorial optimization problems. In this paper, we address the issue of embedding an approximate branch and bound algorithm into a local search framework. The resulting heuristic has been applied to the problem of finding a minimum makespan in the permutation flow shop problem. Computational experiments carried out on a large set of benchmark problems show that the proposed method consistently yields optimal or near-optimal solutions for instances with up to 200 jobs and 10 machines. In particular, for 19 instances, the heuristic produces solutions that outperform the best known ones.     

A 3-flip neighborhood local search for the set covering problem

The set covering problem (SCP) calls for a minimum cost family of subsets from n given subsets, which together covers the entire ground set. In this paper, we propose a local search algorithm for SCP, which has the following three characteristics. (1) The use of 3-flip neighborhood, which is the set of solutions obtainable from the current solution by exchanging at most three subsets. As the size of 3-flip neighborhood is O(n³), the neighborhood search becomes expensive if implemented naively. To overcome this, we propose an efficient implementation that reduces the number of candidates in the neighborhood without sacrificing the solution quality. (2) We allow the search to visit the infeasible region, and incorporate the strategic oscillation technique realized by adaptive control of penalty weights. (3) The size reduction of the problem by using the information from the Lagrangian relaxation is incorporated, which is indispensable for solving very large instances. According to computational comparisons on benchmark instances with other existing heuristic algorithms for SCP, our algorithm performs quite effectively for various types of problems, especially for very large-scale instances.     

The two-echelon production-routing problem

This paper introduces the Two-Echelon Production-Routing Problem. This problem is motivated from the petrochemical industry, enlarging the supply chain integration by taking into account production, inventory, and routing decisions in a two-echelon vendor-managed inventory system. We describe, model, and design a branch-and-cut (B&C) to solve the problem under different inventory policies. We also propose a novel exact algorithm, by employing parallel computing techniques, in order to combine local search procedures within a traditional B&C scheme. We evaluate the performance of our methods through extensive computational experiments, both by comparing the algorithms, the effectiveness of the different inventory policies, and the impact of these policies on the partial costs. We derive many managerial insights based on the results. We also validate our new exact algorithm by solving similar problems from the literature, such as the two-echelon multi-depot inventory-routing (2E-MDIRP) and the classical multi-vehicle production-routing problem (MV-PRP). Computational experiments show that our method is very competitive. Based on 512 experiments for the 2E-MDIRP, our algorithm was able to find 111 new best known solutions (BKS), besides proving 412 optimal solutions, against 298 from the literature. For 336 experiments over small and medium size MV-PRP instances, we proved 242 optimal solutions, 11 more than the exact methods from the literature, besides providing 95 new BKS. Moreover, we were the first to tackle large MV-PRP instances exactly, and in this case, our algorithm provides all BKS for instances up to 50 customers, 20 periods and 5 vehicles, outperforming all meta/matheuristics procedures from the literature.     

Grasp Embedded Scatter Search for the Multicommodity Capacitated Network Design Problem

A GRASP embedded Scatter Search is developed for the multicommodity capacitated network design problem. Difficulty for this problem arises from the fact that selection of the optimal network design is an NP-complete combinatorial problem. There exist no polynomial exact algorithms which can solve this problem in a reasonable period of time for realistically sized instances. In such cases, heuristic procedures are commonly used. Two strategies were designed for GRASP: a traditional approach and a memory based technique. As for Scatter Search, 5 different strategies were used to update the reference set. Computational results on a large set of randomly generated instances show the convenience of the proposed procedures.     

Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm

We present a new exact algorithm for the Steiner tree problem in edge-weighted graphs. Our algorithm improves the classical dynamic programming approach by Dreyfus and Wagner. We achieve a significantly better practical performance via pruning and future costs, a generalization of a well-known concept to speed up shortest path computations. Our algorithm matches the best known worst-case run time and has a fast, often superior, practical performance: on some large instances originating from VLSI design, previous best run times are improved upon by orders of magnitudes. We are also able to solve larger instances of the d-dimensional rectilinear Steiner tree problem for \(d \in \{3, 4, 5\}\), whose Hanan grids contain up to several millions of edges.     

An effective and simple heuristic for the set covering problem

This paper investigates the development of an effective heuristic to solve the set covering problem (SCP) by applying the meta-heuristic Meta-RaPS (Meta-heuristic for Randomized Priority Search). In Meta-RaPS, a feasible solution is generated by introducing random factors into a construction method. Then the feasible solutions can be improved by an improvement heuristic. In addition to applying the basic Meta-RaPS, the heuristic developed herein integrates the elements of randomizing the selection of priority rules, penalizing the worst columns when the searching space is highly condensed, and defining the core problem to speedup the algorithm. This heuristic has been tested on 80 SCP instances from the OR-Library. The sizes of the problems are up to 1000 rows × 10,000 columns for non-unicost SCP, and 28,160 rows × 11,264 columns for the unicost SCP. This heuristic is only one of two known SCP heuristics to find all optimal/best known solutions for those non-unicost instances. In addition, this heuristic is the best for unicost problems among the heuristics in terms of solution quality. Furthermore, evolving from a simple greedy heuristic, it is simple and easy to code. This heuristic enriches the options of practitioners in the optimization area.     

Average-optimal string matching

The exact string matching problem is to find the occurrences of a pattern of length m from a text of length n symbols. We develop a novel and unorthodox filtering technique for this problem. Our method is based on transforming the problem into multiple matching of carefully chosen pattern subsequences. While this is seemingly more difficult than the original problem, we show that the idea leads to very simple algorithms that are optimal on average. We then show how our basic method can be used to solve multiple string matching as well as several approximate matching problems in average optimal time. The general method can be applied to many existing string matching algorithms. Our experimental results show that the algorithms perform very well in practice.     

Surrogate constraint normalization for the set covering problem

The set covering problem (SCP) is central in a wide variety of practical applications for which finding good feasible solutions quickly (often in real-time) is crucial. Surrogate constraint normalization is a classical technique used to derive appropriate weights for surrogate constraint relaxations in mathematical programming. This framework remains the core of the most effective constructive heuristics for the solution of the SCP chiefly represented by the widely-used Chvátal method. This paper introduces a number of normalization rules and demonstrates their superiority to the classical Chvátal rule, especially when solving large scale and real-world instances. Directions for new advances on the creation of more elaborate normalization rules for surrogate heuristics are also provided.     

A hybrid scatter search/electromagnetism meta-heuristic for project scheduling

In the last few decades, several effective algorithms for solving the resource-constrained project scheduling problem have been proposed. However, the challenging nature of this problem, summarised in its strongly NP-hard status, restricts the effectiveness of exact optimisation to relatively small instances. In this paper, we present a new meta-heuristic for this problem, able to provide near-optimal heuristic solutions for relatively large instances. The procedure combines elements from scatter search, a generic population-based evolutionary search method, and from a recently introduced heuristic method for the optimisation of unconstrained continuous functions based on an analogy with electromagnetism theory. We present computational experiments on standard benchmark datasets, compare the results with current state-of-the-art heuristics, and show that the procedure is capable of producing consistently good results for challenging instances of the resource-constrained project scheduling problem. We also demonstrate that the algorithm outperforms state-of-the-art existing heuristics.     

A cutting-plane approach for large-scale capacitated multi-period facility location using a specialized interior-point method

We propose a cutting-plane approach (namely, Benders decomposition) for a class of capacitated multi-period facility location problems. The novelty of this approach lies on the use of a specialized interior-point method for solving the Benders subproblems. The primal block-angular structure of the resulting linear optimization problems is exploited by the interior-point method, allowing the (either exact or inexact) efficient solution of large instances. The consequences of different modeling conditions and problem specifications on the computational performance are also investigated both theoretically and empirically, providing a deeper understanding of the significant factors influencing the overall efficiency of the cutting-plane method. The methodology proposed allowed the solution of instances of up to 200 potential locations, one million customers and three periods, resulting in mixed integer linear optimization problems of up to 600 binary and 600 millions of continuous variables. Those problems were solved by the specialized approach in less than one hour and a half, outperforming other state-of-the-art methods, which exhausted the (144 GB of) available memory in the largest instances.     

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.     

Decomposition methods for the two-stage stochastic Steiner tree problem

A new algorithmic approach for solving the stochastic Steiner tree problem based on three procedures for computing lower bounds (dual ascent, Lagrangian relaxation, Benders decomposition) is introduced. Our method is derived from a new integer linear programming formulation, which is shown to be strongest among all known formulations. The resulting method, which relies on an interplay of the dual information retrieved from the respective dual procedures, computes upper and lower bounds and combines them with several rules for fixing variables in order to decrease the size of problem instances. The effectiveness of our method is compared in an extensive computational study with the state-of-the-art exact approach, which employs a Benders decomposition based on two-stage branch-and-cut, and a genetic algorithm introduced during the DIMACS implementation challenge on Steiner trees. Our results indicate that the presented method significantly outperforms existing ones, both on benchmark instances from literature, as well as on large-scale telecommunication networks.     

Finding near-optimal independent sets at scale

The maximum independent set problem is NP-hard and particularly difficult to solve in sparse graphs, which typically take exponential time to solve exactly using the best-known exact algorithms. In this paper, we present two new novel heuristic algorithms for computing large independent sets on huge sparse graphs, which are intractable in practice. First, we develop an advanced evolutionary algorithm that uses fast graph partitioning with local search algorithms to implement efficient combine operations that exchange whole blocks of given independent sets. Though the evolutionary algorithm itself is highly competitive with existing heuristic algorithms on large social networks, we further show that it can be effectively used as an oracle to guess vertices that are likely to be in large independent sets. We then show how to combine these guesses with kernelization techniques in a branch-and-reduce-like algorithm to compute high-quality independent sets quickly in huge complex networks. Our experiments against a recent (and fast) exact algorithm for large sparse graphs show that our technique always computes an optimal solution when the exact solution is known, and it further computes consistent results on even larger instances where the solution is unknown. Ultimately, we show that identifying and removing vertices likely to be in large independent sets opens up the reduction space—which not only speeds up the computation of large independent sets drastically, but also enables us to compute high-quality independent sets on much larger instances than previously reported in the literature.     

Irregular polyomino tiling via integer programming with application in phased array antenna design

A polyomino is a generalization of the domino and is created by connecting a fixed number of unit squares along edges. Tiling a region with a given set of polyominoes is a hard combinatorial optimization problem. This paper is motivated by a recent application of irregular polyomino tilings in the design of phased array antennas. Specifically, we formulate the irregular polyomino tiling problem as a nonlinear exact set covering model, where irregularity is incorporated into the objective function using the information-theoretic entropy concept. An exact solution method based on a branch-and-price framework along with novel branching and lower-bounding schemes is proposed. The developed method is shown to be effective for small- and medium-size instances of the problem. For large-size instances, efficient heuristics and approximation algorithms are provided. Encouraging computational results including phased array antenna simulations are reported.     

Strategic oscillation for the capacitated hub location problem with modular links

The capacitated single assignment hub location problem with modular link capacities is a variant of the classical hub location problem in which the cost of using edges is not linear but stepwise, and the hubs are restricted in terms of transit capacity rather than in the incoming traffic. We propose a metaheuristic algorithm based on strategic oscillation, a methodology originally introduced in the context of tabu search. Our method incorporates several designs for constructive and destructive algorithms, together with associated local search procedures, to balance diversification and intensification for an efficient search. Computational results on a large set of instances show that, in contrast to exact methods that can only solve small instances optimally, our metaheuristic is able to find high-quality solutions on larger instances in short computing times. In addition, the new method, which joins tabu search strategies with strategic oscillation, outperforms the previous tabu search implementation.     

An exact algorithm for the sequential ordering problem and its application to switching energy minimization in compilers

This article presents an exact algorithm for the precedence-constrained traveling salesman problem, which is also known as the sequential ordering problem. This NP-hard problem has applications in various domains, including operational research and compilers. In this article, the problem is presented and solved in the context of minimizing switching energy in compilers. Most previous work on minimizing switching energy in the compiler domain has been limited to simple heuristics that are not guaranteed to give an optimal solution. In this work, we present an exact algorithm for solving the switching energy minimization problem using a branch-and-bound approach. The proposed algorithm is simple and intuitive, yet powerful. It is the first exact algorithm for the switching energy problem that is shown to solve real instances of the problem within a few seconds per instance. Compared to previous work in the operational research domain, the proposed algorithm is believed to be the most powerful exact algorithm that does not require a linear programming formulation. The proposed algorithm is experimentally evaluated using instances taken from a production compiler. The results show that with a time limit of 10 ms per node, the proposed algorithm optimally solves 99.8 % of the instances. It optimally solves instances with up to 598 nodes within a few seconds. The resulting switching cost is 16 % less than that produced without energy awareness and 5 % less than that produced by a commonly used heuristic.     

Hybrid Metaheuristics for the Vehicle Routing Problem with Stochastic Demands

This article analyzes the performance of metaheuristics on the vehicle routing problem with stochastic demands (VRPSD). The problem is known to have a computationally demanding objective function, which could turn to be infeasible when large instances are considered. Fast approximations of the objective function are therefore appealing because they would allow for an extended exploration of the search space. We explore the hybridization of the metaheuristic by means of two objective functions which are surrogate measures of the exact solution quality. Particularly helpful for some metaheuristics is the objective function derived from the traveling salesman problem (TSP), a closely related problem. In the light of this observation, we analyze possible extensions of the metaheuristics which take the hybridized solution approach VRPSD-TSP even further and report about experimental results on different types of instances. We show that, for the instances tested, two hybridized versions of iterated local search and evolutionary algorithm attain better solutions than state-of-the-art algorithms.