    001    package ifs.example.csp;
    002
    003    import ifs.util.*;
    004    import ifs.model.*;
    005    import java.util.*;
    006
    007    /**
    008     * Random Binary CSP with kernels.
    009     * <br><br>
    010     * This class only implements the generation of Structured CSP problem.<br>
    011     * In Structured CSP, variables are divided into several kernels (some variables may remain ouside kernels).
    012     * Different constraints (in density and tightnes) are generated according to whether variables are from the same kernel or not.
    013     * <br><br>
    014     * Model parameters:
    015     * <br>
    016     * <table border='1'><tr><th>Parameter</th><th>Type</th><th>Comment</th></tr>
    017     * <tr><td>CSP.NrVariables</td><td>{@link Integer}</td><td>Number of variables</td></tr>
    018     * <tr><td>CSP.DomainSize</td><td>{@link Integer}</td><td>Number of values for each variable</td></tr>
    019     * <tr><td>CSP.NrKernels</td><td>{@link Integer}</td><td>Number of kernels</td></tr>
    020     * <tr><td>CSP.KernelSize</td><td>{@link Integer}</td><td>Number of variables in each kernel</td></tr>
    021     * <tr><td>CSP.Tightness</td><td>{@link Double}</td><td>Tightness of constraints outside kernels</td></tr>
    022     * <tr><td>CSP.KernelTightness</td><td>{@link Double}</td><td>Tightness of constraints inside a kernel</td></tr>
    023     * <tr><td>CSP.Density</td><td>{@link Double}</td><td>Density of constraints outside kernels</td></tr>
    024     * <tr><td>CSP.KernelDensity</td><td>{@link Double}</td><td>Density of constraints inside a kernel</td></tr>
    025     * <tr><td>General.MPP</td><td>{@link String}</td><td>Minimal perturbation problem --> generate initial assignment</td></tr>
    026     * </table>
    027     * <br>
    028     *
    029     * @author <a href="mailto:muller@ktiml.mff.cuni.cz">Tomáš Müller</a>
    030     * @version 1.0
    031     */
    032    public class StructuredCSPModel extends Model {
    033        private static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(StructuredCSPModel.class);
    034        private DataProperties iProperties = null;
    035
    036        /** Constructor */
    037        public StructuredCSPModel(DataProperties properties, long seed) {
    038            iProperties = properties;
    039            generate(seed);
    040        }
    041
    042        private void swap(Variable[][] allPairs, int first, int second) {
    043            Variable[] a = allPairs[first];
    044            allPairs[first]=allPairs[second];
    045            allPairs[second]=a;
    046        }
    047
    048        private void buildBinaryConstraintGraph(Vector variables, Vector constraints, Random rnd) {
    049            int numberOfAllPairs = variables.size()*(variables.size()-1)/2;
    050            Variable[][] allPairs = new Variable[numberOfAllPairs][];
    051            int idx=0;
    052            for (Enumeration i1=variables.elements();i1.hasMoreElements();) {
    053                Variable v1 = (Variable)i1.nextElement();
    054                for (Enumeration i2=variables.elements();i2.hasMoreElements();) {
    055                    Variable v2 = (Variable)i2.nextElement();
    056                    if (v1.getId()>=v2.getId()) continue;
    057                    allPairs[idx++]=new Variable[] {v1,v2};
    058                }
    059            }
    060            idx = 0;
    061            for (Enumeration i1=constraints.elements();i1.hasMoreElements();) {
    062                CSPBinaryConstraint c = (CSPBinaryConstraint) i1.nextElement();
    063                swap(allPairs, idx, idx+(int)(rnd.nextDouble()*(numberOfAllPairs-idx)));
    064                    idx++;
    065            }
    066            idx = 0;
    067            for (Enumeration i1=constraints.elements();i1.hasMoreElements();) {
    068                CSPBinaryConstraint c = (CSPBinaryConstraint) i1.nextElement();
    069                c.addVariable(allPairs[idx][0]);
    070                c.addVariable(allPairs[idx][1]);
    071                idx++;
    072            }
    073        }
    074
    075        private void buildBinaryConstraintGraph2(Vector variables, int numberOfAllPairs, Vector constraints, Random rnd) {
    076            Variable[][] allPairs = new Variable[numberOfAllPairs][];
    077            int idx=0;
    078            for (Enumeration i1=variables.elements();i1.hasMoreElements();) {
    079                CSPVariable v1 = (CSPVariable)i1.nextElement();
    080                for (Enumeration i2=variables.elements();i2.hasMoreElements();) {
    081                    CSPVariable v2 = (CSPVariable)i2.nextElement();
    082                    if (v1.getId()>=v2.getId()) continue;
    083                    if (v1.getKernelId()>=0 && v1.getKernelId()==v2.getKernelId()) continue;
    084                    allPairs[idx++]=new Variable[] {v1,v2};
    085                }
    086            }
    087            idx = 0;
    088            for (Enumeration i1=constraints.elements();i1.hasMoreElements();) {
    089                CSPBinaryConstraint c = (CSPBinaryConstraint) i1.nextElement();
    090                swap(allPairs, idx, idx+(int)(rnd.nextDouble()*(numberOfAllPairs-idx)));
    091                    idx++;
    092            }
    093            idx = 0;
    094            for (Enumeration i1=constraints.elements();i1.hasMoreElements();) {
    095                CSPBinaryConstraint c = (CSPBinaryConstraint) i1.nextElement();
    096                c.addVariable(allPairs[idx][0]);
    097                c.addVariable(allPairs[idx][1]);
    098                idx++;
    099            }
    100        }
    101
    102        private void generate(long seed) {
    103            int nrVariables = iProperties.getPropertyInt("CSP.NrVariables", 60);
    104            int nrValues = iProperties.getPropertyInt("CSP.DomainSize", 15);
    105            int nrKernels = iProperties.getPropertyInt("CSP.NrKernels", 2);
    106            int nrKernelVariables = iProperties.getPropertyInt("CSP.KernelSize", 8);
    107
    108            int nrPairValues = nrValues*nrValues;
    109            float tightnessPerc = iProperties.getPropertyFloat("CSP.Tightness", 0.01f);
    110            float kernelTightnessPerc = iProperties.getPropertyFloat("CSP.KernelTightness", 0.097f);
    111            int nrCompatiblePairs = (int)Math.round((1.0-tightnessPerc)*nrPairValues);
    112            int kernelNrCompatiblePairs = (int)Math.round((1.0-kernelTightnessPerc)*nrPairValues);
    113
    114            int nrPairVariables = (nrVariables*(nrVariables-1))/2;
    115            int nrPairKernelVariables = (nrKernelVariables*(nrKernelVariables-1))/2;
    116            nrPairVariables -= nrKernels * nrPairKernelVariables;
    117            float densityPerc = iProperties.getPropertyFloat("CSP.Density", 0.01f);
    118            float densityKernelPerc = iProperties.getPropertyFloat("CSP.KernelDensity", 0.097f);
    119            int density = (int)Math.round(densityPerc*nrPairVariables);
    120            int kernelDensity = (int)Math.round(densityKernelPerc*nrPairKernelVariables);
    121
    122            Random rnd = new Random(seed);
    123            Vector generalVariables = new Vector(nrVariables-(nrKernels*nrKernelVariables));
    124            int varId = 1;
    125            for (int i=0;i<nrVariables-(nrKernels*nrKernelVariables);i++) {
    126                CSPVariable var = new CSPVariable(varId++,nrValues);
    127                generalVariables.addElement(var);
    128                addVariable(var);
    129            }
    130            sLogger.debug("Created "+generalVariables.size()+" general variables.");
    131            Vector[] kernelVariables = new Vector[nrKernels];
    132            for (int k=0;k<nrKernels;k++) {
    133                kernelVariables[k]=new Vector(nrKernelVariables);
    134                for (int i=0;i<nrKernelVariables;i++) {
    135                    CSPVariable var = new CSPVariable(varId++,nrValues,k);
    136                    kernelVariables[k].addElement(var);
    137                    addVariable(var);
    138                }
    139                if (k==0) sLogger.debug("Created "+kernelVariables[0].size()+" kernel variables (per kernel).");
    140            }
    141            sLogger.debug("Created "+variables().size()+" variables at total.");
    142            int constId = 1;
    143            Vector generalConstraints = new Vector(density);
    144            for (int i=0;i<density;i++) {
    145                CSPBinaryConstraint c = new CSPBinaryConstraint(constId++,nrCompatiblePairs);
    146                generalConstraints.addElement(c);
    147                addConstraint(c);
    148            }
    149            sLogger.debug("Created "+generalConstraints.size()+" general constraints (tightness="+tightnessPerc+").");
    150            Vector[] kernelConstraints = new Vector[nrKernels];
    151            for (int k=0;k<nrKernels;k++) {
    152                kernelConstraints[k] = new Vector(kernelDensity);
    153                for (int i=0;i<kernelDensity;i++) {
    154                    CSPBinaryConstraint c = new CSPBinaryConstraint(constId++,kernelNrCompatiblePairs);
    155                    kernelConstraints[k].addElement(c);
    156                    addConstraint(c);
    157                }
    158                if (k==0) sLogger.debug("Created "+kernelConstraints[0].size()+" kernel constraints (per kernel, tightness="+kernelTightnessPerc+").");
    159            }
    160            sLogger.debug("Created "+constraints().size()+" constraints at total.");
    161
    162            for (int k=0;k<nrKernels;k++) {
    163                buildBinaryConstraintGraph(kernelVariables[k], kernelConstraints[k], rnd);
    164            }
    165            buildBinaryConstraintGraph2(variables(), nrPairVariables, generalConstraints, rnd);
    166
    167            for (Enumeration i=constraints().elements();i.hasMoreElements();) {
    168                CSPBinaryConstraint constraint = (CSPBinaryConstraint)i.nextElement();
    169                constraint.init(rnd);
    170            }
    171
    172            if (iProperties.getPropertyBoolean("General.MPP",false)) {
    173                for (Enumeration i=variables().elements();i.hasMoreElements();) {
    174                    CSPVariable variable = (CSPVariable)i.nextElement();
    175                    variable.generateInitialValue(rnd);
    176                }
    177            }
    178        }
    179
    180        /** Return information table */
    181        public Hashtable getInfo() {
    182            Hashtable ret = super.getInfo();
    183            ret.put("Solution value", String.valueOf(getTotalValue()));
    184            return ret;
    185        }
    186    }