Multilevel graph partitioning: an evolutionary approach

The graph partitioning problem is defined as that of dividing the vertices of an undirected graph into a set of balanced parts through the removal of a set of edges, whose size is to be minimized. A number of researchers have investigated multilevel schemes, which coarsen the graph by collapsing vertices and edges, partition the smaller graph, and then uncoarsen it to construct a partitioning of the original graph. In this paper, a genetic algorithm for the coarsening phase of a multilevel scheme for graph partitioning is presented. The proposed approach has been demonstrated to improve the solution quality at the expense of running time.     

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.     

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.     

Simulated N-Body: New Particle Physics-Based Heuristics for a Euclidean Location-Allocation Problem

The general facility location problem and its variants, including most location-allocation and P-median problems, are known to be NP-hard combinatorial optimization problems. Consequently, there is now a substantial body of literature on heuristic algorithms for a variety of location problems, among which can be found several versions of the well-known simulated annealing algorithm. This paper presents an optimization paradigm that, like simulated annealing, is based on a particle physics analogy but is markedly different from simulated annealing. Two heuristics based on this paradigm are presented and compared to simulated annealing for a capacitated facility location problem on Euclidean graphs. Experimental results based on randomly generated graphs suggest that one of the heuristics outperforms simulated annealing both in cost minimization as well as execution time. The particular version of location problem considered here, a location-allocation problem, involves determining locations and associated regions for a fixed number of facilities when the region sizes are given. Intended applications of this work include location problems with congestion costs as well as graph and network partitioning problems.     

A multi-parametric programming approach for multilevel hierarchical and decentralised optimisation problems

In this paper, we outline the foundations of a general global optimisation strategy for the solution of multilevel hierarchical and general decentralised multilevel problems, based on our recent developments on multi-parametric programming and control theory. The core idea is to recast each optimisation subproblem, present in the hierarchy, as a multi-parametric programming problem, with parameters being the optimisation variables belonging to the remaining subproblems. This then transforms the multilevel problem into single-level linear/convex optimisation problems. For decentralised systems, where more than one optimisation problem is present at each level of the hierarchy, Nash equilibrium is considered. A three person dynamic optimisation problem is presented to illustrate the mathematical developments.     

Symmetry in RLT-type relaxations for the quadratic assignment and standard quadratic optimization problems

The reformulation–linearization technique (RLT), introduced in [Sherali, H. D., Adams. W. P. (1990). A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM Journal on Discrete Mathematics 3(3), 411–430], provides a way to compute a hierarchy of linear programming bounds on the optimal values of NP-hard combinatorial optimization problems. In this paper we show that, in the presence of suitable algebraic symmetry in the original problem data, it is sometimes possible to compute level two RLT bounds with additional linear matrix inequality constraints. As an illustration of our methodology, we compute the best-known bounds for certain graph partitioning problems on strongly regular graphs.     

Global optimization of multilevel electricity market models including network design and graph partitioning

We consider the combination of a network design and graph partitioning model in a multilevel framework for determining the optimal network expansion and the optimal zonal configuration of zonal pricing electricity markets, which is an extension of the model discussed in Grimm et al. (2019) that does not include a network design problem. The two classical discrete optimization problems of network design and graph partitioning together with nonlinearities due to economic modeling yield extremely challenging mixed-integer nonlinear multilevel models for which we develop two problem-tailored solution techniques. The first approach relies on an equivalent bilevel formulation and a standard KKT transformation thereof including novel primal-dual bound tightening techniques, whereas the second is a tailored generalized Benders decomposition. For the latter, we strengthen the Benders cuts of Grimm et al. (2019) by using the structure of the newly introduced network design subproblem. We prove for both methods that they yield global optimal solutions. Afterward, we compare the approaches in a numerical study and show that the tailored Benders approach clearly outperforms the standard KKT transformation. Finally, we present a case study that illustrates the economic effects that are captured in our model.     

Ant colony optimization for the examination scheduling problem

Ant colony optimization is an evolutionary search procedure based on the way that ant colonies cooperate in locating shortest routes to food sources. Early implementations focussed on the travelling salesman and other routing problems but it is now being applied to an increasingly diverse range of combinatorial optimization problems. This paper is concerned with its application to the examination scheduling problem. It builds on an existing implementation for the graph colouring problem to produce clash-free timetables and goes on to consider the introduction of a number of additional practical constraints and objectives. A number of enhancements and modifications to the original algorithm are introduced and evaluated. Results based on real-examination scheduling problems including standard benchmark data (the Carter data set) show that the final implementation is able to compete effectively with the best-known solution approaches to the problem.     

Comparing Metaheuristic Algorithms for Sonet Network Design Problems

This paper considers two problems that arise in the design of optical telecommunication networks when a ring-based topology is adopted, namely the SONET Ring Assignment Problem and the Intraring Synchronous Optical Network Design Problem. We show that these two network topology problems correspond to graph partitioning problems with capacity constraints: the first is a vertex partitioning problem, while the latter is an edge partitioning problem. We consider solution methods for both problems, based on metaheuristic algorithms. We first describe variable objective functions that depend on the transition from one solution to a neighboring one, then we apply several diversification and intensification techniques including Path Relinking, eXploring Tabu Search and Scatter Search. Finally we propose a diversification method based on the use of multiple neighborhoods. A set of extensive computational results is used to compare the behaviour of the proposed methods and objective functions.     

A Parallel Multilevel Metaheuristic for Graph Partitioning

One significant problem of optimisation which occurs in many scientific areas is that of graph partitioning. Several heuristics, which pertain to high quality partitions, have been put forward. Multilevel schemes can in fact improve the quality of the solutions. However, the size of the graphs is very large in many applications, making it impossible to effectively explore the search space. In these cases, parallel processing becomes a very useful tool overcoming this problem. In this paper, we propose a new parallel algorithm which uses a hybrid heuristic within a multilevel scheme. It is able to obtain very high quality partitions and improvement on those obtained by other algorithms previously put forward.     

Hybrid genetic algorithms for bin-packing and related problems

The genetic algorithm (GA) paradigm has attracted considerable attention as a promising heuristic approach for solving optimization problems. Much of the development has related to problems of optimizing functions of continuous variables, but recently there have been several applications to problems of a combinatorial nature. What is often found is that GAs have fairly poor performance for combinatorial problems if implemented in a naive way, and most reported work has involved somewhat ad hoc adjustments to the basic method. In this paper, we will describe a general approach which promises good performance for a fairly extensive class of problems by hybridizing the GA with existing simple heuristics. The procedure will be illustrated mainly in relation to the problem ofbin-packing, but it could be extended to other problems such asgraph partitioning, parallel-machine scheduling andgeneralized assignment. The method is further extended by usingproblem size reduction hybrids. Some results of numerical experiments will be presented which attempt to identify those circumstances in which these heuristics will perform well relative to exact methods. Finally, we discuss some general issues involving hybridization: in particular, we raise the possibility of blending GAs with orthodox mathematical programming procedures.     

Tabu search for graph partitioning

In this paper, we develop a tabu search procedure for solving the uniform graph partitioning problem. Tabu search, an abstract heuristic search method, has been shown to have promise in solving several NP-hard problems, such as job shop and flow shop scheduling, vehicle routing, quadratic assignment, and maximum satisfiability. We compare tabu search to other heuristic procedures for graph partitioning, and demonstrate that tabu search is superior to other solution approaches for the uniform graph partitioning problem both with respect to solution quality and computational requirements.     

Dual multilevel optimization

We study the structure of dual optimization problems associated with linear constraints, bounds on the variables, and separable cost. We show how the separability of the dual cost function is related to the sparsity structure of the linear equations. As a result, techniques for ordering sparse matrices based on nested dissection or graph partitioning can be used to decompose a dual optimization problem into independent subproblems that could be solved in parallel. The performance of a multilevel implementation of the Dual Active Set algorithm is compared with CPLEX Simplex and Barrier codes using Netlib linear programming test problems.      

A variable neighborhood search for graph coloring

Descent methods for combinatorial optimization proceed by performing a sequence of local changes on an initial solution which improve each time the value of an objective function until a local optimum is found. Several metaheuristics have been proposed which extend in various ways this scheme and avoid being trapped in local optima. For example, Hansen and Mladenovic have recently proposed the variable neighborhood search method which has not yet been applied to many combinatorial optimization problems. The aim of this paper is to propose an adaptation of this new method to the graph coloring problem.     

Evolutionary,constructive and hybrid procedures for the bi-objective set packing problem

The bi-objective set packing problem is a multi-objective combinatorial optimization problem similar to the well-known set covering/partitioning problems. To our knowledge and surprise, this problem has not yet been studied whereas several applications have been reported. Unfortunately, solving the problem exactly in a reasonable time using a generic solver is only possible for small instances. We designed three alternative procedures for approximating solutions to this problem. The first is derived from the original ‘Strength Pareto Evolutionary Algorithm’, which is a population-based metaheuristic. The second is an adaptation of the ‘Greedy Randomized Adaptative Search Procedure’, which is a constructive metaheuristic. As underlined in the overview of the literature summarized here, almost all the recent, effective procedures designed for approximating optimal solutions to multi-objective combinatorial optimization problems are based on a blend of techniques, called hybrid metaheuristics. Thus, the third alternative, which is the primary subject of this paper, is an original hybridization of the previous two metaheuristics. The algorithmic aspects, which differ from the original definition of these metaheuristics, are described, so that our results can be reproduced. The performance of our procedures is reported and the computational results for 120 numerical instances are discussed.     

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.     

Pareto Simulated Annealing for Fuzzy Multi-Objective Combinatorial Optimization

The paper presents a metaheuristic method for solving fuzzy multi-objective combinatorial optimization problems. It extends the Pareto simulated annealing (PSA) method proposed originally for the crisp multi-objective combinatorial (MOCO) problems and is called fuzzy Pareto simulated annealing (FPSA). The method does not transform the original fuzzy MOCO problem to an auxiliary deterministic problem but works in the original fuzzy objective space. Its goal is to find a set of approximately efficient solutions being a good approximation of the whole set of efficient solutions defined in the fuzzy objective space. The extension of PSA to FPSA requires the definition of the dominance in the fuzzy objective space, modification of rules for calculating probability of accepting a new solution and application of a defuzzification operator for updating the average position of a solution in the objective space. The use of the FPSA method is illustrated by its application to an agricultural multi-objective project scheduling problem.     

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.     

Partitioning (hierarchically clustered) complex networks via size-constrained graph clustering

The most commonly used method to tackle the graph partitioning problem in practice is the multilevel metaheuristic. In this paper we introduce size-constrained label propagation (SCLaP) and show how it can be used to instantiate both the coarsening phase and the refinement phase of multilevel graph partitioning. We mainly target networks with highly irregular and hierarchically clustered structure (but other network types can be partitioned as well). Additionally, we augment the basic algorithm with several extensions to further improve its speed and/or solution quality. Depending on the configuration of the resulting partitioner using SCLaP, we are able to compute high-quality partitions outperforming all competitors, or instead, to compute similarly good partitions as the best competitor in terms of quality, hMetis, while being an order of magnitude faster. Our fastest configuration partitions the largest real-world graph in our study (it has 3.3 billion edges) with sequential code in about ten minutes while cutting less than half of the edges than the fastest competitor, kMetis.     

Constraint Programming-based Column Generation

This paper surveys recent applications and advances of the Constraint Programming-based Column Generation framework, where the master subproblem is solved by traditional OR techniques, while the pricing subproblem is solved by Constraint Programming. This framework has been introduced to solve crew assignment problems, where complex regulations make the pricing subproblem demanding for traditional techniques, and then it has been applied to other contexts. The main benefits of using Constraint Programming are the expressiveness of its modeling language and the flexibility of its solvers. Recently, the Constraint Programming-based Column Generation framework has been applied to many other problems, ranging from classical combinatorial problems such as graph coloring and two dimensional bin packing, to application oriented problems, such as airline planning and resource allocation in wireless ad-hoc networks.