Your Solution object represents a solution to your problem. It is not necessarily a good solution - just a solution.

OpenTS imposes no restriction on how you define your solution or what data structures you use because OpenTS never manipulates your Solution objects directly. It relies on your Move object to modify the Solution, your ObjectiveFunction object to evaluate the Solution, and your Solution itself to clone it.

You may find it useful to subclass (extend) the SolutionAdapter class since it automatically handles the three required methods getObjectiveValue(), setObjectiveValue(...), and clone().

SolutionAdapter properly clones the objective value array, but it is essential that you properly clone your data structures as well. For an excellent discussion of cloning techniques, see this Java Developer Connection Tech Tip.

It is a common mistake to copy references to data instead of copying the data itself. The easiest place to make this mistake is with arrays. Suppose you have an int array called sack that maintains your solution state - perhaps it's an array of zero/one variables in a knapsack problem. It would be tempting to implement a clone() method like this in your Solution object:

Wrong Way To Do It:

public Object clone()
{   
    TSPSolution copy = (TSPSolution)super.clone();
    copy.sack = this.sack;
    return copy;
}   // end clone

All you've done is give your newly-cloned Solution a pointer to the original sack array. If you were to modify one Solution by manipulating the array, you would incorrectly be modifying the other Solution as well.

Instead, make sure you make a complete copy of your data structures. In case where your data structures are representing by simple arrays of primitives, you should have no problems using a clone() method like this:

Right Way To Do It:

public Object clone()
{   
    TSPSolution copy = (TSPSolution)super.clone();
    copy.sack = (int[])this.sack.clone();
    return copy;
}   // end clone

Another common way to represent your data is with a java.util.ArrayList or java.util.LinkedList. These are fairly efficient data structures depending on your problem type and can be a real headache-saver for problems like the Traveling Salesman Problem or Vehicle Routing Problem.

Suppose you create your own Vehicle.java and Customer.java classes each containing relevant information such as speed, endurance, location, capacity, demand, etc. An easy way to represent a tour would be to use Java's lists to store the customers you plan to visit in the order you plan to visit them.

In fact, you may end up with an ArrayList of ArrayLists to account for multiple vehicles. Again, be sure that you think through your clone() method and make sure that you're cloning deep enough to ensure independence in your solution objects.

In this case, it's probably okay if you don't clone the Vehicle and Customer objects since they don't change, but you will need to clone the ArrayLists.

OpenTS expects an objective/constraint penalties function to be able to evaluate a solution's worth. OpenTS will pass the ObjectiveFunction a Solution and optionally pass a proposed Move. If the passed move is not null, then the evaluation should consider the effect that executing this move on the solution would have before evaluating it.

If you can use some sort of incremental evaluation technique, this will save you time. If you must operate on the solution to actually calculate its value, you must return the solution to its original state before the method returns.

It may be helfpul to give yourself some helper methods in your ObjectiveFunction to separate the incremental evaluation from the absolute evaluation. You might setup your evaluate(...) method like this:

It May Help to Separate Your Logic:

public double[] evaluate( Solution soln, Move proposedMove )
{
    if( proposedMove == null )
        return evaluateAbsolutely( soln );
    else
        return evaluateIncrementally( soln, proposedMove );
}

Then you can deal with the two pieces of logic separately. If you cannot incrementally evaluate your solution but are forced to modify the Solution object first, make sure your Move object has a way to undo its operation:

Always Return the Solution to its Original State:

private double[] evaluateIncrementally( Solution soln, Move proposedMove )
{
    proposedMove.operateOn( soln );
    double[] val = evaluateAbsolutely( soln );
    proposedMove.undoOperation( soln );
    return val;
}

It is a common mistake to try to reuse arrays of doubles and mess it up (it's possible, but you have to be careful). When you're first writing your code and aren't fine tuning it to this level, it's easiest to evaluate your objective function values with scalars and then return a fresh array:

Avoid Reusing Arrays:

public double[] evaluate( Solution soln, Move proposedMove )
{
    double val1 = ...;
    double val2 = ...;

    return new double[]{ val1, val2 };
}

The array of returned values will later be compared lexicographically in the classic "goal-programming" style. If instead you want some goals to overpower higher goals, use the style of weighting the levels with appropriate values.

In this trivial example, suppose your ObjectiveFunction returns an array of three doubles in an assignment problem where the first value in the array (Goal #1) is the number of customers in a day who wait longer than 10 minutes on hold waiting for one of the available Tech Support personnel (objective value #2: minimize hiring), and the third value is the total cost of the operation.

We see in the tables above that with the lexicographical comparison of ObjectiveFunction values, that Goal #1 is absolutely more important than the rest of the goals which is why, in Solution Pair A, Soln 2 beats Soln 1 despite Soln 1's lower cost and number of people hired.

In Solution Pair B we see that there's a tie on Goal #1, so OpenTS compares the next goal and declares Soln 1 the winner for hiring fewer people. If this goal had been a tie, OpenTS would have moved on to the next goal.

Although all numbers are stored and calculated as doubles, they are cast to floats before being compared. This helps avoid the problems where two "equal" values stored as doubles differ by 0.000000000001 or some ridiculously small value.

When OpenTS considers whether or not some solution X is better than some other solution Y, the answer is No if the two objective function values result in ties for all of the goals.

By implementing and registering as a TabuSearchListener your objects can react dynamically to the search as it progresses. This gives you an easy way to trigger techniques such as Reactive/Adaptive Tabu Lists, Strategic Oscillation, Path Relinking, and Restarts.

When registered, your object will receive the following events:

newCurrentSolutionFound

Fired after each iteration whether or not the move that was selected actually made any change to your solution (that's your business).

newBestSolutionFound

Fired after an iteration when a solution has been found that is better than any previously-found solution.

unimprovingMoveMade

Fired after an iteration when the chosen move, probably due to a constraining tabu list, results in a move that is worse than when the iteration started.

tabuSearchStarted

Fired on the calling thread just before the tabu search starts the first iteration.

tabuSearchStopped

Fired on the tabu search's thread when there are no more iterations to solve.

The first three events listed above will be fired in that order, should more than one need to be fired in a given iteration.

In OpenTS versions prior to v1.0-exp2, if you changed the current or best solution using the setCurrentSolution( ... ) or setBestSolution( ... ) methods while responding to these events, the appropriate event would be fired again, resulting in an infinite loop. This "feature" has been removed since what it offers in the rare case that it's useful can be accomplished more safely in other ways.

You register as a TabuSearchListener by implementing the interface and registering with the TabuSearch object after you instantiate it:

Register As a TabuSearchListener

import org.coinor.opents.*;
public class MySearchProgram implements TabuSearchListener
{
    ...

    TabuSearch ts = new MultiThreadedTabuSearch( ... );
    ts.addTabuSearchListener( this );

    ...
}

You may find it easier to use Java's anonymous inner classes along with the TabuSearchAdapter class. With this design pattern, you only have to implements methods for the events you're actually interested in:

Use TabuSearchAdapter with Anonymous Inner Classes

    TabuSearch ts = new MultiThreadedTabuSearch( ... );
    ts.addTabuSearchListener( 
    new TabuSearchAdapter()
    {
        public void unimprovingMoveMade( TabuSearchEvent evt )
        {
            ...
        }
    } );

You might find it particularly useful to have your tabu list or objective function objects implement TabuSearchListener. Here we extend the included SimpleTabuList to make it a reactive tabu list:

Reactive Tabu List

import org.coinor.opents.*;
public class MyTabuList extends SimpleTabuList
 implements TabuSearchListener
{
    public final static int MAX_TENURE = 30;

    public void newBestSolutionFound( TabuSearchEvent evt )
    {   // Decrease tenure
        setTenure( Math.max( 1, (int)( 0.75 * getTenure() ) ) );
    }

    public void unimprovingMoveMade( TabuSearchEvent evt )
    {   // Increase tenure
        setTenure( Math.min( MAX_TENURE, getTenure() + 2 );
    }

    // We're not using these events
    public void newCurrentSolutionFound( TabuSearchEvent evt ){}
    public void tabuSearchStarted( TabuSearchEvent evt ){}
    public void tabuSearchStopped( TabuSearchEvent evt ){}
}

The tabuSearchStarted and tabuSearchStopped events are most important when using the MultiThreadedTabuSearch implemenation of the TabuSearch spec. When startSolving() is called on a MultiThreadedTabuSearch object, control returns immediately to the calling thread, and the tabu search runs on a newly-created thread.

If you have another part of your code, such as a progress bar or some other indicator, that needs to know when your tabu search has started - or more importantly, finished - register as a listener with the tabu search object and respond to the appropriate event.

In a well-designed GUI application, you should always offload long tasks such as a tabu search to another thread, and these two events will help you manage that task.

Here's a code fragment showing how we notify the user the tabu search has finished:

Notify When Done

TabuSearch ts = new MultiThreadedTabuSearch( ... );
final java.awt.Component parent = ...; // Your root window or similar

ts.addTabuSearchListener( new TabuSearchAdapter()
{
    public void tabuSearchStopped( TabuSearchEvent evt )
    {
        TabuSearch theTS = (TabuSearch)evt.getSource();
        Solution   best  = theTS.getBestSolution();
        final String msg = "Done. Best solution: " + best;

        SwingUtilities.invokeLater( new Runnable()
        {   public void run()
            {   JOptionPane.showMessageDialog( parent, msg );
            }
        });
    }
});