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