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    }