    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 &rarr; 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}