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

}