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