2.3 Solver

As noted before, solver is kind of a planner. It decides when to use which algorithm, for how long to use it, on which problems. Furthermore it collects results and renders then. Solver is defined by Solver interface. Most methods has default implementations in BaseSolver so there is actually only one left to implement - Solver#run().

In this method, the solver cycle, algorithm(s) are applied to problem(s). The simplest thing to do is to create Solver that takes one algorithm and one problem as arguments:

package basicusage.solver;

import cz.cvut.felk.cig.jcop.algorithm.Algorithm;
import cz.cvut.felk.cig.jcop.problem.Problem;
import cz.cvut.felk.cig.jcop.solver.BaseSolver;
import cz.cvut.felk.cig.jcop.solver.Solver;

public class PrimitiveSolver extends BaseSolver implements Solver {
    /**
     * Problem to be solved
     */
    protected Problem problem;
    /**
     * Algorithm to be used
     */
    protected Algorithm algorithm;

    public PrimitiveSolver(Algorithm algorithm, Problem problem) {
        this.algorithm = algorithm;
        this.problem = problem;
    }
}

Right now we got an error - for not implementing the Solver interface. Lets do this. First thing we are obliged to do in Solver#run() is to call Algorithm#init(ObjectiveProblem) to initialize (and restart) algorithm on a problem. Don't mind why it takes ObjectiveProblem as argument or what exactly it does right know, all will be explained later. Just consider algorithm to be prepared. Now we need to make the algorithm "work" on a problem. This is called making an optimize step and is invoked by Algorithm#optimize() call. So, let us make solver which will make 10 optimize steps and then ends:

package basicusage.solver;

import /** ... */
import cz.cvut.felk.cig.jcop.problem.BaseObjectiveProblem;

public class PrimitiveSolver extends BaseSolver implements Solver {
    /** ... */
    public void run() {
        this.algorithm.init(new BaseObjectiveProblem(this.problem));

        for (int i = 0; i < 10; i++) this.algorithm.optimize();
    }
}

Well, that's it. If you want to run this solver, just create an instance of it and call its Solver#run() method. Since we do not know much about algorithms and problems, take the following code and run the main method. You will not see any results yet - these will be explained in next chapter.

package basicusage.solver;

import cz.cvut.felk.cig.jcop.algorithm.Algorithm;
import cz.cvut.felk.cig.jcop.algorithm.graphsearch.bfs.BreadthFirstSearch;
import cz.cvut.felk.cig.jcop.problem.Problem;
import cz.cvut.felk.cig.jcop.problem.knapsack.Knapsack;
import cz.cvut.felk.cig.jcop.solver.Solver;

public class DemoPrimitiveSolver {
    public static void main(String[] args) {
        // create problem & algorithm
        Problem problem = new Knapsack("9000 4 100 18 114 42 136 88 192 3 223");
        Algorithm algorithm = new BreadthFirstSearch();

        // create solver
        Solver solver = new PrimitiveSolver(algorithm, problem);

        // run!
        solver.run();
    }
}

If it finishes without exception, you've made your first own solver. If there is an error, take a look back through this tutorial and try to find our what you have done differently. Both classes could be downloaded here (zip, tgz, 7z).

Bundled Solvers

There are several Solvers bundled with JCOP and they are preferred to use instead of creating your own. SimpleSolver is used if you want to run a single algorithm on a single problem, usually in development stage. AlgorithmCompareSolver is used to benchmark several algorithms against one problem. For a full list see Appendix A.

StopConditions

An important part of Solver are StopConditions. We have not covered them in our solver to make things easy to understand. In real use however, we need to control when should solver iterations stop. To accomplish this, JCOP provides you with StopCondition concept.

A solver can have several stop conditions registered to it and whenever at least one is met, it ends (only current solver iteration). Stop conditions are added to solver by Solver#addStopCondition(StopCondition). Conditions works as listeners (and are automatically registered as such) for solver which then sends them messages about its progress. After every optimization step it evaluates if any condition was met and possibly ends.

There are several stop conditions bundled with JCOP. For the full list and description, see Appendix D. The usage is quite simple:

package basicusage.solver;

import cz.cvut.felk.cig.jcop.algorithm.Algorithm;
import cz.cvut.felk.cig.jcop.algorithm.graphsearch.bfs.BreadthFirstSearch;
import cz.cvut.felk.cig.jcop.problem.Problem;
import cz.cvut.felk.cig.jcop.problem.knapsack.Knapsack;
import cz.cvut.felk.cig.jcop.solver.SimpleSolver;
import cz.cvut.felk.cig.jcop.solver.Solver;
import cz.cvut.felk.cig.jcop.solver.condition.IterationCondition;
import cz.cvut.felk.cig.jcop.solver.condition.TimeoutCondition;

public class DemoCondition {
    public static void main(String[] args) {
        // create problem & algorithm
        Problem problem = new Knapsack("9000 4 100 18 114 42 136 88 192 3 223");
        Algorithm algorithm = new BreadthFirstSearch();

        // create solver
        Solver solver = new SimpleSolver(algorithm, problem);

        // max 10 optimizations
        solver.addStopCondition(new IterationCondition(10));
        // and max 10ms of solver iteration run
        solver.addStopCondition(new TimeoutCondition(10));

        // run!
        solver.run();
    }
}

Now the solver (note that we use SimpleSolver now) will attempt maximum of 10 optimization and will run no more than 10ms (of CPU time, see util for details).