Solver.java
- /* Copyright 2015 Laurent COCAULT
- * Licensed to Laurent COCAULT under one or more contributor license agreements.
- * See the NOTICE file distributed with this work for additional information
- * regarding copyright ownership. Laurent COCAULT licenses this file to You
- * under the Apache License, Version 2.0 (the "License"); you may not use this
- * file except in compliance with the License. You may obtain a copy of the
- * License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
- package org.csp.constraint.solver;
- import org.csp.constraint.model.Value;
- import org.csp.constraint.model.Variable;
- /**
- * Basic class for solving managers.
- */
- public abstract class Solver<T> {
- /**
- * Search result.
- */
- public enum SearchResult {
- /** No solution is found. */
- NO_SOLUTION,
- /** A solution is found. */
- SOLUTION_FOUND,
- /** Depth of search tree is reached. */
- DEPTH_LIMIT,
- /** Maximum number of fails is reached. */
- FAILS_LIMIT,
- /** Maximum number of choice points is reached. */
- CHOICE_POINTS_LIMIT
- };
- /**
- * Problem to solve.
- */
- private Problem<T> problem_;
- // Resolution limits
- /**
- * Maximum depth of the stack.
- */
- private int depthLimit_;
- /**
- * Maximum number of fails.
- */
- private int failsLimit_;
- /**
- * Maximum number of choice points.
- */
- private int choicePointsLimit_;
- // Optimization
- /**
- * Optimization criterion.
- */
- private Variable<T> criterion_;
- /**
- * Optimization flag.
- */
- private boolean optimize_;
- /**
- * Constructor.
- * @param problem
- * Problem to solve
- */
- public Solver(final Problem<T> problem) {
- // Problem to solve
- problem_ = problem;
- // Default attributes (no optimization, no limit)
- optimize_ = false;
- depthLimit_ = Integer.MAX_VALUE;
- failsLimit_ = Integer.MAX_VALUE;
- choicePointsLimit_ = Integer.MAX_VALUE;
- }
- /**
- * Solve the problem. Try to give one value to variables while satisfying
- * all the constraints defined. This method uses the following methods :
- * selectUnboundVariable, selectValue.
- * @return The result of the search
- */
- public SearchResult branchAndBound() {
- // Search result
- SearchResult result = SearchResult.SOLUTION_FOUND;
- // AC3 consistency
- boolean ac3 = true;
- // Recursive search result
- SearchResult intermediateResult = SearchResult.SOLUTION_FOUND;
- // Current variable and value
- Variable<T> variable;
- // This is a new choice point
- problem_.increaseChoicePointsCounter();
- if (problem_.getChoicePointsCounter() <= choicePointsLimit_) {
- if (problem_.getStackDepth() < depthLimit_) {
- // Store the current domains
- problem_.store();
- // Select a couple of variable/value to try
- variable = branchAndBoundVariableSelection();
- if (variable != null) {
- final Value<T> value = branchAndBoundValueSelection(variable);
- // Test if the value can be in the solution
- variable.setValue(value);
- // Check the AC3 consistency
- ac3 = problem_.applyAC3(variable);
- if (ac3) {
- // Try to find a solution with this choice
- intermediateResult = branchAndBound();
- } else {
- // No solution
- intermediateResult = SearchResult.NO_SOLUTION;
- }
- // If no solution is found, try to remove the value
- if (intermediateResult == SearchResult.NO_SOLUTION) {
- // The problem is no more consistent. The counter of
- // fails is increased. Notice that the number of fails
- // is increased either when an assignment immediately
- // fails (AC3) or when the following of the search fails
- // (recursive call to branchAndBound).
- // Therefore it is not useful to count a fail when the
- // removal of the value (made below) also fails, since
- // the fail is counted at the branchAnd return.
- problem_.increaseFailsCounter();
- problem_.backtrack();
- if (problem_.getFailsCounter() <= failsLimit_) {
- // Test if the value can be out of the solution
- variable.removeValue(value);
- // Check the AC3 consistency
- ac3 = problem_.applyAC3(variable);
- if (!ac3) {
- result = SearchResult.NO_SOLUTION;
- } else {
- // The problem is not consistent, with or
- // without the value. A choice made before must
- // be cancelled. Notice that the number of fails
- // is not increased immediately (see previous
- // notice).
- result = branchAndBound();
- }
- } else {
- // The total number of fails allowed is exceeded
- result = SearchResult.FAILS_LIMIT;
- }
- } else {
- // In the end, report the result to the upper level
- result = intermediateResult;
- }
- }
- } else {
- // The stack depth
- result = SearchResult.DEPTH_LIMIT;
- }
- } else {
- // The total number of choice points allowed is exceeded
- result = SearchResult.CHOICE_POINTS_LIMIT;
- }
- return result;
- }
- /**
- * Solve the problem (cf. classical branch and bound). Find a solution that
- * minimizes the given criterion.
- * @param criterion
- * Variable to minimize
- * @return The result of the search
- */
- public SearchResult branchAndBound(final Variable<T> criterion) {
- // Search result
- SearchResult result = SearchResult.SOLUTION_FOUND;
- // Prepare the search
- criterion_ = criterion;
- optimize_ = true;
- // Search for the solution
- result = branchAndBound();
- // End the search
- optimize_ = false;
- return result;
- }
- /**
- * Value selection method of the branch and bound algorithm.
- * @param variable
- * Selected variable to bind
- * @return Selected value to be used for binding
- */
- protected Value<T> branchAndBoundValueSelection(final Variable<T> variable) {
- if (optimize_ && criterion_ == variable) {
- // When the criterion must be bound, try the minimum value first
- return criterion_.getFirstValue();
- } else {
- return selectValue(variable);
- }
- }
- /**
- * Variable selection method of the branch and bound algorithm.
- * @return Selected variable, null if no variable has been selected
- */
- protected Variable<T> branchAndBoundVariableSelection() {
- // Selected variable
- Variable<T> variable = null;
- if (optimize_ && !criterion_.isBound()) {
- // First try to bind the criterion
- variable = criterion_;
- } else {
- variable = selectVariableToBind();
- }
- return variable;
- }
- /**
- * Get the problem solved.
- * @return Problem being solved
- */
- protected Problem<T> getProblem() {
- return problem_;
- }
- /**
- * Select a value for a variable to bind.
- * @param variable
- * Selected variable to bind
- * @return Selected value to be used for binding
- */
- protected abstract Value<T> selectValue(Variable<T> variable);
- /**
- * Select a variable to bind.
- * @return Selected variable, null if no variable is selected
- */
- protected abstract Variable<T> selectVariableToBind();
- /**
- * Set the maximum number of choice points. When the number of choice points
- * is reached, the search is stopped without any solution. The search is
- * stopped before the exceeding choice point is made.
- * @param choicePointsLimit
- * Maximum number of choice points
- */
- public void setChoicePointsLimit(final int choicePointsLimit) {
- choicePointsLimit_ = choicePointsLimit;
- }
- /**
- * Set the maximum depth of the stack. When the stack is reached, the search
- * is stopped without any solution. The search is stopped before the stack
- * depth is exceeded.
- * @param depthLimit
- * Maximum depth of the stack
- */
- public void setDepthLimit(final int depthLimit) {
- depthLimit_ = depthLimit;
- }
- /**
- * Set the maximum number of fails (A fail is a wrong variable assignation).
- * When the number of fails is reached, the search is stopped without any
- * solution. After the call, the state of the problem is the last valid one.
- * @param failsLimit
- * Maximum number of fails
- */
- public void setFailsLimit(final int failsLimit) {
- failsLimit_ = failsLimit;
- }
- }