Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- * To change this template, choose Tools | Templates
- * and open the template in the editor.
- */
- package Transporte;
- /**
- *
- * @author oarboleda
- */
- /**
- * Examples.java
- * This file is part of JaCoP.
- *
- * JaCoP is a Java Constraint Programming solver.
- *
- * Copyright (C) 2000-2008 Krzysztof Kuchcinski and Radoslaw Szymanek
- *
- * This program is free software: you can redistribute it and/or modify
- * it under the terms of the GNU Affero General Public License as published by
- * the Free Software Foundation, either version 3 of the License, or
- * (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU Affero General Public License for more details.
- *
- * Notwithstanding any other provision of this License, the copyright
- * owners of this work supplement the terms of this License with terms
- * prohibiting misrepresentation of the origin of this work and requiring
- * that modified versions of this work be marked in reasonable ways as
- * different from the original version. This supplement of the license
- * terms is in accordance with Section 7 of GNU Affero General Public
- * License version 3.
- *
- * You should have received a copy of the GNU Affero General Public License
- * along with this program. If not, see <http://www.gnu.org/licenses/>.
- *
- */
- import JaCoP.constraints.Constraint;
- import JaCoP.core.IntVar;
- import JaCoP.core.Store;
- import JaCoP.core.Var;
- import JaCoP.search.CreditCalculator;
- import JaCoP.search.DepthFirstSearch;
- import JaCoP.search.IndomainMedian;
- import JaCoP.search.IndomainMiddle;
- import JaCoP.search.IndomainMin;
- import JaCoP.search.IndomainSimpleRandom;
- import JaCoP.search.LDS;
- import JaCoP.search.MaxRegret;
- import JaCoP.search.MostConstrainedStatic;
- import JaCoP.search.NoGoodsCollector;
- import JaCoP.search.Search;
- import JaCoP.search.SelectChoicePoint;
- import JaCoP.search.Shaving;
- import JaCoP.search.SimpleSelect;
- import JaCoP.search.SmallestDomain;
- import JaCoP.search.SmallestMin;
- import JaCoP.search.WeightedDegree;
- import java.util.*;
- /**
- * It is an abstract class to describe all necessary functions of any store.
- *
- * @author Radoslaw Szymanek and Krzysztof Kuchcinski
- * @version 3.0
- */
- public abstract class Example {
- /**
- * It contains all variables used within a specific example.
- */
- public ArrayList<Var> vars;
- /**
- * It specifies the cost function, null if no cost function is used.
- */
- public IntVar cost;
- /**
- * It specifies the constraint store responsible for holding information
- * about constraints and variables.
- */
- public Store store;
- /**
- * It specifies the search procedure used by a given example.
- */
- public Search search;
- /**
- * It specifies a standard way of modeling the problem.
- */
- public abstract void model();
- /**
- * It specifies simple search method based on input order and lexigraphical
- * ordering of values.
- *
- * @return true if there is a solution, false otherwise.
- */
- public boolean search() {
- long T1, T2;
- T1 = System.currentTimeMillis();
- SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]), null,
- new IndomainMin());
- search = new DepthFirstSearch();
- boolean result = search.labeling(store, select);
- if (result)
- store.print();
- T2 = System.currentTimeMillis();
- System.out.println("\n\t*** Execution time = " + (T2 - T1) + " ms");
- System.out.println();
- System.out.print(search.getNodes() + "\t");
- System.out.print(search.getDecisions() + "\t");
- System.out.print(search.getWrongDecisions() + "\t");
- System.out.print(search.getBacktracks() + "\t");
- System.out.print(search.getMaximumDepth() + "\t");
- return result;
- }
- /**
- * It specifies simple search method based on input order and lexigraphical
- * ordering of values. It optimizes the solution by minimizing the cost function.
- *
- * @return true if there is a solution, false otherwise.
- */
- public boolean searchOptimal() {
- long T1, T2;
- T1 = System.currentTimeMillis();
- SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]), null,
- new IndomainMin());
- search = new DepthFirstSearch();
- boolean result = search.labeling(store, select, cost);
- if (result){
- store.print();
- }
- T2 = System.currentTimeMillis();
- System.out.println("\n\t*** Execution time = " + (T2 - T1) + " ms");
- return result;
- }
- /**
- * It searches for all solutions with the optimal value.
- * @return true if any optimal solution has been found.
- */
- public boolean searchAllOptimal() {
- long T1, T2, T;
- T1 = System.currentTimeMillis();
- SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]), null,
- new IndomainMin());
- search = new DepthFirstSearch();
- search.getSolutionListener().searchAll(true);
- search.getSolutionListener().recordSolutions(true);
- boolean result = search.labeling(store, select, cost);
- T2 = System.currentTimeMillis();
- T = T2 - T1;
- System.out.println("\n\t*** Execution time = " + T + " ms");
- return result;
- }
- /**
- * It specifies simple search method based on smallest domain variable order
- * and lexigraphical ordering of values.
- * @param optimal it specifies if the search the optimal solution takes place.
- *
- * @return true if there is a solution, false otherwise.
- */
- public boolean searchSmallestDomain(boolean optimal) {
- long T1, T2;
- T1 = System.currentTimeMillis();
- SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]), new SmallestDomain(),
- new IndomainMin());
- search = new DepthFirstSearch();
- boolean result = false;
- if (optimal) {
- search.labeling(store, select, cost);
- }
- else{
- search.labeling(store, select);
- }
- System.out.println();
- System.out.print(search.getNodes() + "\t");
- System.out.print(search.getDecisions() + "\t");
- System.out.print(search.getWrongDecisions() + "\t");
- System.out.print(search.getBacktracks() + "\t");
- System.out.print(search.getMaximumDepth() + "\t");
- if (result)
- store.print();
- T2 = System.currentTimeMillis();
- System.out.println("\n\t*** Execution time = " + (T2 - T1) + " ms");
- return result;
- }
- /**
- * It specifies simple search method based on weighted degree variable order
- * and lexigraphical ordering of values. This search method is rather general
- * any problem good fit. It can be a good first trial to see if the model is
- * correct.
- *
- * @return true if there is a solution, false otherwise.
- */
- public boolean searchWeightedDegree() {
- long T1, T2;
- T1 = System.currentTimeMillis();
- SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]),
- new WeightedDegree(),
- new SmallestDomain(),
- new IndomainMin());
- search = new DepthFirstSearch();
- boolean result = search.labeling(store, select);
- System.out.println();
- System.out.print(search.getNodes() + "\t");
- System.out.print(search.getDecisions() + "\t");
- System.out.print(search.getWrongDecisions() + "\t");
- System.out.print(search.getBacktracks() + "\t");
- System.out.print(search.getMaximumDepth() + "\t");
- if (result)
- store.print();
- T2 = System.currentTimeMillis();
- System.out.println("\n\t*** Execution time = " + (T2 - T1) + " ms");
- return result;
- }
- /**
- * It specifies simple search method based variable order which
- * takes into account the number of constraints attached to a variable
- * and lexigraphical ordering of values.
- *
- * @return true if there is a solution, false otherwise.
- */
- public boolean searchMostConstrainedStatic() {
- search = new DepthFirstSearch();
- SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]),
- new MostConstrainedStatic(), new IndomainMin());
- boolean result = search.labeling(store, select);
- System.out.println();
- System.out.print(search.getNodes() + "\t");
- System.out.print(search.getDecisions() + "\t");
- System.out.print(search.getWrongDecisions() + "\t");
- System.out.print(search.getBacktracks() + "\t");
- System.out.print(search.getMaximumDepth() + "\t");
- if (!result)
- System.out.println("**** No Solution ****");
- return result;
- }
- /**
- * It specifies simple search method based on most constrained static and lexigraphical
- * ordering of values. It searches for all solutions.
- *
- * @return true if there is a solution, false otherwise.
- */
- public boolean searchAllAtOnce() {
- long T1, T2;
- T1 = System.currentTimeMillis();
- SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]),
- new MostConstrainedStatic(), new IndomainMin());
- search = new DepthFirstSearch();
- search.getSolutionListener().searchAll(true);
- search.getSolutionListener().recordSolutions(true);
- search.setAssignSolution(true);
- boolean result = search.labeling(store, select);
- T2 = System.currentTimeMillis();
- if (result) {
- System.out.println("Number of solutions " + search.getSolutionListener().solutionsNo());
- search.printAllSolutions();
- }
- else
- System.out.println("Failed to find any solution");
- System.out.println("\n\t*** Execution time = " + (T2 - T1) + " ms");
- return result;
- }
- /**
- * It searches using an input order search with indomain based on middle value.
- * @return true if there is a solution, false otherwise.
- */
- public boolean searchMiddle() {
- long begin = System.currentTimeMillis();
- search = new DepthFirstSearch();
- SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]),
- null, new IndomainMiddle());
- boolean result = search.labeling(store, select);
- long end = System.currentTimeMillis();
- System.out.println("Number of milliseconds " + (end - begin));
- return result;
- }
- /**
- * It searches with shaving which is guided by supplied constraints.
- * @param guidingShaving the array of constraints proposing shaving candidates.
- * @param printInfo it specifies if that function should print any info.
- * @return true if the solution was found, false otherwise.
- */
- public boolean shavingSearch(ArrayList<Constraint> guidingShaving, boolean printInfo) {
- Shaving shaving = new Shaving();
- shaving.setStore(store);
- shaving.quickShave = true;
- for (Constraint c : guidingShaving)
- shaving.addShavingConstraint(c);
- long begin = System.currentTimeMillis();
- search = new DepthFirstSearch();
- search.setPrintInfo(printInfo);
- SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]), null, new IndomainMiddle());
- search.setConsistencyListener(shaving);
- search.setExitChildListener(shaving);
- boolean result = search.labeling(store, select);
- long end = System.currentTimeMillis();
- if (printInfo) {
- System.out.println("Number of milliseconds " + (end - begin));
- System.out.println("Ratio " + (shaving.successes * 100 / (shaving.successes + shaving.failures)));
- if (result)
- store.print();
- }
- return result;
- }
- /**
- * It conducts the search with restarts from which the no-goods are derived.
- * Every search contributes with new no-goods which are kept so eventually
- * the search is complete (although can be very expensive to maintain explicitly
- * all no-goods found during search).
- * @return true if there is a solution, false otherwise.
- */
- public boolean searchWithRestarts() {
- // Input Order tie breaking
- boolean result = false;
- boolean timeout = true;
- int nodes = 0;
- int decisions = 0;
- int backtracks = 0;
- int wrongDecisions = 0;
- search = new DepthFirstSearch();
- NoGoodsCollector collector = new NoGoodsCollector();
- search.setExitChildListener(collector);
- search.setTimeOutListener(collector);
- search.setExitListener(collector);
- SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]), new SmallestDomain(),
- new IndomainSimpleRandom());
- while (timeout) {
- // search.setPrintInfo(false);
- search.setNodesOut(1000);
- result = search.labeling(store, select);
- timeout &= collector.timeOut;
- nodes += search.getNodes();
- decisions += search.getDecisions();
- wrongDecisions += search.getWrongDecisions();
- backtracks += search.getBacktracks();
- search = new DepthFirstSearch();
- collector = new NoGoodsCollector();
- search.setExitChildListener(collector);
- search.setTimeOutListener(collector);
- search.setExitListener(collector);
- }
- // System.out.println(search.noGoodsVariables);
- // System.out.println(search.noGoodsValues);
- // System.out.println(store.watchedConstraints);
- // store.toXCSP2_0();
- // store.finalizeXCSP2_0(-1, "./", "restarts.xml");
- System.out.println();
- System.out.print(nodes + "\t");
- System.out.print(decisions + "\t");
- System.out.print(wrongDecisions + "\t");
- System.out.print(backtracks + "\t");
- if (result)
- System.out.println(1);
- else
- System.out.println(0);
- return result;
- }
- /**
- * It uses credit search to solve a problem.
- * @param credits the number of credits available.
- * @param backtracks the maximum number of backtracks used when a path exhausts its credits.
- * @param maxDepth the maximum depth to which the credit distribution takes place.
- * @return true if a solution was found, false otherwise.
- */
- public boolean creditSearch(int credits, int backtracks, int maxDepth) {
- SelectChoicePoint select = new SimpleSelect(vars
- .toArray(new Var[1]), new SmallestDomain(),
- new IndomainMin());
- CreditCalculator credit = new CreditCalculator(credits, backtracks, maxDepth);
- search = new DepthFirstSearch();
- if (search.getConsistencyListener() == null)
- search.setConsistencyListener(credit);
- else
- search.getConsistencyListener().setChildrenListeners(credit);
- search.setExitChildListener(credit);
- search.setTimeOutListener(credit);
- boolean result = search.labeling(store, select);
- store.print();
- System.out.print(search.getNodes() + "\t");
- System.out.print(search.getDecisions() + "\t");
- System.out.print(search.getWrongDecisions() + "\t");
- System.out.print(search.getBacktracks() + "\t");
- System.out.print(search.getMaximumDepth() + "\t");
- if (result)
- System.out.println(1);
- else
- System.out.println(0);
- return result;
- }
- /**
- *
- * It uses MaxRegret variable ordering heuristic to search for a solution.
- * @return true if there is a solution, false otherwise.
- *
- */
- public boolean searchWithMaxRegret() {
- SelectChoicePoint select = new SimpleSelect (vars.toArray(new Var[0]),
- new MaxRegret(),
- new SmallestDomain(),
- new IndomainMiddle());
- search = new DepthFirstSearch();
- search.getSolutionListener().searchAll(true);
- search.getSolutionListener().recordSolutions(true);
- boolean result = search.labeling(store, select);
- return result;
- }
- /**
- * It searches for solution using Limited Discrepancy Search.
- * @param noDiscrepancy maximal number of discrepancies
- * @return true if the solution was found, false otherwise.
- */
- public boolean searchLDS(int noDiscrepancy) {
- search = new DepthFirstSearch();
- boolean result = false;
- SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]),
- new SmallestDomain(), new IndomainMiddle());
- LDS lds = new LDS(noDiscrepancy);
- if (search.getExitChildListener() == null)
- search.setExitChildListener(lds);
- else
- search.getExitChildListener().setChildrenListeners(lds);
- // Execution time measurement
- long begin = System.currentTimeMillis();
- result = search.labeling(store, select);
- // Execution time measurement
- long end = System.currentTimeMillis();
- System.out.println("Number of milliseconds " + (end - begin));
- return result;
- }
- /**
- * It searches for optimal solution using max regret variable ordering
- * and indomain min for value ordering.
- * @return true if there is a solution, false otherwise.
- */
- public boolean searchMaxRegretOptimal() {
- long T1, T2, T;
- T1 = System.currentTimeMillis();
- search = new DepthFirstSearch();
- SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]), new MaxRegret(),
- new IndomainMin());
- boolean result = search.labeling(store, select, cost);
- T2 = System.currentTimeMillis();
- T = T2 - T1;
- if (result)
- System.out.println("Variables : " + vars);
- else
- System.out.println("Failed to find any solution");
- System.out.println("\n\t*** Execution time = " + T + " ms");
- return result;
- }
- /**
- * It searches using smallest domain variable ordering and
- * indomain middle value ordering.
- * @return true if there is a solution, false otherwise.
- */
- public boolean searchSmallestMiddle() {
- long begin = System.currentTimeMillis();
- boolean result = false;
- search = new DepthFirstSearch();
- SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]), new SmallestDomain(),
- new IndomainMiddle());
- result = search.labeling(store, select);
- long end = System.currentTimeMillis();
- System.out.println("Number of milliseconds " + (end - begin));
- return result;
- }
- /**
- * It searches using smallest domain variable ordering and
- * indomain middle value ordering.
- * @return true if there is a solution, false otherwise.
- */
- public boolean searchSmallestMedian() {
- long begin = System.currentTimeMillis();
- boolean result = false;
- search = new DepthFirstSearch();
- SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]), new SmallestDomain(),
- new IndomainMedian());
- result = search.labeling(store, select);
- long end = System.currentTimeMillis();
- System.out.println("Number of milliseconds " + (end - begin));
- return result;
- }
- /**
- * It searches using Smallest Min variable ordering heuristic and indomainMin value
- * ordering heuristic.
- *
- * @return true if there is a solution, false otherwise.
- */
- public boolean searchSmallestMin() {
- long begin = System.currentTimeMillis();
- SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]), new SmallestMin(),
- new IndomainMin());
- search = new DepthFirstSearch();
- boolean solution = search.labeling(store, select, cost);
- long end = System.currentTimeMillis();
- if (solution)
- store.print();
- else
- System.out.println("Failed to find any solution");
- System.out.println("Number of milliseconds " + (end - begin));
- return solution;
- }
- /**
- * It conducts master-slave search. Both of them use input order variable ordering.
- *
- * @param masterVars it specifies the search variables used in master search.
- * @param slaveVars it specifies the search variables used in slave search.
- *
- * @return true if the solution exists, false otherwise.
- */
- public boolean searchMasterSlave(ArrayList<Var> masterVars,
- ArrayList<Var> slaveVars) {
- long T1 = System.currentTimeMillis();
- boolean result = false;
- Search labelSlave = new DepthFirstSearch();
- SelectChoicePoint selectSlave = new SimpleSelect(slaveVars.toArray(new Var[0]), null,
- new IndomainMin());
- labelSlave.setSelectChoicePoint(selectSlave);
- Search labelMaster = new DepthFirstSearch();
- SelectChoicePoint selectMaster = new SimpleSelect(masterVars.toArray(new Var[0]), null,
- new IndomainMin());
- labelMaster.addChildSearch(labelSlave);
- search = labelMaster;
- result = labelMaster.labeling(store, selectMaster);
- if (result)
- System.out.println("Solution found");
- if (result)
- store.print();
- long T2 = System.currentTimeMillis();
- System.out.println("\n\t*** Execution time = " + (T2 - T1) + " ms");
- return result;
- }
- /**
- * It returns the search used within an example.
- * @return the search used within an example.
- */
- public Search getSearch() {
- return search;
- }
- /**
- * It specifies the constraint store used within an example.
- * @return constraint store used within an example.
- */
- public Store getStore() {
- return store;
- }
- /**
- * It returns an array list of variables used to model the example.
- * @return the array list of variables used to model the example.
- */
- public ArrayList<Var> getSearchVariables() {
- return vars;
- }
- /**
- * It prints a matrix of variables. All variables must be grounded.
- * @param matrix matrix containing the grounded variables.
- * @param rows number of elements in the first dimension.
- * @param cols number of elements in the second dimension.
- */
- public static void printMatrix(IntVar[][] matrix, int rows, int cols) {
- for(int i = 0; i < rows; i++) {
- for(int j = 0; j < cols; j++) {
- System.out.print(matrix[i][j].value() + " ");
- }
- System.out.println();
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement