Solver.java

  1. /* Copyright 2015 Laurent COCAULT
  2.  * Licensed to Laurent COCAULT under one or more contributor license agreements.
  3.  * See the NOTICE file distributed with this work for additional information
  4.  * regarding copyright ownership. Laurent COCAULT licenses this file to You
  5.  * under the Apache License, Version 2.0 (the "License"); you may not use this
  6.  * file except in compliance with the License.  You may obtain a copy of the
  7.  * License at
  8.  *
  9.  *   http://www.apache.org/licenses/LICENSE-2.0
  10.  *
  11.  * Unless required by applicable law or agreed to in writing, software
  12.  * distributed under the License is distributed on an "AS IS" BASIS,
  13.  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14.  * See the License for the specific language governing permissions and
  15.  * limitations under the License.
  16.  */
  17. package org.csp.constraint.solver;

  18. import org.csp.constraint.model.Value;
  19. import org.csp.constraint.model.Variable;

  20. /**
  21.  * Basic class for solving managers.
  22.  */
  23. public abstract class Solver<T> {

  24.     /**
  25.      * Search result.
  26.      */
  27.     public enum SearchResult {
  28.         /** No solution is found. */
  29.         NO_SOLUTION,
  30.         /** A solution is found. */
  31.         SOLUTION_FOUND,
  32.         /** Depth of search tree is reached. */
  33.         DEPTH_LIMIT,
  34.         /** Maximum number of fails is reached. */
  35.         FAILS_LIMIT,
  36.         /** Maximum number of choice points is reached. */
  37.         CHOICE_POINTS_LIMIT
  38.     };

  39.     /**
  40.      * Problem to solve.
  41.      */
  42.     private Problem<T> problem_;

  43.     // Resolution limits

  44.     /**
  45.      * Maximum depth of the stack.
  46.      */
  47.     private int depthLimit_;

  48.     /**
  49.      * Maximum number of fails.
  50.      */
  51.     private int failsLimit_;

  52.     /**
  53.      * Maximum number of choice points.
  54.      */
  55.     private int choicePointsLimit_;

  56.     // Optimization

  57.     /**
  58.      * Optimization criterion.
  59.      */
  60.     private Variable<T> criterion_;

  61.     /**
  62.      * Optimization flag.
  63.      */
  64.     private boolean optimize_;

  65.     /**
  66.      * Constructor.
  67.      * @param problem
  68.      *            Problem to solve
  69.      */
  70.     public Solver(final Problem<T> problem) {

  71.         // Problem to solve
  72.         problem_ = problem;

  73.         // Default attributes (no optimization, no limit)
  74.         optimize_ = false;
  75.         depthLimit_ = Integer.MAX_VALUE;
  76.         failsLimit_ = Integer.MAX_VALUE;
  77.         choicePointsLimit_ = Integer.MAX_VALUE;
  78.     }

  79.     /**
  80.      * Solve the problem. Try to give one value to variables while satisfying
  81.      * all the constraints defined. This method uses the following methods :
  82.      * selectUnboundVariable, selectValue.
  83.      * @return The result of the search
  84.      */
  85.     public SearchResult branchAndBound() {

  86.         // Search result
  87.         SearchResult result = SearchResult.SOLUTION_FOUND;
  88.         // AC3 consistency
  89.         boolean ac3 = true;
  90.         // Recursive search result
  91.         SearchResult intermediateResult = SearchResult.SOLUTION_FOUND;
  92.         // Current variable and value
  93.         Variable<T> variable;

  94.         // This is a new choice point
  95.         problem_.increaseChoicePointsCounter();

  96.         if (problem_.getChoicePointsCounter() <= choicePointsLimit_) {

  97.             if (problem_.getStackDepth() < depthLimit_) {

  98.                 // Store the current domains
  99.                 problem_.store();

  100.                 // Select a couple of variable/value to try
  101.                 variable = branchAndBoundVariableSelection();
  102.                 if (variable != null) {
  103.                     final Value<T> value = branchAndBoundValueSelection(variable);

  104.                     // Test if the value can be in the solution
  105.                     variable.setValue(value);

  106.                     // Check the AC3 consistency
  107.                     ac3 = problem_.applyAC3(variable);

  108.                     if (ac3) {
  109.                         // Try to find a solution with this choice
  110.                         intermediateResult = branchAndBound();
  111.                     } else {
  112.                         // No solution
  113.                         intermediateResult = SearchResult.NO_SOLUTION;
  114.                     }

  115.                     // If no solution is found, try to remove the value
  116.                     if (intermediateResult == SearchResult.NO_SOLUTION) {

  117.                         // The problem is no more consistent. The counter of
  118.                         // fails is increased. Notice that the number of fails
  119.                         // is increased either when an assignment immediately
  120.                         // fails (AC3) or when the following of the search fails
  121.                         // (recursive call to branchAndBound).
  122.                         // Therefore it is not useful to count a fail when the
  123.                         // removal of the value (made below) also fails, since
  124.                         // the fail is counted at the branchAnd return.
  125.                         problem_.increaseFailsCounter();
  126.                         problem_.backtrack();

  127.                         if (problem_.getFailsCounter() <= failsLimit_) {

  128.                             // Test if the value can be out of the solution
  129.                             variable.removeValue(value);
  130.                             // Check the AC3 consistency
  131.                             ac3 = problem_.applyAC3(variable);
  132.                             if (!ac3) {
  133.                                 result = SearchResult.NO_SOLUTION;
  134.                             } else {

  135.                                 // The problem is not consistent, with or
  136.                                 // without the value. A choice made before must
  137.                                 // be cancelled. Notice that the number of fails
  138.                                 // is not increased immediately (see previous
  139.                                 // notice).
  140.                                 result = branchAndBound();

  141.                             }
  142.                         } else {
  143.                             // The total number of fails allowed is exceeded
  144.                             result = SearchResult.FAILS_LIMIT;
  145.                         }
  146.                     } else {
  147.                         // In the end, report the result to the upper level
  148.                         result = intermediateResult;
  149.                     }
  150.                 }
  151.             } else {
  152.                 // The stack depth
  153.                 result = SearchResult.DEPTH_LIMIT;
  154.             }
  155.         } else {
  156.             // The total number of choice points allowed is exceeded
  157.             result = SearchResult.CHOICE_POINTS_LIMIT;
  158.         }

  159.         return result;
  160.     }

  161.     /**
  162.      * Solve the problem (cf. classical branch and bound). Find a solution that
  163.      * minimizes the given criterion.
  164.      * @param criterion
  165.      *            Variable to minimize
  166.      * @return The result of the search
  167.      */
  168.     public SearchResult branchAndBound(final Variable<T> criterion) {

  169.         // Search result
  170.         SearchResult result = SearchResult.SOLUTION_FOUND;

  171.         // Prepare the search
  172.         criterion_ = criterion;
  173.         optimize_ = true;

  174.         // Search for the solution
  175.         result = branchAndBound();

  176.         // End the search
  177.         optimize_ = false;

  178.         return result;
  179.     }

  180.     /**
  181.      * Value selection method of the branch and bound algorithm.
  182.      * @param variable
  183.      *            Selected variable to bind
  184.      * @return Selected value to be used for binding
  185.      */
  186.     protected Value<T> branchAndBoundValueSelection(final Variable<T> variable) {
  187.         if (optimize_ && criterion_ == variable) {
  188.             // When the criterion must be bound, try the minimum value first
  189.             return criterion_.getFirstValue();
  190.         } else {
  191.             return selectValue(variable);
  192.         }
  193.     }

  194.     /**
  195.      * Variable selection method of the branch and bound algorithm.
  196.      * @return Selected variable, null if no variable has been selected
  197.      */
  198.     protected Variable<T> branchAndBoundVariableSelection() {

  199.         // Selected variable
  200.         Variable<T> variable = null;

  201.         if (optimize_ && !criterion_.isBound()) {
  202.             // First try to bind the criterion
  203.             variable = criterion_;
  204.         } else {
  205.             variable = selectVariableToBind();
  206.         }

  207.         return variable;
  208.     }

  209.     /**
  210.      * Get the problem solved.
  211.      * @return Problem being solved
  212.      */
  213.     protected Problem<T> getProblem() {
  214.         return problem_;
  215.     }

  216.     /**
  217.      * Select a value for a variable to bind.
  218.      * @param variable
  219.      *            Selected variable to bind
  220.      * @return Selected value to be used for binding
  221.      */
  222.     protected abstract Value<T> selectValue(Variable<T> variable);

  223.     /**
  224.      * Select a variable to bind.
  225.      * @return Selected variable, null if no variable is selected
  226.      */
  227.     protected abstract Variable<T> selectVariableToBind();

  228.     /**
  229.      * Set the maximum number of choice points. When the number of choice points
  230.      * is reached, the search is stopped without any solution. The search is
  231.      * stopped before the exceeding choice point is made.
  232.      * @param choicePointsLimit
  233.      *            Maximum number of choice points
  234.      */
  235.     public void setChoicePointsLimit(final int choicePointsLimit) {
  236.         choicePointsLimit_ = choicePointsLimit;
  237.     }

  238.     /**
  239.      * Set the maximum depth of the stack. When the stack is reached, the search
  240.      * is stopped without any solution. The search is stopped before the stack
  241.      * depth is exceeded.
  242.      * @param depthLimit
  243.      *            Maximum depth of the stack
  244.      */
  245.     public void setDepthLimit(final int depthLimit) {
  246.         depthLimit_ = depthLimit;
  247.     }

  248.     /**
  249.      * Set the maximum number of fails (A fail is a wrong variable assignation).
  250.      * When the number of fails is reached, the search is stopped without any
  251.      * solution. After the call, the state of the problem is the last valid one.
  252.      * @param failsLimit
  253.      *            Maximum number of fails
  254.      */
  255.     public void setFailsLimit(final int failsLimit) {
  256.         failsLimit_ = failsLimit;
  257.     }

  258. }