#### Info

In this example the random descent and variable neighbourhood search algorithms are applied for optimization. Don't know what random descent is? Read this. Never heard about variable neighbourhood search? Read this.

This example demonstrates the application of a greedy heuristic to search for a maximum clique in a given graph. The heuristic is created by plugging in a custom greedy neighbourhood in the random descent algorithm. A variable neighbourhood search is also applied based on the greedy heuristic where additional shaking neighbourhoods are used to escape from local optima.

First provide the graph data by implementing the `IntegerIdentifiedData` interface in `CliqueData`. Each vertex in the graph is represented by a unique integer ID. Edges are modeled using an adjacency map in which every vertex is mapped onto the set of adjacent vertices. The data provides some utility methods to get the neighbours or degree of a given vertex, to check whether two vertices are connected, etc. The method `degree(int v, Set<Integer> subGraph)` computes the degree of a given vertex in a specific subgraph, in which case edges to vertices outside this subgraph are not counted.

```public class CliqueData implements IntegerIdentifiedData {

// maps each vertex to set of adjacent vertices
// number of edges
private int numEdges;

// count number of edges
.stream()              // stream of neighbour sets
.mapToInt(Set::size)   // map to number of neighbours
.sum()                 // sum neighbour counts of all vertices
/2;                    // all edges have been counted twice
}

public Set<Integer> getIDs() {
}

public Set<Integer> getNeighbours(int vertex){
}

public boolean connected(int v1, int v2){
}

public int degree(int v){
}

// computes the degree of a vertex in a specific subgraph
// (edges to vertices outside the subgraph are not counted)
public int degree(int v, Set<Integer> subGraph){
// get neighbours of v
// count and return degree within subgraph
return neighbours.stream().filter(n -> subGraph.contains(n)).count();
}

public int numVertices(){
}

public int numEdges(){
return numEdges;
}

}
```

The objective for the maximum clique problem is straightforward: maximize the size of the selected subset. The solution type of `CliqueObjective` is `SubsetSolution`. The data type is set to `Object` as no data is used for evaluation. In fact, this same objective could also be used for other subset problems with any data type.

```public class CliqueObjective implements Objective<SubsetSolution, Object>{

public Evaluation evaluate(SubsetSolution solution, Object data) {
return SimpleEvaluation.WITH_VALUE(solution.getNumSelectedIDs());
}

public boolean isMinimizing() {
return false;
}

}
```

Our basic search strategy is as follows: start with an empty clique and iteratively add a vertex that is connected to all vertices in the current clique. This is a greedy approach in which the size of the clique inceases with one vertex in each search step. To implement this strategy we provide a custom neighbourhood that will be used in a random descent search. The `GreedyCliqueNeighbourhood` implements the `Neighbourhood` interface with solution type `SubsetSolution`. It has two methods: one to get a random move and one to get the list of all considered moves for the current solution. The greedy neighbourhood generates moves that add a single new vertex with maximum degree in the subgraph induced by all vertices that are connected to the entire current clique.

To get a random move, all moves are generated and one is randomly selected. If no vertex can be added, `null` is returned. The list of all considered moves is created as follows:

1. Infer the set of possible adds, i.e. unselected vertices that are connected to the entire current clique.
2. Retain only those vertices from the set of possible adds with maximum degree in the subgraph induced by this set of vertices.
For every retained candidate vertex an `AdditionMove` is generated. If desired, a custom move type could be created as well but this is not necessary here.

#### Info

The method `getRandomMove(solution, rnd)` takes a random generator as its second argument, which should be used as the source of randomness. Each search has a dedicated random generator, which is passed to the neighbourhood when requesting a random move. If desired, a search's random generator can be customized with `search.setRandom(rnd)`.
```public class GreedyCliqueNeighbourhood implements Neighbourhood<SubsetSolution> {

// clique data (graph)
private CliqueData data;

public GreedyCliqueNeighbourhood(CliqueData data) {
this.data = data;
}

public Move<SubsetSolution> getRandomMove(SubsetSolution solution, Random rnd) {
List<Move<SubsetSolution>> allMoves = getAllMoves(solution);
if(allMoves.isEmpty()){
return null;
} else {
return allMoves.get(rnd.nextInt(allMoves.size()));
}
}

public List<Move<SubsetSolution>> getAllMoves(SubsetSolution solution) {
// get current clique
Set<Integer> clique = solution.getSelectedIDs();
// construct set of possible additions
.collect(Collectors.toSet());
// retain only additions of candidate vertices
// with maximum degree within induced subgraph
List<Move<SubsetSolution>> moves = new ArrayList<>();
long degree, maxDegree = -1;
// get degree within subgraph
if(degree > maxDegree){
// higher degree
maxDegree = degree;
moves.clear();
} else if (degree == maxDegree){
// same degree
}
}
return moves;
}

// check if given vertex is connected to all vertices in the current clique
private boolean isPossibleAdd(int vertex, Set<Integer> clique){
return clique.stream().allMatch(vc -> data.connected(vertex, vc));
}

}
```

A basic greedy search is obtained by plugging in our `GreedyCliqueNeighbourhood` in a random descent algorithm that starts with an empty clique. In every step a random vertex with maximum degree among all possible adds is included in the clique. When no more vertices can be added, the neighbourhood returns `null` and the search automatically stops.

#### Search listener

The attached `ProgressSearchListener` keeps track of the search progress (see example 1A: core subset selection).
```// define adjacency map (graph)

// create data object
// create objective
CliqueObjective obj = new CliqueObjective();
// create subset problem (all sizes allowed)
SubsetProblem<CliqueData> problem = new SubsetProblem<>(obj, data);

// create random descent search with greedy clique neighbourhood
RandomDescent<SubsetSolution> randomDescent = new RandomDescent<>(problem, new GreedyCliqueNeighbourhood(data));

// attach listener

randomDescent.setCurrentSolution(new SubsetSolution(data.getIDs()));

// start search
randomDescent.start();
// print results
System.out.println("Clique size: " + randomDescent.getBestSolution().getNumSelectedIDs());
// dispose search
randomDescent.dispose();
```

The basic greedy approach may easily get stuck in a local optimum, i.e. a clique which can not be further extended (maximal) but which is not the largest clique in the entire graph (not maximum). We will now create a more advanced variable neighbourhood search that is based on the greedy approach from above in combination with additional shaking neighbourhoods used to escape from local optima.

A variable neighbourhood search iteratively applies some local search algorithm where the best solution obtained in the previous iteration is somehow perturbed (shaked) and then used as initial solution of the next iteration. We will use the predefined `DisjointMultiDeletionNeighbourhood` for shaking. Random moves generated by such neighbourhood remove a fixed number of randomly chosen items (vertices) from the selection (clique). The number of removed items is specified as a parameter when creating the neighbourhood.

The code below demonstrates how to create a variable neighbourhood search that iteratively applies the greedy strategy from before, using a series of shaking neighbourhoods with a different number of removals to escape from local optima. When the greedy search terminates some vertices will be randomly removed from the clique through shaking and the greedy strategy is resumed. This process is repeated until some stop criterion is satisfied.

```// create shaking neighbourhoods
int maxShake = ...
List<Neighbourhood<SubsetSolution>> shakingNeighs = new ArrayList<>();
for(int s=1; s <= maxShake; s++){
}
// create variable neighbourhood search
LocalSearch<SubsetSolution> vns = new VariableNeighbourhoodSearch<>(
problem,
shakingNeighs,
// use random descent with greedy clique neighbourhood
problem -> new RandomDescent<>(problem, new GreedyCliqueNeighbourhood(data))
);
// set maximum runtime
long timeLimit = ...
// attach listener
vns.setCurrentSolution(new SubsetSolution(data.getIDs()));

// start search
vns.start();
// print results
System.out.println("Clique size: " + vns.getBestSolution().getNumSelectedIDs(););
// dispose search
vns.dispose();
```

The applied VNS strategy is a simplification of a more powerful variable neighbourhood search described in "Variable neighborhood search for the maximum clique" — Hansen et al. This full VNS strategy can easily be implemented in JAMES by plugging in some additional neighbourhoods and chaining several local searches using a piped local search.

The current implementation of `GreedyCliqueNeighbourhood` first constructs the set of possible adds by scanning all unselected vertices and verifying whether they are connected to the entire current clique. These computations are repeated whenever a random move is generated. Here, we describe an optimization that dynamically updates the set of possible adds when a vertex is added to or removed from the clique. This reduces the overall time complexity of the optimization process so that more steps can be taken in the same time.

To keep track of the set of possible adds we extend `SubsetSolution` in `CliqueSolution`. Only a single constructor is provided to create an empty clique. When a vertex is added to the clique, all unconnected vertices are removed from the possible adds. It is also verified whether the added vertex itself is actually contained in the set of possible adds and if not, the vertex is not added. This ensures that the selected subset is always a clique. When removing a vertex from the clique, all vertices that are connected to all remaining clique nodes are again marked as possible adds. The set of possible adds can be accessed at any time using `getPossibleAdds()`.

When implementing or extending a solution type it is important to always provide a `copy()` method that returns a copy of the appropriate solution type. Therefore we override this method as well: it creates a new `CliqueSolution` in which exactly the same clique is selected.

```public class CliqueSolution extends SubsetSolution {

// possible adds (connected to entire current clique)
// impossible adds (not connected to at least one vertex in current clique)

// reference to clique data
private CliqueData data;

// single constructor (empty clique)
public CliqueSolution(CliqueData data){
super(data.getIDs());
// initialize possible adds (all vertices)
// store data reference
this.data = data;
}

@Override
public CliqueSolution copy() {
CliqueSolution copy = new CliqueSolution(data);
copy.selectAll(getSelectedIDs());
return copy;
}

@Override
public boolean select(int vertex){
// new vertex included in clique
.filter(v -> !data.connected(v, vertex))
.collect(Collectors.toSet());
return true;
} else {
return false;
}
}

@Override
public boolean deselect(int vertex){
if(super.deselect(vertex)){
// vertex removed from clique (goes back to possible adds)
// check for new possible adds (connected to remaining clique)
.filter(v -> connectedToClique(v))
.collect(Collectors.toSet());
return true;
} else {
return false;
}
}

// checks whether a given vertex is conected to the entire current clique
private boolean connectedToClique(int vertex){
return getSelectedIDs().stream().allMatch(v -> data.connected(vertex, v));
}

}

}
```

To actually benefit from the new solution type, we create an alternative implementation of the greedy clique neighbourhood with solution type `CliqueSolution`. It can simply call `clique.getPossibleAdds()` to get the set of possible adds. Note that we still return an `AdditionMove` which is defined for solution type `SubsetSolution`. This is allowed because the method definitions in the `Neighbourhood` interface allow to return a more general move type (using generics with wildcards) and `CliqueSolution` extends `SubsetSolution`. After all, a move that can be applied to any subset solution can certainly also be applied to a clique solution.

```public class GreedyCliqueNeighbourhood2 implements Neighbourhood<CliqueSolution> {

// ...

public Move<SubsetSolution> getRandomMove(CliqueSolution clique, Random rnd) {
// ... (same as before)
}

public List<Move<SubsetSolution>> getAllMoves(CliqueSolution clique) {

// get possible adds (constant time!)

// retain only additions of candidate vertices
// with maximum degree within induced subgraph

// ... (same as before)

}

}
```

Now we can not use the predefined `SubsetProblem` as its solution type is fixed to `SubsetSolution`. We can not change it to our new `CliqueSolution`. Therefore, we use the more general `GenericProblem` which allows to set a custom solution type. The constructor also requests a random solution generator, but since creating a random clique is not supported, we specify a generator that throws an appropriate exception. Our search strategy starts from an empty clique, so no random solution will ever be requested anyway.

#### Random solution generator

The `RandomSolutionGenerator` interface has a single method `create(rnd, data)` which generates a random solution using the specified source of randomness and data. Each search has a dedicated random generator, which is passed to the problem, and subsequently to the applied random solution generator, when requesting a random solution. If desired, a search's random generator can be customized with `search.setRandom(rnd)`.
```// as before
CliqueData data = ...
CliqueObjective obj = ...

// create problem
GenericProblem<CliqueSolution, CliqueData> cliqueProblem = new GenericProblem<>(data, obj, (r,d) -> {
// random solution generator throws exception (not supported for this problem)
throw new UnsupportedOperationException("Creating a random clique is not supported.");
});

// RANDOM DESCENT

// set solution type of search to clique solution and use optimized neighbourhood
RandomDescent<CliqueSolution> randomDescent = new RandomDescent<>(problem, new GreedyCliqueNeighbourhood2(data));
randomDescent.setCurrentSolution(new CliqueSolution(data));

// ... (same as before)

// VARIABLE NEIGHBOURHOOD SEARCH

// create shaking neighbourhoods (same as before)
List<Neighbourhood<SubsetSolution>> shakingNeighs = ...

// create variable neighbourhood search with solution type clique solution and optimized neighbourhood
VariableNeighbourhoodSearch<CliqueSolution> vns = new VariableNeighbourhoodSearch<>(
problem,
shakingNeighs,
problem -> new RandomDescent<>(problem, new GreedyCliqueNeighbourhood2(data))
);
```\$ java -cp james-examples.jar org.jamesframework.examples.clique.MaximumClique <inputfile> <maxshake> <runtime>
from the command line. The input file should be a text file in which every row indicates an edge between two vertices (integer IDs) separated by one or more spaces. The `<maxshake>` parameter determines the number of shaking neighbourhoods that are used for VNS which each remove a fixed number of vertices in [1,`<maxshake>`]. The runtime is given in seconds.