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