C. Problems

List of all problems in JCOP

In table 1 is a list of all problems bundled with JCOP, along with brief description and provided interfaces.

Name Description Provided interfaces
Bucket Buckets of given capacity and starting contents are required each to have given contents in every bucket by using operations fill, spill and pour one bucket into another. Problem
DestinationProblem
StartingConfigurationProblem
JobShop Plan n different jobs, each given duration, on m (m < n) identical machines, each able to run one job at a time. Find assignment of jobs to machines with minimal total duration. Problem
StartingConfigurationProblem
RandomConfigurationProblem
GlobalSearchProblem
Knapsack Add items with given capacity and price to a knapsack, which can hold only given weight. Maximize total price of items in knapsack. Problem
StartingConfigurationProblem
RandomConfigurationProblem
GlobalSearchProblem
SAT Assign boolean values to variables (each given weight) so that given formula evaluates to true. Minimize weight of variables assigned with true. Problem
StartingConfigurationProblem
RandomConfigurationProblem
GlobalSearchProblem
TSP Find in which order to visit a list of cities (each given distance to all others) such that every city is visited exactly once and total trip length is minimal. Problem
StartingConfigurationProblem

Table 1: List of all problems in JCOP.

Bucket

Bucket starts with a set of n buckets, each with given capacity, starting and destination contents. The goal is to have each bucket filled with destination contents. Only allowed operations are to fill bucket (to its capacity), spill bucket empty or pour one bucket into another (if there is not enough space in destination bucket, rest is left in source one).

Bucket is initialized with arrays of integers as shown below.

Bucket bucket = new Bucket(new int[]{14, 10, 6, 2, 8}, new int[]{0, 0, 1, 0, 0}, new int[]{12, 6, 4, 1, 8});

This creates 5 buckets problem, with capacities of 14, 10, 6, 2, 8, starting contents 0, 0, 1, 0, 0 and destination contents of 12, 6, 4, 1, 8. Best solution with such parameters is (Pour 2 into 0, Fill 1, Pour 1 into 2, Pour 2 into 4, Fill 2, Pour 2 into 3, Pour 3 into 1, Pour 0 into 3, Fill 0, Pour 0 into 4), where numbers are indexes of buckets (indexed from 0).

Three operations are FillOperation (fills bucket to the brim), SpillOperation (empties a bucket) and PourOperation (pours contents of one bucket into another). Default fitness BucketFitness ranges from 0 to n, the number equals how many buckets have its destination contents. Configuration has n variables, each representing capacity of one bucket.

JobShop

JobShop is problem where you have given n jobs, each having its duration, and m identical machines. The goal is to assign every job a machine on which to run it with minimal total duration.

JobShop is initialized with a list of integers (jobs duration) and number of machines as shown below.

List<Integer> jobs = new ArrayList<Integer>(5);
jobs.add(5);
jobs.add(4);
jobs.add(6);
jobs.add(2);
jobs.add(2);
JobShop jobShop = new JobShop(jobs, 3);

This creates a JobShop with 5 jobs with durations 5, 4, 6, 2 and 2, and 3 machines. Best solutions to have jobs 1 and 4 on machine 0, jobs 0 and 3 on machine 1 and job 2 on machine 2. Total time is 7.

Only one operation is MoveOperation which moves job from one machine to another. Default fitness JobShopFitness is calculated such that if all jobs are on single machine, fitness is 0. For every saved unit of time fitness is increased by 1. Configuration has n variables, each representing number of machine on which job runs.

Knapsack

In Knapsack there are n items with given price and weight (represented as KnapsackItem) and capacity of knapsack. We need to put items to knapsack so that total weight of items is no more than knapsack's capacity and total price is maximal.

Knapsack is initialized either from file or a string. Both takes the same format, in case of file is used either first line or line with given id. First number in line is id, second number of items, third is knapsack capacity. Then follows pairs weight-price for every item. Below is shown example when loading form string.

Knapsack knapsack = new Knapsack("9000 4 100 18 114 42 136 88 192 3 223");

This creates a Knapsack with 4 items (weighting 18, 42, 88 and 3, pricing 114, 136, 192, 223), id 9000 and knapsack capacity 100. Best solution is to have items 0, 1 and 3 in knapsack (total weight 63, total price 473).

Two operations are AddOperation (adds item to knapsack) and RemoveOperation (removes item from knapsack). Default fitness is KnapsackFitness and works such that overfilled knapsack has negative fitness (higher total price means higher fitness) and positive number if total weight is not greater than knapsack's capacity (in that case fitness is total price). Configuration has one variable for every item, 0 means item is not present, 1 items is present.

SAT

SAT has n variables (each having a weight) and one formula (product of sums). The goal is to assign each variable either true or false so that formula evaluates to true and total weight of all true variables is minimal.

SAT is initialized from file (for format see SAT#SAT(File)). It creates n variables and m clauses. In every clause, there are any number (but usually 3 as for 3-SAT problem) of variables, which can be negated. Below is example how to load from file:

SAT sat = new SAT(new File("data/sat/easy.cnf"));

This creates a SAT from file data/sat/easy.cnf.

Two operations are SetTrueOperation (sets variable to true) and SetFalseOperation (sets variable to false). Default fitness is SATFitness and is calculated that if formula is satisfied, fitness is positive number (higher weight means lower fitness). If formula is not satisfied, fitness is negative number of non-satisfied clauses. Configuration has n variables, each either 0 (variable is false) or 1 (variable is true).

TSP

TSP (traveling salesman problem) has n cities and for every city distance to every other. Goal is to find a tour in which to visit each city so that every one is visited exactly once and total distance is minimal (also known as Hamiltonian cycle).

TSP is initialized from 2D array of Integer - square matrix of distances (allowing asymmetric TSP). For every row in the matrix, one City is created with map of distances to other cities. Below is example how to load TSP from array:

TSP tsp = new TSP(new Integer[][]{
        { 0, 20, 42, 35},
        {20,  0, 30, 34},
        {42, 30,  0, 53},
        {35, 34, 53,  0},
});

This creates TSP with 4 cities. Distance from first to second is 20, from first to third is 42 etc. Best solution is to visit cities in order city 2, city 1, city 0 and city 3. Total distance is 97.

One operations is SwitchCityOperation which switches two cities in a tour (eg. when city A was to be visited at k-th position and city B at j-th position, after switch is city A visited at j-th position and B at i-th). Default fitness is TSPFitness, value is either negative distance (if configuration is invalid tour) or positive number - shorter tour means higher fitness. Configuration has n variables, indexes are position in tour and values are indexes of cities. For example configuration [2,3,1,0] means that first is visited city 2, then city 3, then city 1 and last is city 0.