001 package net.sf.cpsolver.ifs.example.csp;
002
003 import java.util.ArrayList;
004 import java.util.List;
005 import java.util.Map;
006 import java.util.Random;
007
008 import net.sf.cpsolver.ifs.model.Constraint;
009 import net.sf.cpsolver.ifs.model.Model;
010 import 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 Tomas Muller<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 */
094 public 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 }