Gray-box optimization is an approach for making some problem-specific information available to the algorithm while still relying on fitness information as the main guide to an optimum. This approach was shown to be beneficial in various combinatorial optimization tasks and neatly captures the continuum between fully black-box algorithms and tailored algorithms. In this work, we discuss different flavors of gray-box algorithms. We show that RLS can find a proper 2-coloring in a bipartite graph starting from a random 2-coloring, in an expected time of O(nlogn). In contrast, when starting from a proper n-coloring, the (1+1) EA cannot find such a coloring except when offered additional guiding on plateaus of the search space. Finally, we show the run time for this setting can be much improved by using gray-box operators.
Local search is a well-known heuristic method used in optimization. In this thesis, we explore its capabilities on the vertex coloring problem, an NP-hard problem with relevance in both theoretical analysis and practical application. To recognize limitations in the applicability of local search of the vertex coloring problem, we analyze local search landscapes on differently-structured bipartite graphs. We identify structures that ensure only global optima can exist as well as ones that enable the existence of non-global local optima, showing that on general bipartite graphs, it is possible for local search to return arbitrarily bad results. Further, we analyze the capabilities of local search on graphs where a local optimum can be found. To do so, we introduce a gray-box local search mutation operator that removes less frequent colors with higher probability and prove that it finds an optimal coloring on complete bipartite graphs in an expected run time of Θ(nlogn). This is a drastic improvement to the exponential tun time of the black-box Random Local Search, showing that gray-box mutation operators can improve the run time of local search.
The Graph Coloring Problem (GCP) is NP-hard and DSATUR stands as one of the fastest heuristics for it despite producing colorings that typically use more colors than state-of-the-art coloring algorithms. We propose SSLD (Semidefinite Spectral Learning with DSATUR), which improves DSATUR by preprocessing a first good color class before letting DSATUR complete coloring the rest of the given graph. We obtain this color class from a Semidefinite Programming (SDP), similar to an SDP used to compute the Lovász theta number. To the best of our knowledge, SSLD is the first approach to improve DSATUR by preprocessing through fixed color classes. We evaluate SSLD against DSATUR and against a naive 1-color-class preprocessing algorithm on DIMACS instances, random graphs (Erdős--Rényi, Watts-Strogatz, Barabási--Albert), Frequency Assignment and Job Shop Scheduling instances. SSLD matches or beats DSATUR in almost every case across over 1600 benchmark instances, and out performs the naive GISD baseline, allows us to confirm the value brought by the SDP-guided choice of the first color class. This quality comes at a runtime cost of roughly 195 times slower that DSATUR, but demonstrating that SDP-guided preprocessing of a first color class is a direction for future improvements.
We analyze the two combinatorial problems of Dominating Set and Vertex Coloring regarding what kind of local optima are present for various instances. For a variety of graph classes each, we determine whether the induced landscapes are unimodal, plateau-unimodal (all optima are just one plateau), equimodal (all local optima are global) or truly multimodal. We do this for two different neighborhood operators, one based on making only a single change and one also allowing swaps (interchanging two parts of the solution).