Choco Solver



Recherche d'un ensemble dominant avec Choco Solver

Etant donné un graphe non-orienté, un ensemble dominant est un sous-ensemble de noeuds tel que chaque noeud du graphe peut-être connecté à ce sous-ensemble par au plus une arrête. Dans cet exemple nous cherchons un ensemble dominant de cardinalité minimale et tel que le sous-graphe induit par cet ensemble soit connexe.

Cet exemple illustre comment hybrider une variable graphe avec des variables booléennes représentant l’ensemble des noeuds. Remarquez que la variable de graphe n’est qu’un support à la contrainte globale de connexité mais ne constitue pas une variable de décision: il ne sert à rien de brancher sur les arcs du graphe.

Nous pouvons préciser une heuristique visant à retirer d’abord les noeuds de faible degré. Cela permettra a priori d’avoir une bonne première 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);
		}
	}
}
            
        

solution optimale:


            
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