Choco Solver

Using Choco Solver to compute Dominating Sets

Given an undirected graph, a dominating set is a subset of its nodes such that any node can be connected by an edge to a node of this subset. In this example, we consider the problem of finding a minimum size dominating set such that the induced subgraph is connected.

This example illustrates how to hybrid a graph variable with boolean variables representing the node set. It is important to understand that the graph variable is only a support to apply the connectivity global constraint, but it is not a decision variable: once the node set is fixed, all arcs are considered, we do not need to branch on them.

We can then add a search heuristic to switch off nodes with low degrees first. This presumably leads to a good first solution.

/*
 * Copyright (C) 2017 COSLING S.A.S.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

import org.chocosolver.graphsolver.GraphModel;
import org.chocosolver.graphsolver.variables.UndirectedGraphVar;
import org.chocosolver.solver.Model;
import org.chocosolver.solver.search.strategy.Search;
import org.chocosolver.solver.search.strategy.selectors.values.IntDomainMin;
import org.chocosolver.solver.variables.BoolVar;
import org.chocosolver.solver.variables.IntVar;
import org.chocosolver.util.objects.graphs.UndirectedGraph;
import org.chocosolver.util.objects.setDataStructures.SetType;

/**
 * Simple example of connected dominating set problem
 * Shows how to use graph-set channeling and how to create a set constraint
 * @author Jean-Guillaume FAGES (cosling)
 * @version Choco Solver 4.0.4
 * @version Choco Graph 4.2.0
 */
public class DomSetProblem {

	public static void main(String[] args){
		// INPUT GRAPH
		int n = 6;
		UndirectedGraph inputGraph = new UndirectedGraph(n, SetType.BITSET, true);
		for(int[] edge:new int[][]{{0,1},{1,2},{0,3},{1,3},{2,4},{3,4},{4,5}})
			inputGraph.addEdge(edge[0],edge[1]);

		GraphModel model = new GraphModel();

		// GRAPH VARIABLE : initial domain (from https://en.wikipedia.org/wiki/Dominating_set)
		UndirectedGraph GUB = new UndirectedGraph(model, n, SetType.BITSET, false);
		UndirectedGraph GLB = new UndirectedGraph(model, n, SetType.BITSET, false);
		for(int i:inputGraph.getNodes()){
			GUB.addNode(i);
			for(int j:inputGraph.getNeighOf(i)){
				GUB.addEdge(i,j);
			}
		}
		UndirectedGraphVar subgraph = model.graphVar("g", GLB, GUB);
		model.connected(subgraph).post();

		// DOMINATING SET
		BoolVar[] domSet = model.nodeSetBool(subgraph);
		IntVar size = model.intVar(0,n);
		model.setObjective(Model.MINIMIZE,size);
		model.sum(domSet,"=",size).post();
		for(int i=0;i< n;i++){
			int idx = 0;
			BoolVar[] cluster = new BoolVar[1+inputGraph.getNeighOf(i).size()];
			cluster[idx++] = domSet[i];
			for(int j:inputGraph.getNeighOf(i))cluster[idx++] = domSet[j];
			model.or(cluster).post();
		}

		//SEARCH (domset only -> then all edges can be used)
		model.getSolver().setSearch(Search.intVarSearch(variables -> {
			int min = -1;
			int size1 = Integer.MAX_VALUE/10;
			for(int i=0;i< n;i++){
				if(!variables[i].isInstantiated()){
					if(size1 > inputGraph.getNeighOf(i).size()){
						size1 = inputGraph.getNeighOf(i).size();
						min = i;
					}
				}
			}
			return min==-1?null:variables[min];
		}, new IntDomainMin(),domSet));

		System.out.println("input graph : "+inputGraph);
		System.out.println("start solving...");
		while (model.getSolver().solve()){
			System.out.println("dominating set : ");
			for(int i=0;i< n;i++)if(domSet[i].isInstantiatedTo(1)) System.out.println("\t"+i);
		}
	}
}
            
        

Optimal solution:

            
input graph : nodes :
[0,5]
neighbors :
0 -> {1 3 }
1 -> {0 2 3 }
2 -> {1 4 }
3 -> {0 1 4 }
4 -> {2 3 5 }
5 -> {4 }

start solving...
dominating set :
	3
	4