Case-based reasoning for repetitive combinatorial optimization problems, part I: Framework

This article presents a case-based reasoning approach for the development of learning heuristics for solving repetitive operations research problems. We first define the subset of problems we will consider in this work: repetitive combinatorial optimization problems. We then present several general forms that can be used to select previously solved problems that might aid in the solution of the current problem, and several different techniques for actually using this information to derive a solution for the current problem. We describe both fixed forms and forms that have the ability to change as we solve more problems. A simple example for the 0–1 knapsack problem is presented.     

A General Meta-Heuristic Based Solver for Combinatorial Optimisation Problems

In recent years, there have been many studies in which tailored heuristics and meta-heuristics have been applied to specific optimisation problems. These codes can be extremely efficient, but may also lack generality. In contrast, this research focuses on building a general-purpose combinatorial optimisation problem solver using a variety of meta-heuristic algorithms including Simulated Annealing and Tabu Search. The system is novel because it uses a modelling environment in which the solution is stored in dense dynamic list structures, unlike a more conventional sparse vector notation. Because of this, it incorporates a number of neighbourhood search operators that are normally only found in tailored codes and it performs well on a range of problems. The general nature of the system allows a model developer to rapidly prototype different problems. The new solver is applied across a range of traditional combinatorial optimisation problems. The results indicate that the system achieves good performance in terms of solution quality and runtime.     

An algebraic approach to assignment problems

For assignment problems a class of objective functions is studied by algebraic methods and characterized in terms of an axiomatic system. It says essentially that the coefficients of the objective function can be chosen from a totally ordered commutative semigroup, which obeys a divisibility axiom. Special cases of the general model are the linear assignment problem, the linear bottleneck problem, lexicographic multicriteria problems,p-norm assignment problems and others. Further a polynomial bounded algorithm for solving this generalized assignment problem is stated. The algebraic approach can be extended to a broader class of combinatorial optimization problems.     

Self-Adaptive Genetic Algorithm for Clustering

Clustering is a hard combinatorial problem which has many applications in science and practice. Genetic algorithms (GAs) have turned out to be very effective in solving the clustering problem. However, GAs have many parameters, the optimal selection of which depends on the problem instance. We introduce a new self-adaptive GA that finds the parameter setup on-line during the execution of the algorithm. In this way, the algorithm is able to find the most suitable combination of the available components. The method is robust and achieves results comparable to or better than a carefully fine-tuned non-adaptive GA.     

Unified encoding for hyper-heuristics with application to bioinformatics

This paper introduces a new approach to applying hyper-heuristic algorithms to solve combinatorial problems with less effort, taking into account the modelling and algorithm construction process. We propose a unified encoding of a solution and a set of low level heuristics which are domain-independent and which change the solution itself. This approach enables us to address NP-hard problems and generate good approximate solutions in a reasonable time without a large amount of additional work required to tailor search methodologies for the problem in hand. In particular, we focused on solving DNA sequencing by hybrydization with errors, which is known to be strongly NP-hard. The approach was extensively tested by solving multiple instances of well-known combinatorial problems and compared with results generated by meta heuristics that have been tailored for specific problem domains.     

Performance of a genetic algorithm for the graph partitioning problem

The performance of the genetic algorithm (GA) for the graph partitioning problem (GPP) is investigated by comparison with standard heuristics on well-known benchmark graphs. In general, there is a case where a practical performance of a conventional genetic approach, which performs only simple operations without a local search strategy, is not sufficient. However, it is known that a combination of GA and local search can produce better solutions. From this practice, we incorporate a simple local search algorithm into the GA. In particular, the search ability of the GA is compared with standard heuristics such as multistart local search and simulated annealing, which use the same neighborhood structure of the simple local search, for solving the GPP. Experimental results show that the GA performs better than its competitors.     

Capacitated facility location: Separation algorithms and computational experience

We consider the polyhedral approach to solving the capacitated facility location problem. The valid inequalities considered are the knapsack cover, flow cover, effective capacity, single depot, and combinatorial inequalities. The flow cover, effective capacity and single depot inequalities form subfamilies of the general family of submodular inequalities. The separation problem based on the family of submodular inequalities is NP-hard in general. For the well known subclass of flow cover inequalities, however, we show that if the client set is fixed, and if all capacities are equal, then the separation problem can be solved in polynomial time. For the flow cover inequalities based on an arbitrary client set and general capacities, and for the effective capacity and single depot inequalities we develop separation heuristics. An important part of these heuristics is based on the result that two specific conditions are necessary for the effective cover inequalities to be facet defining. The way these results are stated indicates precisely how structures that violate the two conditions can be modified to produce stronger inequalities. The family of combinatorial inequalities was originally developed for the uncapacitated facility location problem, but is also valid for the capacitated problem. No computational experience using the combinatorial inequalities has been reported so far. Here we suggest how partial output from the heuristic identifying violated submodular inequalities can be used as input to a heuristic identifying violated combinatorial inequalities. We report on computational results from solving 60 medium size problems. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

Rollout Algorithms for Stochastic Scheduling Problems

Stochastic scheduling problems are difficult stochastic control problems with combinatorial decision spaces. In this paper we focus on a class of stochastic scheduling problems, the quiz problem and its variations. We discuss the use of heuristics for their solution, and we propose rollout algorithms based on these heuristics which approximate the stochastic dynamic programming algorithm. We show how the rollout algorithms can be implemented efficiently, with considerable savings in computation over optimal algorithms. We delineate circumstances under which the rollout algorithms are guaranteed to perform better than the heuristics on which they are based. We also show computational results which suggest that the performance of the rollout policies is near-optimal, and is substantially better than the performance of their underlying heuristics.     

Applying the attribute based hill climber heuristic to the vehicle routing problem

The attribute based hill climber (ABHC) is a variant of the general tabu-search principle which has shown to be competitive with respect to quality as well as efficiency to other local search heuristics for the two corner stone problems in combinatorial optimization: the travelling salesman problem and the quadratic assignment problem. ABHC is completely parameter-free, and its generic logic depends on the concept of partitioning the solution space based on solution “attributes”, which is the problem-specific choice. In this paper we analyze the effectiveness of this concept and the efficiency of the ABHC heuristic for the general vehicle routing problem.     

Kernel Search: a new heuristic framework for?portfolio?selection

In this paper we propose a new heuristic framework, called Kernel Search, to solve the complex problem of portfolio selection with real features. The method is based on the identification of a restricted set of promising securities (kernel) and on the exact solution of the MILP problem on this set. The continuous relaxation of the problem solved on the complete set of available securities is used to identify the initial kernel and a sequence of integer problems are then solved to identify further securities to insert into the kernel. We analyze the behavior of several heuristic algorithms as implementations of the Kernel Search framework for the solution of the analyzed problem. The proposed heuristics are very effective and quite efficient. The Kernel Search has the advantage of being general and thus easily applicable to a variety of combinatorial problems.     

A biased random key genetic algorithm applied to the electric distribution network reconfiguration problem

This work presents a biased random-key genetic algorithm (BRKGA) to solve the electric distribution network reconfiguration problem (DNR). The DNR is one of the most studied combinatorial optimization problems in power system analysis. Given a set of switches of an electric network that can be opened or closed, the objective is to select the best configuration of the switches to optimize a given network objective while at the same time satisfying a set of operational constraints. The good performance of BRKGAs on many combinatorial optimization problems and the fact that it has never been applied to solve DNR problems are the main motivation for this research. A BRKGA is a variant of random-key genetic algorithms, where one of the parents used for mating is biased to be of higher fitness than the other parent. Solutions are encoded by using random keys, which are represented as vectors of real numbers in the interval (0,1), thus enabling an indirect search of the solution inside a proprietary search space. The genetic operators do not need to be modified to generate only feasible solutions, which is an exclusive task of the decoder of the problem. Tests were performed on standard distribution systems used in DNR studies found in the technical literature and the performance and robustness of the BRKGA were compared with other GA implementations.     

Reducing costs of backhaul networks for PCS networks using genetic algorithms

Designing cost-effective telecommunications networks often involves solving several challenging, interdependent combinatorial optimization problems simultaneously. For example, it may be necessary to select a least-cost subset of locations (network nodes) to serve as hubs where traffic is to be aggregated and switched; optimally assign other nodes to these hubs, meaning that the traffic entering the network at these nodes will be routed to the assigned hubs while respecting capacity constraints on the links; and optimally choose the types of links to be used in interconnecting the nodes and hubs based on the capacities and costs associated with each link type. Each of these three combinatorial optimization problems must be solved while taking into account its impacts on the other two. This paper introduces a genetic algorithm (GA) approach that has proved effective in designing networks for carrying personal communications services (PCS) traffic. The key innovation is to represent information about hub locations and their interconnections as two parts of a chromosome, so that solutions to both aspects of the problem evolve in parallel toward a globally optimal solution. This approach allows realistic problems that take 4–10 hours to solve via a more conventional branch-and-bound heuristic to be solved in 30–35 seconds. Applied to a real network design problem provided as a test case by Cox California PCS, the heuristics successfully identified a design 10% less expensive than the best previously known design. Cox California PCS has adopted the heuristic results and plans to incorporate network optimization in its future network designs and requests for proposals.     

Heuristic concentration: Two stage solution construction

By utilizing information from multiple runs of an interchange heuristic we construct a new solution that is generally better than the best local optimum previously found. This new, two stage, approach to combinatorial optimization is demonstrated in the context of the p-median problem. Two layers of optimization are superimposed. The first layer is a conventional heuristic the second is a heuristic or exact procedure which draws on the concentrated solution set generated by the initial heuristic. The intention is to provide an alternative heuristic procedure which, when dealing with large problems, has a higher probability of producing optimal solutions than existing methods. The procedure is fairly general and appears to be applicable to combinatorial problems in a number of contexts.     

Comparison of Algorithms for the Degree Constrained Minimum Spanning Tree

The Degree Constrained Minimum Spanning Tree (DCMST) on a graph is the problem of generating a minimum spanning tree with constraints on the number of arcs that can be incident to vertices of the graph. In this paper we develop three heuristics for the DCMST, including simulated annealing, a genetic algorithm and a method based on problem space search. We propose alternative tree representations to facilitate the neighbourhood searches for the genetic algorithm. The tree representation that we use for the genetic algorithm can be generalised to other tree optimisation problems as well. We compare the computational performance of all of these approaches against the performance of an exact solution approach in the literature. In addition, we also develop a new exact solution approach based on the combinatorial structure of the problem. We test all of these approaches using standard problems taken from the literature and some new test problems that we generate.     

Cyclic scheduling for F.M.S.: Modelling and evolutionary solving approach

This paper concerns the domain of flexible manufacturing systems (FMS) and focuses on the scheduling problems encountered in these systems. We have chosen the cyclic behaviour to study this problem, to reduce its complexity. This cyclic scheduling problem, whose complexity is NP-hard in the general case, aims to minimise the work in process (WIP) to satisfy economic constraints. We first recall and discuss the best known cyclic scheduling heuristics. Then, we present a two-step resolution approach. In the first step, a performance analysis is carried out; it is based on the Petri net modelling of the production process. This analysis resolves some indeterminism due to the system’s flexibility and allows a lower bound of the WIP to be obtained. In the second step, after a formal model of the scheduling problem has been given, we describe a genetic algorithm approach to find a schedule which can reach the optimal production speed while minimizing the WIP. Finally, our genetic approach is validated and compared with known heuristics on a set of test problems.     

Index Heuristics for Multiclass M/G/1 Systems with Nonpreemptive Service and Convex Holding Costs

We consider the optimal service control of a multiclass M/G/1 queueing system in which customers are served nonpreemptively and the system cost rate is additive across classes and increasing convex in the numbers present in each class. Following Whittle's approach to a class of restless bandit problems, we develop a Langrangian relaxation of the service control problem which serves to motivate the development of a class of index heuristics. The index for a particular customer class is characterised as a fair charge for service of that class. The paper develops these indices and reports an extensive numerical investigation which exhibits strong performance of the index heuristics for both discounted and average costs.     

A hybrid genetic algorithmic approach to the maximally diverse grouping problem

The maximally diverse grouping problem (MDGP) is a NP-complete problem. For such NP-complete problems, heuristics play a major role in searching for solutions. Most of the heuristics for MDGP focus on the equal group-size situation. In this paper, we develop a genetic algorithm (GA)-based hybrid heuristic to solve this problem considering not only the equal group-size situation but also the different group-size situation. The performance of the algorithm is compared with the established Lotfi–Cerveny–Weitz algorithm and the non-hybrid GA. Computational experience indicates that the proposed GA-based hybrid algorithm is a good tool for solving MDGP. Moreover, it can be easily modified to solve other equivalent problems.     

Mathematical programming based heuristics for the 0–1 MIP: a survey

The 0–1 mixed integer programming problem is used for modeling many combinatorial problems, ranging from logical design to scheduling and routing as well as encompassing graph theory models for resource allocation and financial planning. This paper provides a survey of heuristics based on mathematical programming for solving 0–1 mixed integer programs (MIP). More precisely, we focus on the stand-alone heuristics for 0–1 MIP as well as those heuristics that use linear programming techniques or solve a series of linear programming models or reduced problems, deduced from the initial one, in order to produce a high quality solution of a considered problem. Our emphasis will be on how mathematical programming techniques can be used for approximate problem solving, rather than on comparing performances of heuristics.     

Competitive genetic algorithms for the open-shop scheduling problem

For more than two machines, and when preemption is forbidden, the computation of minimum makespan schedules for the open-shop problem is NP-hard. Compared to the flow-shop and the job-shop, the open-shop has free job routes which lead to a much larger solution space, to smaller gaps between the optimal makespan and the lower bounds, and to disappointing results for the algorithms based on the disjunctive graph model. For instance, the best existing branch and bound method cannot solve some 7 ×7 hard instances to optimality, and all published metaheuristics (working by reversing some disjunctions already fixed) do not better than some greedy or steepest-descent heuristics which need a much smaller computational effort. In this context, the intrinsic parallelism of genetic algorithms (GAs) seems well adapted, for detecting global optima disseminated among many quasi-optimal schedules. This paper presents several GAs for the open-shop problem. It is shown that even simple and fast versions can compete with the best known heuristics and metaheuristics, thanks to two key-features: a population in which each individual has a distinct makespan, and a special procedure which reorders every new chromosome. Using problem-specific heuristics, it is possible to design more powerful GAs which give excellent results, even on the hardest benchmarks of the literature: for instance, all hard open instances from Taillard are broken, except one for which the best known solution is improved.