1.1 JCOP

What is JCOP

JCOP stands for Java Combinatorial Optimization Platform. Its development began in 2009 as a part of Ondřej Skalička's master's thesis. It was created with two main goals in mind. First is to make a platform which allows to create combinatorial algorithms and problems in such a way that it is possible to apply (almost) every algorithm on every problem, without any modifications. This way it should be possible to benchmark several settings of the same algorithm or even different algorithms on one problem and tell which performed better. It is not intended to be able to solve problems extremely fast, just to be able to tell which one is better among the others to be preferred and used on a problem.

The second goal of JCOP is that it is both easy to use and contains several algorithms and problems bundled with it. This is because of it will be used as part of teaching process on Faculty of Electrical Engineering on Czech Technical University in Prague by students to make their end-term projects, in which several algorithms of increasing complexity will be implemented.

JCOP comes bundled with several problems and algorithms of its own (see appendixes for description) so you can begin playing with it right away. After you have seen how it works, you can add your own algorithms and problems to it and see how better (or worse) do they fare against built-in ones.

Where to get it

JCOP have a compiled beta distribution available for download from download page. Source files can be accessed via SVN server.

How does it work

When it comes to start solving problems using in-built or your own algorithms, benchmarking different algorithms or just testing how algorithm settings affects solutions, JCOP stands on four main pillars - Solver, Problem, Algorithm and Result. Solver takes Algorithm(s) and Problem(s) and begins to solve the Problems (either sequentially one at a time or possibly some switching etc.). During this time Result begins to collect important data. When Solver is finished, Result displays collected data to user in varying formats. To be able to have these four main parts to interact together, JCOP uses lots of interfaces through which components interact with each other.

Solver

Solver is responsible for proper initializing of algorithm and problem, applying of algorithm on the problem, creating results and terminating whole process. This process is called a Solver Iteration and many solvers repeat it several times (to use several algorithms on a single problem for example). The most basic implementation - SimpleSolver - just takes single algorithm and applies it to a single problem. Other solvers tests multiple algorithms on same problem or benchmarks how good does one algorithm solve different problems. Furthermore Solver package contains StopConditions, a set of rules that determine when to stop, and messages passed to different listeners.

Result

Result takes care of collecting results from solver (both final result and collecting runtime data) and presenting collected information to user. This includes printing results to xml/html/txt or console, making plots or creating summaries for benchmarks. Result itself is registered to a solver which is responsible for informing it about anything of importance.

Problem

Problem contains all information about one combinatorial problem. This ranges from different forms of initialization (loading from file, arrays etc.), through implementing required interfaces (providing fitness, operations), to adding the optional interfaces (support for global search algorithms, random configurations, destination problems and more).

Problems are a bit more difficult to understand than other part of the platform. This is because Problem must be able to cover lots of different real world problems and be able to provide all necessary information about it. JCOP works with the fact that most combinatorial problems can be defined with following:

  • Every configuration (point in search space) has final number of variables (also called dimension), each having final number of available values.
  • For every configuration, there is final set of operations that can be applied on that configuration.
  • Every configuration can have its fitness calculated.

This list is the minimal requirements for a problem to be able to exist in JCOP. There are other additional information that problem can provide and algorithms may require to run. These are optional, but the more information a problem provides the more algorithms could be used to solve it.

Algorithm

Algorithm on the other hand has one simple interface, two main parts of which are initialization of algorithm on a given problem and performing one optimization step. Also, algorithms may be able to dynamically adapt to a problem if they recognize some of its features (for example algorithm can choose to use own fitness calculation for problems derived from SAT).

Util

Util contains some useful utilities which are used in JCOP. Such may include utilities for measuring precise time, random with special properties and commonly used comparators.