Graph colouring approaches for a satellite range scheduling problem

Patrick Amstutz, Philippe Giaccari, Nicolas Zufferey
2008
Journal paper

Abstract

A goal of this paper is to efficiently adapt the best ingredients of the graph colouring techniques to an NP-hard satellite range scheduling problem, called MuRRSP. We propose two new heuristics for the MuRRSP, where as many jobs as possible have to be scheduled on several resources, while respecting time and capacity constraints. In the permutation solution space, which is widely used by other researchers, a solution is represented by a permutation of the jobs, and a schedule builder is needed to generate and evaluate a feasible schedule from the permutation. On the contrary, our heuristics are based on the solution space which contains all the feasible schedules. Based on the similarities between the graph colouring problem and the MuRRSP, we show that the latter solution space has significant advantages. A tabu search and an adaptive memory algorithms are designed to tackle the MuRRSP. These heuristics are derived from efficient graph colouring methods. Numerical experiments, performed on large, realistic, and challenging instances, showed that our heuristics are very competitive, robust, and outperform algorithms based on the permutation solution space.

Official source

https://infoscience.epfl.ch/record/160714?ln=en

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts

Related publications

Suboptimal colorings and solution of large chromatic scheduling problems

Ivo Blöchliger

Graph Coloring is a very active field of research in graph theory as well as in the domain of the design of efficient heuristics to solve problems which, due to their computational complexity, cannot be solved exactly (no guarantee that an optimal solution will be reported), see [Cul] for a list of over 450 references. The graph coloring problem involves coloring the vertices of a given graph in such a way that two adjacent vertices never share the same color. The goal is to find the smallest number of colors needed to color all vertices in a fashion that satisfies this requirement. This number is called chromatic number and is denoted by Χ. In the first chapter, we present our research on suboptimal colorings and graphs which can be colored in such a way that the number of different colors appearing on the closed neighborhood (a vertex plus its neighbors) of any vertex v is less than Χ. We call such graphs oligomatic. The most interesting result is the following: given a graph and a coloring using Χ + p colors, there exists a vertex v such that there are at least Χ different colors among all vertices which are at a distance of [p/2] + 1 or less from v. We also study the existence of oligomatic graphs in special classes. Additionally, we present results of research on universal graphs which are "generic" oligomatic graphs in the sense that most properties of oligomatic graphs can be analyzed by restricting ourselves to universal graphs. Chapters Two to Four deal with the development of heuristics for two types of graph coloring problems. The tabu search heuristic was a central focus of our research. A tabu search iteratively modifies a candidate solution (which becomes the new candidate solution) with the goal of improving it. In such a procedure it is forbidden (tabu) to undo a modification for a certain number iterations. This mechanism allows to escape from local minima. In Chapter Two, we propose general improvements for tabu search based on some new and simple mechanisms (called reactive tabu schemes) to adapt the tabu tenure (which corresponds to the number of iterations a modification stays tabu). We also introduce distance and similarity measures for graph coloring problems which are needed in iterative procedures such as those of the tabu search. In the third chapter, we present the PARTIALCOL heuristic for the graph coloring problem. This method obtains excellent results compared to other similar methods and is able to color the well known DIMACS [JT96] benchmark graph flat300_28_0 optimally with 28 colors. (The best colorings found to date by other researchers use at least 31 colors.) PARTIALCOL uses partial solutions in its search space, which is a little explored way of approaching the graph coloring problem. Most approaches either use colorings and try to minimize the number of colors, or they use improper colorings (having conflicts, i.e. adjacent vertices which may have the same color) and try to minimize the number of conflicts. In the final chapter, we present a weighted version of the graph coloring problem which has applications in batch scheduling and telecommunication problems. We present two different adaptations of tabu search to the weighted graph coloring problem and test several of the reactive tabu schemes presented in Chapter Two. Further, we devise an adaptive memory algorithm AMA inspired by genetic algorithms. A large set of benchmark graphs with different properties is presented. All benchmark graphs with known optima have been solved to optimality by AMA. A key element of this algorithm is its capacity to determine the number k of colors to be used. Most other graph coloring heuristics need this parameter to be supplied by the user. Considering the results obtained on various graphs, we are confident that the methods developed are very efficient.

EPFL2005

In this thesis we give new algorithms for two fundamental graph problems. We develop novel ways of using linear programming formulations, even exponential-sized ones, to extract structure from problem instances and to guide algorithms in making progress. Somewhat surprisingly, similar polyhedral techniques can be harnessed in the two seemingly disparate settings. In the first part of the thesis we address a benchmark problem in combinatorial optimization: the asymmetric traveling salesman problem (ATSP). It consists in finding the shortest tour that visits all vertices of a given directed graph with weights on edges. Due to its NP-hardness, the theoretical study of algorithms for ATSP has focused on approximation algorithms: ones that are provably both efficient and give solutions competitive with the optimum. Specifically, a rho-approximation algorithm for ATSP is one that runs in polynomial time and always outputs a tour that is at most rho times longer than the shortest tour. Finding such an approximation algorithm with rho bounded (i.e., a constant factor) had been a long-standing open problem. In this thesis, we give such an algorithm. Our approximation guarantee is analyzed with respect to the standard linear programming relaxation, and thus our result also confirms the conjectured constant integrality gap of that relaxation. Our techniques build upon the constant-factor approximation algorithm for the special case of node-weighted metrics due to Svensson. In particular, we give a generic reduction to structured instances that resemble but are more general than those arising from node-weighted metrics. This reduction takes advantage of a laminar family of vertex sets that arises from the linear programming relaxation. In the second part of the thesis we address the perfect matching problem. The first polynomial-time algorithm for it, given by Edmonds in 1965, is historically associated with the introduction of the class P and our notion that polynomial-time'' means efficient''. That algorithm is sequential and deterministic. We have also known since the 1980s that the matching problem has efficient parallel algorithms if the use of randomness is allowed. Formally, it is in the class RNC, i.e., it has randomized algorithms that use polynomially many processors and run in polylogarithmic time. However, we do not know if randomness is necessary - that is, whether the matching problem is in the class NC. In this thesis we show that the matching problem is in quasi-NC. That is, we give a deterministic parallel algorithm that runs in O(log^3 n) time on n^{O(log^2 n)} processors. The result is obtained by a derandomization of the Isolation Lemma for perfect matchings, which was introduced in the classic paper by Mulmuley, Vazirani and Vazirani to obtain an RNC algorithm. Our proof extends the framework of Fenner, Gurjar and Thierauf, who proved the analogous result in the special case of bipartite graphs. Compared to that setting, several new ingredients are needed due to the significantly more complex structure of perfect matchings in general graphs. In particular, our proof heavily relies on the laminar structure of the faces of the perfect matching polytope.

EPFL2019

Suboptimal colorings and solution of large chromatic scheduling problems

Ivo Blöchliger

EPFL2005