Want more features on Pastebin? Sign Up, it's FREE!
Guest

Class Example

By: a guest on Feb 10th, 2013  |  syntax: Java  |  size: 21.44 KB  |  views: 51  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. /*
  2.  * To change this template, choose Tools | Templates
  3.  * and open the template in the editor.
  4.  */
  5. package Transporte;
  6.  
  7. /**
  8.  *
  9.  * @author oarboleda
  10.  */
  11. /**
  12.  *  Examples.java
  13.  *  This file is part of JaCoP.
  14.  *
  15.  *  JaCoP is a Java Constraint Programming solver.
  16.  *     
  17.  *      Copyright (C) 2000-2008 Krzysztof Kuchcinski and Radoslaw Szymanek
  18.  *
  19.  *  This program is free software: you can redistribute it and/or modify
  20.  *  it under the terms of the GNU Affero General Public License as published by
  21.  *  the Free Software Foundation, either version 3 of the License, or
  22.  *  (at your option) any later version.
  23.  *
  24.  *  This program is distributed in the hope that it will be useful,
  25.  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  26.  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  27.  *  GNU Affero General Public License for more details.
  28.  *  
  29.  *  Notwithstanding any other provision of this License, the copyright
  30.  *  owners of this work supplement the terms of this License with terms
  31.  *  prohibiting misrepresentation of the origin of this work and requiring
  32.  *  that modified versions of this work be marked in reasonable ways as
  33.  *  different from the original version. This supplement of the license
  34.  *  terms is in accordance with Section 7 of GNU Affero General Public
  35.  *  License version 3.
  36.  *
  37.  *  You should have received a copy of the GNU Affero General Public License
  38.  *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
  39.  *
  40.  */
  41.  
  42. import JaCoP.constraints.Constraint;
  43. import JaCoP.core.IntVar;
  44. import JaCoP.core.Store;
  45. import JaCoP.core.Var;
  46. import JaCoP.search.CreditCalculator;
  47. import JaCoP.search.DepthFirstSearch;
  48. import JaCoP.search.IndomainMedian;
  49. import JaCoP.search.IndomainMiddle;
  50. import JaCoP.search.IndomainMin;
  51. import JaCoP.search.IndomainSimpleRandom;
  52. import JaCoP.search.LDS;
  53. import JaCoP.search.MaxRegret;
  54. import JaCoP.search.MostConstrainedStatic;
  55. import JaCoP.search.NoGoodsCollector;
  56. import JaCoP.search.Search;
  57. import JaCoP.search.SelectChoicePoint;
  58. import JaCoP.search.Shaving;
  59. import JaCoP.search.SimpleSelect;
  60. import JaCoP.search.SmallestDomain;
  61. import JaCoP.search.SmallestMin;
  62. import JaCoP.search.WeightedDegree;
  63.  
  64. import java.util.*;
  65.  
  66. /**
  67.  * It is an abstract class to describe all necessary functions of any store.
  68.  *
  69.  * @author Radoslaw Szymanek and Krzysztof Kuchcinski
  70.  * @version 3.0
  71.  */
  72.  
  73. public abstract class Example {
  74.  
  75.         /**
  76.          * It contains all variables used within a specific example.
  77.          */
  78.         public ArrayList<Var> vars;
  79.        
  80.         /**
  81.          * It specifies the cost function, null if no cost function is used.
  82.          */
  83.         public IntVar cost;
  84.        
  85.         /**
  86.          * It specifies the constraint store responsible for holding information
  87.          * about constraints and variables.
  88.          */
  89.         public Store store;
  90.        
  91.         /**
  92.          * It specifies the search procedure used by a given example.
  93.          */
  94.         public Search search;  
  95.        
  96.         /**
  97.          * It specifies a standard way of modeling the problem.
  98.          */
  99.         public abstract void model();
  100.        
  101.         /**
  102.          * It specifies simple search method based on input order and lexigraphical
  103.          * ordering of values.
  104.          *
  105.          * @return true if there is a solution, false otherwise.
  106.          */
  107.         public boolean search() {
  108.                
  109.                 long T1, T2;
  110.                 T1 = System.currentTimeMillis();
  111.                
  112.                 SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]), null,
  113.                                 new IndomainMin());
  114.  
  115.                 search = new DepthFirstSearch();
  116.  
  117.                 boolean result = search.labeling(store, select);
  118.  
  119.                 if (result)
  120.                         store.print();
  121.  
  122.                 T2 = System.currentTimeMillis();
  123.  
  124.                 System.out.println("\n\t*** Execution time = " + (T2 - T1) + " ms");
  125.                
  126.                 System.out.println();
  127.                 System.out.print(search.getNodes() + "\t");
  128.                 System.out.print(search.getDecisions() + "\t");
  129.                 System.out.print(search.getWrongDecisions() + "\t");
  130.                 System.out.print(search.getBacktracks() + "\t");
  131.                 System.out.print(search.getMaximumDepth() + "\t");
  132.                
  133.                 return result;
  134.                
  135.         }      
  136.  
  137.         /**
  138.          * It specifies simple search method based on input order and lexigraphical
  139.          * ordering of values. It optimizes the solution by minimizing the cost function.
  140.          *
  141.          * @return true if there is a solution, false otherwise.
  142.          */
  143.         public boolean searchOptimal() {
  144.                
  145.                 long T1, T2;
  146.                 T1 = System.currentTimeMillis();
  147.                
  148.                 SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]), null,
  149.                                 new IndomainMin());
  150.  
  151.                 search = new DepthFirstSearch();
  152.                
  153.                 boolean result = search.labeling(store, select, cost);
  154.  
  155.                 if (result){
  156.                         store.print();
  157.                 }
  158.  
  159.                 T2 = System.currentTimeMillis();
  160.  
  161.                 System.out.println("\n\t*** Execution time = " + (T2 - T1) + " ms");
  162.                
  163.                 return result;
  164.                
  165.         }      
  166.        
  167.        
  168.         /**
  169.          * It searches for all solutions with the optimal value.
  170.          * @return true if any optimal solution has been found.
  171.          */
  172.         public boolean searchAllOptimal() {
  173.                
  174.                 long T1, T2, T;
  175.                 T1 = System.currentTimeMillis();
  176.  
  177.                 SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]), null,
  178.                                                                                                         new IndomainMin());
  179.  
  180.                 search = new DepthFirstSearch();
  181.                 search.getSolutionListener().searchAll(true);
  182.                 search.getSolutionListener().recordSolutions(true);
  183.  
  184.                 boolean result = search.labeling(store, select, cost);
  185.  
  186.                 T2 = System.currentTimeMillis();
  187.                 T = T2 - T1;
  188.                 System.out.println("\n\t*** Execution time = " + T + " ms");
  189.  
  190.                 return result;
  191.                
  192.         }
  193.        
  194.         /**
  195.          * It specifies simple search method based on smallest domain variable order
  196.          * and lexigraphical ordering of values.
  197.          * @param optimal it specifies if the search the optimal solution takes place.
  198.          *
  199.          * @return true if there is a solution, false otherwise.
  200.          */
  201.  
  202.         public boolean searchSmallestDomain(boolean optimal) {
  203.                
  204.                 long T1, T2;
  205.                 T1 = System.currentTimeMillis();
  206.                
  207.                 SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]), new SmallestDomain(),
  208.                                 new IndomainMin());
  209.  
  210.                 search = new DepthFirstSearch();
  211.  
  212.                 boolean result = false;
  213.                
  214.                 if (optimal) {
  215.                         search.labeling(store, select, cost);
  216.                 }
  217.                 else{
  218.                         search.labeling(store, select);
  219. }
  220.                 System.out.println();
  221.                 System.out.print(search.getNodes() + "\t");
  222.                 System.out.print(search.getDecisions() + "\t");
  223.                 System.out.print(search.getWrongDecisions() + "\t");
  224.                 System.out.print(search.getBacktracks() + "\t");
  225.                 System.out.print(search.getMaximumDepth() + "\t");
  226.                
  227.                 if (result)
  228.                         store.print();
  229.  
  230.                 T2 = System.currentTimeMillis();
  231.  
  232.                 System.out.println("\n\t*** Execution time = " + (T2 - T1) + " ms");
  233.                
  234.                 return result;
  235.                
  236.         }      
  237.        
  238.         /**
  239.          * It specifies simple search method based on weighted degree variable order
  240.          * and lexigraphical ordering of values. This search method is rather general
  241.          * any problem good fit. It can be a good first trial to see if the model is
  242.          * correct.
  243.          *
  244.          * @return true if there is a solution, false otherwise.
  245.          */
  246.  
  247.         public boolean searchWeightedDegree() {
  248.                
  249.                 long T1, T2;
  250.                 T1 = System.currentTimeMillis();
  251.                
  252.                 SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]),
  253.                                                             new WeightedDegree(),
  254.                                                             new SmallestDomain(),
  255.                                                             new IndomainMin());
  256.  
  257.                 search = new DepthFirstSearch();
  258.  
  259.                 boolean result = search.labeling(store, select);
  260.  
  261.                 System.out.println();
  262.                 System.out.print(search.getNodes() + "\t");
  263.                 System.out.print(search.getDecisions() + "\t");
  264.                 System.out.print(search.getWrongDecisions() + "\t");
  265.                 System.out.print(search.getBacktracks() + "\t");
  266.                 System.out.print(search.getMaximumDepth() + "\t");
  267.                
  268.                 if (result)
  269.                         store.print();
  270.  
  271.                 T2 = System.currentTimeMillis();
  272.  
  273.                 System.out.println("\n\t*** Execution time = " + (T2 - T1) + " ms");
  274.                
  275.                 return result;
  276.                
  277.         }      
  278.  
  279.         /**
  280.          * It specifies simple search method based variable order which
  281.          * takes into account the number of constraints attached to a variable
  282.          * and lexigraphical ordering of values.
  283.          *
  284.          * @return true if there is a solution, false otherwise.
  285.          */
  286.  
  287.         public boolean searchMostConstrainedStatic() {
  288.                
  289.                 search = new DepthFirstSearch();
  290.  
  291.                 SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]),
  292.                                 new MostConstrainedStatic(), new IndomainMin());
  293.  
  294.                 boolean result = search.labeling(store, select);
  295.  
  296.                 System.out.println();
  297.                 System.out.print(search.getNodes() + "\t");
  298.                 System.out.print(search.getDecisions() + "\t");
  299.                 System.out.print(search.getWrongDecisions() + "\t");
  300.                 System.out.print(search.getBacktracks() + "\t");
  301.                 System.out.print(search.getMaximumDepth() + "\t");
  302.                
  303.                 if (!result)
  304.                         System.out.println("**** No Solution ****");
  305.  
  306.                 return result;
  307.         }
  308.        
  309.         /**
  310.          * It specifies simple search method based on most constrained static and lexigraphical
  311.          * ordering of values. It searches for all solutions.
  312.          *
  313.          * @return true if there is a solution, false otherwise.
  314.          */
  315.  
  316.         public boolean searchAllAtOnce() {
  317.                
  318.                 long T1, T2;
  319.                 T1 = System.currentTimeMillis();               
  320.                
  321.                 SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]),
  322.                                 new MostConstrainedStatic(), new IndomainMin());
  323.  
  324.                 search = new DepthFirstSearch();
  325.                
  326.                 search.getSolutionListener().searchAll(true);
  327.                 search.getSolutionListener().recordSolutions(true);
  328.                 search.setAssignSolution(true);
  329.                
  330.                 boolean result = search.labeling(store, select);
  331.  
  332.                 T2 = System.currentTimeMillis();
  333.  
  334.                 if (result) {
  335.                         System.out.println("Number of solutions " + search.getSolutionListener().solutionsNo());
  336.                         search.printAllSolutions();
  337.                 }
  338.                 else
  339.                         System.out.println("Failed to find any solution");
  340.  
  341.                 System.out.println("\n\t*** Execution time = " + (T2 - T1) + " ms");
  342.  
  343.                 return result;
  344.         }      
  345.        
  346.        
  347.         /**
  348.          * It searches using an input order search with indomain based on middle value.
  349.          * @return true if there is a solution, false otherwise.
  350.          */
  351.         public boolean searchMiddle() {
  352.  
  353.                 long begin = System.currentTimeMillis();
  354.  
  355.                 search = new DepthFirstSearch();
  356.  
  357.                 SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]),
  358.                                                                                                         null, new IndomainMiddle());
  359.  
  360.                 boolean result = search.labeling(store, select);
  361.  
  362.                 long end = System.currentTimeMillis();
  363.  
  364.                 System.out.println("Number of milliseconds " + (end - begin));
  365.  
  366.                 return result;
  367.         }
  368.  
  369.         /**
  370.          * It searches with shaving which is guided by supplied constraints.
  371.          * @param guidingShaving the array of constraints proposing shaving candidates.
  372.          * @param printInfo it specifies if that function should print any info.
  373.          * @return true if the solution was found, false otherwise.
  374.          */
  375.         public boolean shavingSearch(ArrayList<Constraint> guidingShaving, boolean printInfo) {
  376.  
  377.                 Shaving shaving = new Shaving();
  378.                 shaving.setStore(store);
  379.                 shaving.quickShave = true;
  380.  
  381.                 for (Constraint c : guidingShaving)
  382.                         shaving.addShavingConstraint(c);
  383.  
  384.                 long begin = System.currentTimeMillis();
  385.  
  386.                 search = new DepthFirstSearch();
  387.                 search.setPrintInfo(printInfo);
  388.                
  389.                 SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]), null, new IndomainMiddle());
  390.  
  391.                 search.setConsistencyListener(shaving);
  392.                 search.setExitChildListener(shaving);
  393.  
  394.                 boolean result = search.labeling(store, select);
  395.  
  396.                 long end = System.currentTimeMillis();
  397.  
  398.                 if (printInfo) {
  399.                         System.out.println("Number of milliseconds " + (end - begin));
  400.                         System.out.println("Ratio "     + (shaving.successes * 100 / (shaving.successes + shaving.failures)));
  401.  
  402.                         if (result)
  403.                                 store.print();
  404.                 }
  405.                
  406.                 return result;
  407.  
  408.         }
  409.        
  410.         /**
  411.          * It conducts the search with restarts from which the no-goods are derived.
  412.          * Every search contributes with new no-goods which are kept so eventually
  413.          * the search is complete (although can be very expensive to maintain explicitly
  414.          * all no-goods found during search).
  415.          * @return true if there is a solution, false otherwise.
  416.          */
  417.         public boolean searchWithRestarts() {
  418.                
  419.                 // Input Order tie breaking
  420.                 boolean result = false;
  421.                 boolean timeout = true;
  422.                
  423.                 int nodes = 0;
  424.                 int decisions = 0;
  425.                 int backtracks = 0;
  426.                 int wrongDecisions = 0;
  427.  
  428.                 search = new DepthFirstSearch();
  429.  
  430.                 NoGoodsCollector collector = new NoGoodsCollector();
  431.                 search.setExitChildListener(collector);
  432.                 search.setTimeOutListener(collector);
  433.                 search.setExitListener(collector);
  434.  
  435.                 SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]), new SmallestDomain(),
  436.                                 new IndomainSimpleRandom());
  437.                
  438.                 while (timeout) {
  439.  
  440.                         // search.setPrintInfo(false);
  441.                         search.setNodesOut(1000);
  442.  
  443.                         result = search.labeling(store, select);
  444.                         timeout &= collector.timeOut;
  445.                        
  446.                         nodes += search.getNodes();
  447.                         decisions += search.getDecisions();
  448.                         wrongDecisions += search.getWrongDecisions();
  449.                         backtracks += search.getBacktracks();
  450.  
  451.                         search = new DepthFirstSearch();
  452.                         collector = new NoGoodsCollector();
  453.                         search.setExitChildListener(collector);
  454.                         search.setTimeOutListener(collector);
  455.                         search.setExitListener(collector);
  456.  
  457.                 }
  458.  
  459.                 // System.out.println(search.noGoodsVariables);
  460.                 // System.out.println(search.noGoodsValues);
  461.                 // System.out.println(store.watchedConstraints);
  462.  
  463.                 // store.toXCSP2_0();
  464.                 // store.finalizeXCSP2_0(-1, "./", "restarts.xml");
  465.  
  466.                 System.out.println();
  467.                 System.out.print(nodes + "\t");
  468.                 System.out.print(decisions + "\t");
  469.                 System.out.print(wrongDecisions + "\t");
  470.                 System.out.print(backtracks + "\t");
  471.  
  472.                 if (result)
  473.                         System.out.println(1);
  474.                 else
  475.                         System.out.println(0);
  476.  
  477.                 return result;
  478.         }
  479.        
  480.         /**
  481.          * It uses credit search to solve a problem.
  482.          * @param credits the number of credits available.
  483.          * @param backtracks the maximum number of backtracks used when a path exhausts its credits.
  484.          * @param maxDepth the maximum depth to which the credit distribution takes place.
  485.          * @return true if a solution was found, false otherwise.
  486.          */
  487.         public boolean creditSearch(int credits, int backtracks, int maxDepth) {
  488.  
  489.                 SelectChoicePoint select = new SimpleSelect(vars
  490.                                 .toArray(new Var[1]), new SmallestDomain(),
  491.                                 new IndomainMin());
  492.  
  493.                 CreditCalculator credit = new CreditCalculator(credits, backtracks, maxDepth);
  494.  
  495.                 search = new DepthFirstSearch();
  496.  
  497.                 if (search.getConsistencyListener() == null)
  498.                         search.setConsistencyListener(credit);
  499.                 else
  500.                         search.getConsistencyListener().setChildrenListeners(credit);
  501.  
  502.                 search.setExitChildListener(credit);
  503.                 search.setTimeOutListener(credit);
  504.  
  505.                 boolean result = search.labeling(store, select);
  506.  
  507.                 store.print();
  508.  
  509.                 System.out.print(search.getNodes() + "\t");
  510.                 System.out.print(search.getDecisions() + "\t");
  511.                 System.out.print(search.getWrongDecisions() + "\t");
  512.                 System.out.print(search.getBacktracks() + "\t");
  513.                 System.out.print(search.getMaximumDepth() + "\t");
  514.  
  515.                 if (result)
  516.                         System.out.println(1);
  517.                 else
  518.                         System.out.println(0);
  519.  
  520.                 return result;
  521.         }
  522.  
  523.        
  524.     /**
  525.     *
  526.     * It uses MaxRegret variable ordering heuristic to search for a solution.
  527.     * @return true if there is a solution, false otherwise.
  528.     *
  529.     */
  530.    public boolean searchWithMaxRegret() {
  531.  
  532.        SelectChoicePoint select = new SimpleSelect (vars.toArray(new Var[0]),
  533.                                                         new MaxRegret(),
  534.                                                         new SmallestDomain(),
  535.                                                     new IndomainMiddle());
  536.        
  537.        search = new DepthFirstSearch();
  538.        search.getSolutionListener().searchAll(true);
  539.        search.getSolutionListener().recordSolutions(true);
  540.        
  541.        boolean result = search.labeling(store, select);
  542.        
  543.            return result;
  544.  
  545.    }
  546.        
  547.    /**
  548.     * It searches for solution using Limited Discrepancy Search.
  549.     * @param noDiscrepancy maximal number of discrepancies
  550.     * @return true if the solution was found, false otherwise.
  551.     */
  552.    public boolean searchLDS(int noDiscrepancy) {
  553.                
  554.                 search = new DepthFirstSearch();
  555.  
  556.                 boolean result = false;
  557.  
  558.                 SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]),
  559.                                 new SmallestDomain(), new IndomainMiddle());
  560.  
  561.                 LDS lds = new LDS(noDiscrepancy);
  562.  
  563.                 if (search.getExitChildListener() == null)
  564.                         search.setExitChildListener(lds);
  565.                 else
  566.                         search.getExitChildListener().setChildrenListeners(lds);
  567.  
  568.                 // Execution time measurement
  569.                 long begin = System.currentTimeMillis();
  570.  
  571.                 result = search.labeling(store, select);
  572.  
  573.                 // Execution time measurement
  574.                 long end = System.currentTimeMillis();
  575.  
  576.                 System.out.println("Number of milliseconds " + (end - begin));
  577.  
  578.                 return result;
  579.                
  580.         }
  581.    
  582.    
  583.  /**
  584.   * It searches for optimal solution using max regret variable ordering
  585.   * and indomain min for value ordering.
  586.  * @return true if there is a solution, false otherwise.
  587.  */
  588.    public boolean searchMaxRegretOptimal() {
  589.                
  590.                 long T1, T2, T;
  591.                 T1 = System.currentTimeMillis();
  592.  
  593.                 search = new DepthFirstSearch();
  594.  
  595.                 SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]), new MaxRegret(),
  596.                                 new IndomainMin());
  597.  
  598.                 boolean result = search.labeling(store, select, cost);
  599.  
  600.                 T2 = System.currentTimeMillis();
  601.                 T = T2 - T1;
  602.  
  603.                 if (result)
  604.                         System.out.println("Variables : " + vars);
  605.                 else
  606.                         System.out.println("Failed to find any solution");
  607.  
  608.                 System.out.println("\n\t*** Execution time = " + T + " ms");
  609.  
  610.                 return result;
  611.         }
  612.    
  613.    /**
  614.     * It searches using smallest domain variable ordering and
  615.     * indomain middle value ordering.
  616.     * @return true if there is a solution, false otherwise.
  617.     */
  618.    public boolean searchSmallestMiddle() {
  619.                
  620.                 long begin = System.currentTimeMillis();
  621.  
  622.                 boolean result = false;
  623.  
  624.                 search = new DepthFirstSearch();
  625.  
  626.                 SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]), new SmallestDomain(),
  627.                                 new IndomainMiddle());
  628.  
  629.                 result = search.labeling(store, select);
  630.  
  631.                 long end = System.currentTimeMillis();
  632.  
  633.  
  634.                 System.out.println("Number of milliseconds " + (end - begin));
  635.                
  636.                 return result;
  637.                
  638.         }
  639.  
  640.    
  641.    /**
  642.     * It searches using smallest domain variable ordering and
  643.     * indomain middle value ordering.
  644.     * @return true if there is a solution, false otherwise.
  645.     */
  646.    public boolean searchSmallestMedian() {
  647.                
  648.                 long begin = System.currentTimeMillis();
  649.  
  650.                 boolean result = false;
  651.  
  652.                 search = new DepthFirstSearch();
  653.  
  654.                 SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]), new SmallestDomain(),
  655.                                 new IndomainMedian());
  656.  
  657.                 result = search.labeling(store, select);
  658.  
  659.                 long end = System.currentTimeMillis();
  660.  
  661.  
  662.                 System.out.println("Number of milliseconds " + (end - begin));
  663.                
  664.                 return result;
  665.                
  666.         }
  667.    
  668.    
  669.         /**
  670.          * It searches using Smallest Min variable ordering heuristic and indomainMin value
  671.          * ordering heuristic.
  672.          *
  673.          * @return true if there is a solution, false otherwise.
  674.          */
  675.         public boolean searchSmallestMin() {
  676.  
  677.                 long begin = System.currentTimeMillis();
  678.                
  679.                 SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]), new SmallestMin(),
  680.                                 new IndomainMin());
  681.  
  682.                 search = new DepthFirstSearch();
  683.                
  684.                 boolean solution = search.labeling(store, select, cost);
  685.  
  686.                 long end = System.currentTimeMillis();
  687.  
  688.                 if (solution)
  689.                         store.print();
  690.                 else
  691.                         System.out.println("Failed to find any solution");
  692.  
  693.                 System.out.println("Number of milliseconds " + (end - begin));
  694.  
  695.                 return solution;
  696.        
  697.         }
  698.  
  699.        
  700.         /**
  701.          * It conducts master-slave search. Both of them use input order variable ordering.
  702.          *
  703.          * @param masterVars it specifies the search variables used in master search.
  704.          * @param slaveVars it specifies the search variables used in slave search.
  705.          *
  706.          * @return true if the solution exists, false otherwise.
  707.          */
  708.         public boolean searchMasterSlave(ArrayList<Var> masterVars,
  709.                                                                          ArrayList<Var> slaveVars) {
  710.  
  711.                 long T1 = System.currentTimeMillis();
  712.  
  713.                 boolean result = false;
  714.  
  715.                 Search labelSlave = new DepthFirstSearch();
  716.                 SelectChoicePoint selectSlave = new SimpleSelect(slaveVars.toArray(new Var[0]), null,
  717.                                 new IndomainMin());
  718.                 labelSlave.setSelectChoicePoint(selectSlave);
  719.  
  720.                 Search labelMaster = new DepthFirstSearch();
  721.                 SelectChoicePoint selectMaster = new SimpleSelect(masterVars.toArray(new Var[0]), null,
  722.                                 new IndomainMin());
  723.                
  724.                 labelMaster.addChildSearch(labelSlave);
  725.  
  726.                 search = labelMaster;
  727.                
  728.                 result = labelMaster.labeling(store, selectMaster);
  729.  
  730.                 if (result)
  731.                         System.out.println("Solution found");
  732.  
  733.                 if (result)
  734.                         store.print();
  735.  
  736.                 long T2 = System.currentTimeMillis();
  737.                
  738.                 System.out.println("\n\t*** Execution time = " + (T2 - T1) + " ms");
  739.  
  740.                 return result;
  741.         }
  742.  
  743.        
  744.         /**
  745.          * It returns the search used within an example.
  746.          * @return the search used within an example.
  747.          */
  748.         public Search getSearch() {
  749.                 return search;
  750.         }
  751.  
  752.         /**
  753.          * It specifies the constraint store used within an example.
  754.          * @return constraint store used within an example.
  755.          */
  756.         public Store getStore() {
  757.                 return store;
  758.         }
  759.  
  760.         /**
  761.          * It returns an array list of variables used to model the example.
  762.          * @return the array list of variables used to model the example.
  763.          */
  764.         public ArrayList<Var> getSearchVariables() {
  765.                 return vars;
  766.         }      
  767.                
  768.     /**
  769.      * It prints a matrix of variables. All variables must be grounded.
  770.      * @param matrix matrix containing the grounded variables.
  771.      * @param rows number of elements in the first dimension.
  772.      * @param cols number of elements in the second dimension.
  773.      */
  774.     public static void printMatrix(IntVar[][] matrix, int rows, int cols) {
  775.  
  776.         for(int i = 0; i < rows; i++) {
  777.             for(int j = 0; j < cols; j++) {
  778.                 System.out.print(matrix[i][j].value() + " ");
  779.             }
  780.             System.out.println();
  781.         }
  782.  
  783.     }
  784.  
  785. }
clone this paste RAW Paste Data