001package net.sf.cpsolver.ifs.example.csp; 002 003import java.util.ArrayList; 004import java.util.List; 005import java.util.Map; 006import java.util.Random; 007 008import net.sf.cpsolver.ifs.model.Constraint; 009import net.sf.cpsolver.ifs.model.Model; 010import net.sf.cpsolver.ifs.util.DataProperties; 011 012/** 013 * Random Binary CSP with kernels. <br> 014 * <br> 015 * This class only implements the generation of Structured CSP problem.<br> 016 * In Structured CSP, variables are divided into several kernels (some variables 017 * may remain ouside kernels). Different constraints (in density and tightnes) 018 * are generated according to whether variables are from the same kernel or not. <br> 019 * <br> 020 * Model parameters: <br> 021 * <table border='1'> 022 * <tr> 023 * <th>Parameter</th> 024 * <th>Type</th> 025 * <th>Comment</th> 026 * </tr> 027 * <tr> 028 * <td>CSP.NrVariables</td> 029 * <td>{@link Integer}</td> 030 * <td>Number of variables</td> 031 * </tr> 032 * <tr> 033 * <td>CSP.DomainSize</td> 034 * <td>{@link Integer}</td> 035 * <td>Number of values for each variable</td> 036 * </tr> 037 * <tr> 038 * <td>CSP.NrKernels</td> 039 * <td>{@link Integer}</td> 040 * <td>Number of kernels</td> 041 * </tr> 042 * <tr> 043 * <td>CSP.KernelSize</td> 044 * <td>{@link Integer}</td> 045 * <td>Number of variables in each kernel</td> 046 * </tr> 047 * <tr> 048 * <td>CSP.Tightness</td> 049 * <td>{@link Double}</td> 050 * <td>Tightness of constraints outside kernels</td> 051 * </tr> 052 * <tr> 053 * <td>CSP.KernelTightness</td> 054 * <td>{@link Double}</td> 055 * <td>Tightness of constraints inside a kernel</td> 056 * </tr> 057 * <tr> 058 * <td>CSP.Density</td> 059 * <td>{@link Double}</td> 060 * <td>Density of constraints outside kernels</td> 061 * </tr> 062 * <tr> 063 * <td>CSP.KernelDensity</td> 064 * <td>{@link Double}</td> 065 * <td>Density of constraints inside a kernel</td> 066 * </tr> 067 * <tr> 068 * <td>General.MPP</td> 069 * <td>{@link String}</td> 070 * <td>Minimal perturbation problem --> generate initial assignment</td> 071 * </tr> 072 * </table> 073 * <br> 074 * 075 * @version IFS 1.2 (Iterative Forward Search)<br> 076 * Copyright (C) 2006 - 2010 Tomáš Müller<br> 077 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 078 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 079 * <br> 080 * This library is free software; you can redistribute it and/or modify 081 * it under the terms of the GNU Lesser General Public License as 082 * published by the Free Software Foundation; either version 3 of the 083 * License, or (at your option) any later version. <br> 084 * <br> 085 * This library is distributed in the hope that it will be useful, but 086 * WITHOUT ANY WARRANTY; without even the implied warranty of 087 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 088 * Lesser General Public License for more details. <br> 089 * <br> 090 * You should have received a copy of the GNU Lesser General Public 091 * License along with this library; if not see 092 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 093 */ 094public class StructuredCSPModel extends Model<CSPVariable, CSPValue> { 095 private static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(StructuredCSPModel.class); 096 private DataProperties iProperties = null; 097 098 /** Constructor */ 099 public StructuredCSPModel(DataProperties properties, long seed) { 100 iProperties = properties; 101 generate(seed); 102 } 103 104 private void swap(CSPVariable[][] allPairs, int first, int second) { 105 CSPVariable[] a = allPairs[first]; 106 allPairs[first] = allPairs[second]; 107 allPairs[second] = a; 108 } 109 110 private void buildBinaryConstraintGraph(List<CSPVariable> variables, List<CSPBinaryConstraint> constraints, 111 Random rnd) { 112 int numberOfAllPairs = variables.size() * (variables.size() - 1) / 2; 113 CSPVariable[][] allPairs = new CSPVariable[numberOfAllPairs][]; 114 int idx = 0; 115 for (CSPVariable v1 : variables) { 116 for (CSPVariable v2 : variables) { 117 if (v1.getId() >= v2.getId()) 118 continue; 119 allPairs[idx++] = new CSPVariable[] { v1, v2 }; 120 } 121 } 122 for (idx = 0; idx < constraints.size(); idx++) { 123 swap(allPairs, idx, idx + (int) (rnd.nextDouble() * (numberOfAllPairs - idx))); 124 } 125 idx = 0; 126 for (CSPBinaryConstraint c : constraints) { 127 c.addVariable(allPairs[idx][0]); 128 c.addVariable(allPairs[idx][1]); 129 idx++; 130 } 131 } 132 133 private void buildBinaryConstraintGraph2(List<CSPVariable> variables, int numberOfAllPairs, 134 List<CSPBinaryConstraint> constraints, Random rnd) { 135 CSPVariable[][] allPairs = new CSPVariable[numberOfAllPairs][]; 136 int idx = 0; 137 for (CSPVariable v1 : variables) { 138 for (CSPVariable v2 : variables) { 139 if (v1.getId() >= v2.getId()) 140 continue; 141 if (v1.getKernelId() >= 0 && v1.getKernelId() == v2.getKernelId()) 142 continue; 143 allPairs[idx++] = new CSPVariable[] { v1, v2 }; 144 } 145 } 146 for (idx = 0; idx < constraints.size(); idx++) { 147 swap(allPairs, idx, idx + (int) (rnd.nextDouble() * (numberOfAllPairs - idx))); 148 } 149 idx = 0; 150 for (CSPBinaryConstraint c : constraints) { 151 c.addVariable(allPairs[idx][0]); 152 c.addVariable(allPairs[idx][1]); 153 idx++; 154 } 155 } 156 157 @SuppressWarnings("unchecked") 158 private void generate(long seed) { 159 int nrVariables = iProperties.getPropertyInt("CSP.NrVariables", 60); 160 int nrValues = iProperties.getPropertyInt("CSP.DomainSize", 15); 161 int nrKernels = iProperties.getPropertyInt("CSP.NrKernels", 2); 162 int nrKernelVariables = iProperties.getPropertyInt("CSP.KernelSize", 8); 163 164 int nrPairValues = nrValues * nrValues; 165 float tightnessPerc = iProperties.getPropertyFloat("CSP.Tightness", 0.01f); 166 float kernelTightnessPerc = iProperties.getPropertyFloat("CSP.KernelTightness", 0.097f); 167 int nrCompatiblePairs = (int) Math.round((1.0 - tightnessPerc) * nrPairValues); 168 int kernelNrCompatiblePairs = (int) Math.round((1.0 - kernelTightnessPerc) * nrPairValues); 169 170 int nrPairVariables = (nrVariables * (nrVariables - 1)) / 2; 171 int nrPairKernelVariables = (nrKernelVariables * (nrKernelVariables - 1)) / 2; 172 nrPairVariables -= nrKernels * nrPairKernelVariables; 173 float densityPerc = iProperties.getPropertyFloat("CSP.Density", 0.01f); 174 float densityKernelPerc = iProperties.getPropertyFloat("CSP.KernelDensity", 0.097f); 175 int density = Math.round(densityPerc * nrPairVariables); 176 int kernelDensity = Math.round(densityKernelPerc * nrPairKernelVariables); 177 178 Random rnd = new Random(seed); 179 List<CSPVariable> generalVariables = new ArrayList<CSPVariable>(nrVariables - (nrKernels * nrKernelVariables)); 180 int varId = 1; 181 for (int i = 0; i < nrVariables - (nrKernels * nrKernelVariables); i++) { 182 CSPVariable var = new CSPVariable(varId++, nrValues); 183 generalVariables.add(var); 184 addVariable(var); 185 } 186 sLogger.debug("Created " + generalVariables.size() + " general variables."); 187 List<CSPVariable>[] kernelVariables = new ArrayList[nrKernels]; 188 for (int k = 0; k < nrKernels; k++) { 189 kernelVariables[k] = new ArrayList<CSPVariable>(nrKernelVariables); 190 for (int i = 0; i < nrKernelVariables; i++) { 191 CSPVariable var = new CSPVariable(varId++, nrValues, k); 192 kernelVariables[k].add(var); 193 addVariable(var); 194 } 195 if (k == 0) 196 sLogger.debug("Created " + kernelVariables[0].size() + " kernel variables (per kernel)."); 197 } 198 sLogger.debug("Created " + variables().size() + " variables at total."); 199 int constId = 1; 200 List<CSPBinaryConstraint> generalConstraints = new ArrayList<CSPBinaryConstraint>(density); 201 for (int i = 0; i < density; i++) { 202 CSPBinaryConstraint c = new CSPBinaryConstraint(constId++, nrCompatiblePairs); 203 generalConstraints.add(c); 204 addConstraint(c); 205 } 206 sLogger.debug("Created " + generalConstraints.size() + " general constraints (tightness=" + tightnessPerc 207 + ")."); 208 List<CSPBinaryConstraint>[] kernelConstraints = new List[nrKernels]; 209 for (int k = 0; k < nrKernels; k++) { 210 kernelConstraints[k] = new ArrayList<CSPBinaryConstraint>(kernelDensity); 211 for (int i = 0; i < kernelDensity; i++) { 212 CSPBinaryConstraint c = new CSPBinaryConstraint(constId++, kernelNrCompatiblePairs); 213 kernelConstraints[k].add(c); 214 addConstraint(c); 215 } 216 if (k == 0) 217 sLogger.debug("Created " + kernelConstraints[0].size() + " kernel constraints (per kernel, tightness=" 218 + kernelTightnessPerc + ")."); 219 } 220 sLogger.debug("Created " + constraints().size() + " constraints at total."); 221 222 for (int k = 0; k < nrKernels; k++) { 223 buildBinaryConstraintGraph(kernelVariables[k], kernelConstraints[k], rnd); 224 } 225 buildBinaryConstraintGraph2(variables(), nrPairVariables, generalConstraints, rnd); 226 227 for (Constraint<CSPVariable, CSPValue> c : constraints()) { 228 CSPBinaryConstraint constraint = (CSPBinaryConstraint) c; 229 constraint.init(rnd); 230 } 231 232 if (iProperties.getPropertyBoolean("General.MPP", false)) { 233 for (CSPVariable variable : variables()) { 234 variable.generateInitialValue(rnd); 235 } 236 } 237 } 238 239 /** Return information table */ 240 @Override 241 public Map<String, String> getInfo() { 242 Map<String, String> ret = super.getInfo(); 243 ret.put("Solution value", String.valueOf(getTotalValue())); 244 return ret; 245 } 246}