An Ant Colony Optimization Algorithm for the Minimum Weight Vertex Cover Problem

Given an undirected graph and a weighting function defined on the vertex set, the minimum weight vertex cover problem is to find a vertex subset whose total weight is minimum subject to the premise that the selected vertices cover all edges in the graph. In this paper, we introduce a meta-heuristic based upon the Ant Colony Optimization (ACO) approach, to find approximate solutions to the minimum weight vertex cover problem. In the literature, the ACO approach has been successfully applied to several well-known combinatorial optimization problems whose solutions might be in the form of paths on the associated graphs. A solution to the minimum weight vertex cover problem however needs not to constitute a path. The ACO algorithm proposed in this paper incorporates several new features so as to select vertices out of the vertex set whereas the total weight can be minimized as much as possible. Computational experiments are designed and conducted to study the performance of our proposed approach. Numerical results evince that the ACO algorithm demonstrates significant effectiveness and robustness in solving the minimum weight vertex cover problem.     

Staged and constrained two-dimensional guillotine cutting problems: An AND/OR-graph approach

An AND/OR-graph approach has been proposed by Morabito et al. to solve non-staged and unconstrained two-dimensional guillotine cutting problems. Basically, this approach consists of representing cutting patterns as complete paths in an AND/OR graph (where nodes and arcs correspond to rectangles and cuts, respectively) and choosing a search strategy to traverse or enumerate the nodes of the graph. In this present paper, the AND/OR-graph approach is extended to solve staged and constrained problems. Computational experiments with examples from the literature are performed and indicate that this approach generates good and fast solutions using a microcomputer. In addition to the fact that the AND/OR-graph approach can handle important constraints, it can be easily extended to solve cutting and packing problems with multiple dimensions.     

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.     

Positive Semidefinite Rank-Based Correlation Matrix Estimation With Application to Semiparametric Graph Estimation

Many statistical methods gain robustness and flexibility by sacrificing convenient computational structures. In this article, we illustrate this fundamental tradeoff by studying a semiparametric graph estimation problem in high dimensions. We explain how novel computational techniques help to solve this type of problem. In particular, we propose a nonparanormal neighborhood pursuit algorithm to estimate high-dimensional semiparametric graphical models with theoretical guarantees. Moreover, we provide an alternative view to analyze the tradeoff between computational efficiency and statistical error under a smoothing optimization framework. Though this article focuses on the problem of graph estimation, the proposed methodology is widely applicable to other problems with similar structures. We also report thorough experimental results on text, stock, and genomic datasets.     

The robust binomial approach to chance-constrained optimization problems with application to stochastic partitioning of large process networks

In this paper, we study an interpretation of the sample-based approach to chance-constrained programming problems grounded in statistical testing theory. On top of being simple and pragmatic, this approach is theoretically well founded, non parametric and leads to a general method for leveraging existing heuristic algorithms for the deterministic case to their chance-constrained counterparts. Throughout this paper, this algorithm design approach is illustrated on a real world graph partitioning problem which crops up in the field of compilation for parallel systems. Extensive computational results illustrate the practical relevance of the approach, as well as the robustness of the obtained solutions.     

Limit vector variational inequality problems via scalarization

This paper presents a global optimization approach for solving signomial geometric programming (SGP) problems. We employ an accelerated extended cutting plane (ECP) approach integrated with piecewise linear (PWL) approximations to solve the global optimization of SGP problems. In this approach, we separate the feasible regions determined by the constraints into convex and nonconvex ones in the logarithmic domain. In the nonconvex feasible regions, the corresponding constraint functions are converted into mixed integer linear constraints using PWL approximations, while the other constraints with convex feasible regions are handled by the ECP method. We also use pre-processed initial cuts and batched cuts to accelerate the proposed algorithm. Numerical results show that the proposed approach can solve the global optimization of SGP problems efficiently and effectively.     

Solving VRPTWs with Constraint Programming Based Column Generation

Constraint programming based column generation is a hybrid optimization framework recently proposed (Junker et al., 1999) that uses constraint programming to solve column generation subproblems. In the past, this framework has been used to solve scheduling problems where the associated graph is naturally acyclic and has done so very efficiently. This paper attempts to solve problems whose graph is cyclic by nature, such as routing problems, by solving the elementary shortest path problem with constraint programming. We also introduce new redundant constraints which can be useful in the general framework. The experimental results are comparable to those of the similar method in the literature (Desrochers, Desrosiers, and Solomon, 1992) but the proposed method yields a much more flexible approach.     

A polynomially searchable exponential neighbourhood for graph colouring

In this paper, we develop a new graph colouring strategy. Our heuristic is an example of a so-called polynomially searchable exponential neighbourhood approach. The neighbourhood is that of permutations of the colours of vertices of a subgraph. Our approach provides a solution method for colouring problems with edge weights. Results for initial tests on unweighted K-colouring benchmark problems are presented. Our colour permutation move was found in practice to be too slow to justify its use on these problems. By contrast, our implementation of iterative descent, which incorporates a permutation kickback move, performed extremely well. Moreover, our approach may yet prove valuable for weighted K-colouring. In addition, our approach offers an improved measure of the distance between colourings of a graph.     

Stability preserving transformations of graphs

Graph transformations proved useful for many algorithmic problems. In the present paper, we study this tool with respect to the maximum stable set problem. We first review available results on this topic and then propose an approach to uniformly describe and systematically develop graph transformations that do not change the size of a maximum stable set in the graph. The approach is illustrated by a number of new transformations.     

弦图子类的全控制函数

本文首先证明了k-全控制问题和符号全控制问题在双弦图上均为NP-完全的.其次,在强消去序已给定的强弦图上,给出了求解符号全控制、负全控制、k-全控制和k-全控制问题的统一的O(m+n)时间算法.     

Multiple-retrieval case-based reasoning for course timetabling problems

The structured representation of cases by attribute graphs in a case-based reasoning (CBR) system for course timetabling has been the subject of previous research by the authors. In that system, the case base is organized as a decision tree and the retrieval process chooses those cases that are sub-attribute graph isomorphic to the new case. The drawback of that approach is that it is not suitable for solving large problems. This paper presents a multiple-retrieval approach that partitions a large problem into small solvable sub-problems by recursively inputting the unsolved part of the graph into the decision tree for retrieval. The adaptation combines the retrieved partial solutions of all the partitioned sub-problems and employs a graph heuristic method to construct the whole solution for the new case. We present a methodology which is not dependent upon problem-specific information and which, as such, represents an approach which underpins the goal of building more general timetabling systems. We also explore the question of whether this multiple-retrieval CBR could be an effective initialization method for local search methods such as hill climbing, tabu search and simulated annealing. Significant results are obtained from a wide range of experiments. An evaluation of the CBR system is presented and the impact of the approach on timetabling research is discussed. We see that the approach does indeed represent an effective initialization method for these approaches.     

Effective graph resistance

This paper studies an interesting graph measure that we call the effective graph resistance. The notion of effective graph resistance is derived from the field of electric circuit analysis where it is defined as the accumulated effective resistance between all pairs of vertices. The objective of the paper is twofold. First, we survey known formulae of the effective graph resistance and derive other representations as well. The derivation of new expressions is based on the analysis of the associated random walk on the graph and applies tools from Markov chain theory. This approach results in a new method to approximate the effective graph resistance. A second objective of this paper concerns the optimisation of the effective graph resistance for graphs with given number of vertices and diameter, and for optimal edge addition. A set of analytical results is described, as well as results obtained by exhaustive search. One of the foremost applications of the effective graph resistance we have in mind, is the analysis of robustness-related problems. However, with our discussion of this informative graph measure we hope to open up a wealth of possibilities of applying the effective graph resistance to all kinds of networks problems.     

An applied statistics course for systematics and ecology PhD students

Statistics education is under review at all educational levels. Statistical concepts, as well as the use of statistical methods and techniques, can be taught in at least two contrasting ways. Specifically, (1) teaching can be theoretically and mathematically oriented, or (2) it can be less mathematically oriented being focused, instead, on application and the use of data to solve real-world problems. The second approach is growing in practice and new goals have recently emerged. At present, statistics courses stress probability concepts, data analysis, and the interpretation and communication of results. Understanding the process of statistical investigation is established as a way of improving mastery of statistical reasoning. In this context, a project-based approach allows the design and implementation of participating learning scenarios in order to understand the statistical methodology and, as a consequence, improve research. This approach points out that statistics is a rational methodology used to solve practical problems. The purpose of this paper is to present the design and results of an applied statistics course for PhD students in ecology and systematics using a project-based approach. Examples involving character coding, species classification, and the interpretation of geographical variation, which are the principal systematic analyses requiring statistical techniques, are presented using the results from student projects. In addition, an example from conservation ecology is presented. Results indicate that the students understood the concepts and applied the systematic and statistical techniques accurately using a data oriented approach.     

A quadratic programming approach to the determination of an upper bound on the weighted stability number

In a previous work, the authors have introduced an upper bound on the stability number of a graph and several of its properties were given. The determination of this upper bound was done by a quadratic programming approach whose implementation has given good computational results. We now extend this bound to the weighted case, i.e., an upper bound on the weighted stability of an arbitrary graph with node weights is presented. Similarly to the non-weighted case, the deduced bound allows us to give a necessary and sufficient condition to a weighted graph that attains the given bound. Also a heuristic for determining the maximum weight stable set is proposed which is based on an integrality property of a convex quadratic problem that produces the bound. Some comments about the proposed approach will conclude the paper.     

A two-stage solution approach for the Directed Rural Postman Problem with Turn Penalties

In this paper, we consider the Directed Rural Postman Problem with Turn Penalties (DRPP-TP). A solution is a tour that traverses all required arcs of the graph. The total cost of the tour is the sum of the lengths of the traversed arcs plus the penalties associated with the turns. One solution approach involves transforming the arc routing problem into an equivalent node routing problem. An alternative direct approach (without graph transformation) that involves two stages has been proposed in the literature. In the first part of this paper, we investigate the applicability of the direct approach. We identify several characteristics of the input instance that make this approach effective and present several limitations of this approach. In the second part of this paper, we describe an integer linear program that is combined with a local search algorithm. This combination produces high-quality solutions to the DRPP-TP in a reasonable amount of computing time.     

Estimating the statistical error in calculating velocity and temperature components by the direct simulation Monte Carlo method

The direct simulation Monte Carlo (DSMC) method is widely used to solve problems in rarefied gas dynamics. In solving steady state problems, a special feature of the method is in using dependent sample values of random variables to calculate the macroparameters of gas flow. In this paper, the possibilities of methods of statistical physics to estimate the statistical error of the DSMC method are theoretically analyzed. A simple approach to approximate estimation of the statistical error in calculating temperature and velocity components is proposed. The approach is tested on a number of problems.     

Adaptive automated construction of hybrid heuristics for exam timetabling and graph colouring problems

In this paper, we present a random iterative graph based hyper-heuristic to produce a collection of heuristic sequences to construct solutions of different quality. These heuristic sequences can be seen as dynamic hybridisations of different graph colouring heuristics that construct solutions step by step. Based on these sequences, we statistically analyse the way in which graph colouring heuristics are automatically hybridised. This, to our knowledge, represents a new direction in hyper-heuristic research. It is observed that spending the search effort on hybridising Largest Weighted Degree with Saturation Degree at the early stage of solution construction tends to generate high quality solutions. Based on these observations, an iterative hybrid approach is developed to adaptively hybridise these two graph colouring heuristics at different stages of solution construction. The overall aim here is to automate the heuristic design process, which draws upon an emerging research theme on developing computer methods to design and adapt heuristics automatically. Experimental results on benchmark exam timetabling and graph colouring problems demonstrate the effectiveness and generality of this adaptive hybrid approach compared with previous methods on automatically generating and adapting heuristics. Indeed, we also show that the approach is competitive with the state of the art human produced methods.     

Using matrices to link conflict evolution and resolution in a graph model

The graph model for conflict resolution provides a convenient and effective means to model and analyze a strategic conflict. Standard practice is to carry out a stability analysis of a graph model, and then to follow up with a post-stability analysis, an important component of which is status quo analysis. A graph model can be viewed as an edge-colored graph, but the fundamental problem of status quo analysis – to find a shortest colored path from the status quo node to a desired equilibrium – is different from the well-known network analysis problem of finding the shortest path between two nodes. The only matrix method that has been proposed cannot track all aspects of the evolution of a conflict from the status quo state. Our explicit algebraic approach is convenient for computer implementation and, as demonstrated with a real world case study, easy to use. It provides new insights into a graph model, not only identifying all equilibria reachable from the status quo, but also how to reach them. Moreover, this approach bridges the gap between stability analysis and status quo analysis in the graph model for conflict resolution.     

On external-memory MST, SSSP and multi-way planar graph separation

Recently external memory graph problems have received considerable attention because massive graphs arise naturally in many applications involving massive data sets. Even though a large number of I/O-efficient graph algorithms have been developed, a number of fundamental problems still remain open.The results in this paper fall in two main classes. First we develop an improved algorithm for the problem of computing a minimum spanning tree (MST) of a general undirected graph. Second we show that on planar undirected graphs the problems of computing a multi-way graph separation and single source shortest paths (SSSP) can be reduced I/O-efficiently to planar breadth-first search (BFS). Since BFS can be trivially reduced to SSSP by assigning all edges weight one, it follows that in external memory planar BFS, SSSP, and multi-way separation are equivalent. That is, if any of these problems can be solved I/O-efficiently, then all of them can be solved I/O-efficiently in the same bound. Our planar graph results have subsequently been used to obtain I/O-efficient algorithms for all fundamental problems on planar undirected graphs.     

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.