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'><caption>Related Solver Parameters</caption> 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 * @author Tomáš Müller 078 * @version IFS 1.3 (Iterative Forward Search)<br> 079 * Copyright (C) 2006 - 2014 Tomáš Müller<br> 080 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 081 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 082 * <br> 083 * This library is free software; you can redistribute it and/or modify 084 * it under the terms of the GNU Lesser General Public License as 085 * published by the Free Software Foundation; either version 3 of the 086 * License, or (at your option) any later version. <br> 087 * <br> 088 * This library is distributed in the hope that it will be useful, but 089 * WITHOUT ANY WARRANTY; without even the implied warranty of 090 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 091 * Lesser General Public License for more details. <br> 092 * <br> 093 * You should have received a copy of the GNU Lesser General Public 094 * License along with this library; if not see 095 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 096 */ 097public class StructuredCSPModel extends Model<CSPVariable, CSPValue> { 098 private static org.apache.logging.log4j.Logger sLogger = org.apache.logging.log4j.LogManager.getLogger(StructuredCSPModel.class); 099 private DataProperties iProperties = null; 100 101 /** Constructor 102 * @param properties solver configuration 103 * @param seed random seed 104 **/ 105 public StructuredCSPModel(DataProperties properties, long seed) { 106 iProperties = properties; 107 generate(seed); 108 } 109 110 private void swap(CSPVariable[][] allPairs, int first, int second) { 111 CSPVariable[] a = allPairs[first]; 112 allPairs[first] = allPairs[second]; 113 allPairs[second] = a; 114 } 115 116 private void buildBinaryConstraintGraph(List<CSPVariable> variables, List<CSPBinaryConstraint> constraints, 117 Random rnd) { 118 int numberOfAllPairs = variables.size() * (variables.size() - 1) / 2; 119 CSPVariable[][] allPairs = new CSPVariable[numberOfAllPairs][]; 120 int idx = 0; 121 for (CSPVariable v1 : variables) { 122 for (CSPVariable v2 : variables) { 123 if (v1.getId() >= v2.getId()) 124 continue; 125 allPairs[idx++] = new CSPVariable[] { v1, v2 }; 126 } 127 } 128 for (idx = 0; idx < constraints.size(); idx++) { 129 swap(allPairs, idx, idx + (int) (rnd.nextDouble() * (numberOfAllPairs - idx))); 130 } 131 idx = 0; 132 for (CSPBinaryConstraint c : constraints) { 133 c.addVariable(allPairs[idx][0]); 134 c.addVariable(allPairs[idx][1]); 135 idx++; 136 } 137 } 138 139 private void buildBinaryConstraintGraph2(List<CSPVariable> variables, int numberOfAllPairs, 140 List<CSPBinaryConstraint> constraints, Random rnd) { 141 CSPVariable[][] allPairs = new CSPVariable[numberOfAllPairs][]; 142 int idx = 0; 143 for (CSPVariable v1 : variables) { 144 for (CSPVariable v2 : variables) { 145 if (v1.getId() >= v2.getId()) 146 continue; 147 if (v1.getKernelId() >= 0 && v1.getKernelId() == v2.getKernelId()) 148 continue; 149 allPairs[idx++] = new CSPVariable[] { v1, v2 }; 150 } 151 } 152 for (idx = 0; idx < constraints.size(); idx++) { 153 swap(allPairs, idx, idx + (int) (rnd.nextDouble() * (numberOfAllPairs - idx))); 154 } 155 idx = 0; 156 for (CSPBinaryConstraint c : constraints) { 157 c.addVariable(allPairs[idx][0]); 158 c.addVariable(allPairs[idx][1]); 159 idx++; 160 } 161 } 162 163 @SuppressWarnings("unchecked") 164 private void generate(long seed) { 165 int nrVariables = iProperties.getPropertyInt("CSP.NrVariables", 60); 166 int nrValues = iProperties.getPropertyInt("CSP.DomainSize", 15); 167 int nrKernels = iProperties.getPropertyInt("CSP.NrKernels", 2); 168 int nrKernelVariables = iProperties.getPropertyInt("CSP.KernelSize", 8); 169 170 int nrPairValues = nrValues * nrValues; 171 float tightnessPerc = iProperties.getPropertyFloat("CSP.Tightness", 0.01f); 172 float kernelTightnessPerc = iProperties.getPropertyFloat("CSP.KernelTightness", 0.097f); 173 int nrCompatiblePairs = (int) Math.round((1.0 - tightnessPerc) * nrPairValues); 174 int kernelNrCompatiblePairs = (int) Math.round((1.0 - kernelTightnessPerc) * nrPairValues); 175 176 int nrPairVariables = (nrVariables * (nrVariables - 1)) / 2; 177 int nrPairKernelVariables = (nrKernelVariables * (nrKernelVariables - 1)) / 2; 178 nrPairVariables -= nrKernels * nrPairKernelVariables; 179 float densityPerc = iProperties.getPropertyFloat("CSP.Density", 0.01f); 180 float densityKernelPerc = iProperties.getPropertyFloat("CSP.KernelDensity", 0.097f); 181 int density = Math.round(densityPerc * nrPairVariables); 182 int kernelDensity = Math.round(densityKernelPerc * nrPairKernelVariables); 183 184 Random rnd = new Random(seed); 185 List<CSPVariable> generalVariables = new ArrayList<CSPVariable>(nrVariables - (nrKernels * nrKernelVariables)); 186 int varId = 1; 187 for (int i = 0; i < nrVariables - (nrKernels * nrKernelVariables); i++) { 188 CSPVariable var = new CSPVariable(varId++, nrValues); 189 generalVariables.add(var); 190 addVariable(var); 191 } 192 sLogger.debug("Created " + generalVariables.size() + " general variables."); 193 List<CSPVariable>[] kernelVariables = new ArrayList[nrKernels]; 194 for (int k = 0; k < nrKernels; k++) { 195 kernelVariables[k] = new ArrayList<CSPVariable>(nrKernelVariables); 196 for (int i = 0; i < nrKernelVariables; i++) { 197 CSPVariable var = new CSPVariable(varId++, nrValues, k); 198 kernelVariables[k].add(var); 199 addVariable(var); 200 } 201 if (k == 0) 202 sLogger.debug("Created " + kernelVariables[0].size() + " kernel variables (per kernel)."); 203 } 204 sLogger.debug("Created " + variables().size() + " variables at total."); 205 int constId = 1; 206 List<CSPBinaryConstraint> generalConstraints = new ArrayList<CSPBinaryConstraint>(density); 207 for (int i = 0; i < density; i++) { 208 CSPBinaryConstraint c = new CSPBinaryConstraint(constId++, nrCompatiblePairs); 209 generalConstraints.add(c); 210 addConstraint(c); 211 } 212 sLogger.debug("Created " + generalConstraints.size() + " general constraints (tightness=" + tightnessPerc 213 + ")."); 214 List<CSPBinaryConstraint>[] kernelConstraints = new List[nrKernels]; 215 for (int k = 0; k < nrKernels; k++) { 216 kernelConstraints[k] = new ArrayList<CSPBinaryConstraint>(kernelDensity); 217 for (int i = 0; i < kernelDensity; i++) { 218 CSPBinaryConstraint c = new CSPBinaryConstraint(constId++, kernelNrCompatiblePairs); 219 kernelConstraints[k].add(c); 220 addConstraint(c); 221 } 222 if (k == 0) 223 sLogger.debug("Created " + kernelConstraints[0].size() + " kernel constraints (per kernel, tightness=" 224 + kernelTightnessPerc + ")."); 225 } 226 sLogger.debug("Created " + constraints().size() + " constraints at total."); 227 228 for (int k = 0; k < nrKernels; k++) { 229 buildBinaryConstraintGraph(kernelVariables[k], kernelConstraints[k], rnd); 230 } 231 buildBinaryConstraintGraph2(variables(), nrPairVariables, generalConstraints, rnd); 232 233 for (Constraint<CSPVariable, CSPValue> c : constraints()) { 234 CSPBinaryConstraint constraint = (CSPBinaryConstraint) c; 235 constraint.init(rnd); 236 } 237 238 if (iProperties.getPropertyBoolean("General.MPP", false)) { 239 for (CSPVariable variable : variables()) { 240 variable.generateInitialValue(rnd); 241 } 242 } 243 } 244 245 /** Return information table */ 246 @Override 247 public Map<String, String> getInfo(Assignment<CSPVariable, CSPValue> assignment) { 248 Map<String, String> ret = super.getInfo(assignment); 249 ret.put("Solution value", String.valueOf(getTotalValue(assignment))); 250 return ret; 251 } 252}