org.coinor.opents
Class SingleThreadedTabuSearch

java.lang.Object
  extended byorg.coinor.opents.TabuSearchBase
      extended byorg.coinor.opents.SingleThreadedTabuSearch
All Implemented Interfaces:
java.io.Serializable, TabuSearch
Direct Known Subclasses:
MultiThreadedTabuSearch

public class SingleThreadedTabuSearch
extends TabuSearchBase

This version of the TabuSearch does not create any new threads, making it ideal for embedding in Enterprise JavaBeans. The startSolving() method blocks until the given number of iterations have been completed.

This code is licensed for public use under the Common Public License version 0.5.
The Common Public License, developed by IBM and modeled after their industry-friendly IBM Public License, differs from other common open source licenses in several important ways:

Copyright 2001 Robert Harder

Since:
1.0
See Also:
Serialized Form

Field Summary
protected  AspirationCriteria aspirationCriteria
          Aspiration criteria.
protected  Solution bestSolution
          Best solution.
protected  boolean chooseFirstImprovingMove
          Choose first improving neighbor instead of best neighbor overall.
protected  Solution currentSolution
          Current solution.
protected static java.io.PrintStream err
          Print errors to this stream.
protected  boolean fireImprovingMoveMade
          Fire improving solution event at the end of the iteration.
protected  boolean fireNewBestSolution
          Fire new best solution event at the end of the iteration.
protected  boolean fireNewCurrentSolution
          Fire new current solution event at the end of the iteration.
protected  boolean fireNoChangeInValueMoveMade
          Fire no change in value solution event at the end of the iteration.
protected  boolean fireUnimprovingMoveMade
          Fire unimproving solution event at the end of the iteration.
protected  int iterationsToGo
          Iterations to go.
protected  boolean keepSolving
          Whether or not the tabu search should keep solving if it gets a chance to quit.
protected  boolean maximizing
          Maximizing: true.
protected  MoveManager moveManager
          Move manager.
protected  ObjectiveFunction objectiveFunction
          Objective function.
protected  boolean solving
          Whether or not the the tabu search is solving.
protected  TabuList tabuList
          Tabu list.
 
Constructor Summary
SingleThreadedTabuSearch()
          Constructs a SingleThreadedTabuSearch with no tabu objects set.
SingleThreadedTabuSearch(Solution initialSolution, MoveManager moveManager, ObjectiveFunction objectiveFunction, TabuList tabuList, AspirationCriteria aspirationCriteria, boolean maximizing)
          Constructs a SingleThreadedTabuSearch with all tabu objects set.
 
Method Summary
protected  void fireQueuedEvents()
          Fires events that are queued for firing at the end of an iteration.
static boolean firstIsBetterThanSecond(double[] first, double[] second, boolean maximizing)
          Deprecated.  
 AspirationCriteria getAspirationCriteria()
          Returns the aspiration criteria.
protected  java.lang.Object[] getBestMove(Solution soln, Move[] moves, ObjectiveFunction objectiveFunction, TabuList tabuList, AspirationCriteria aspirationCriteria, boolean maximizing, boolean chooseFirstImprovingMove)
          Gets the best move--one that should be used for this iteration.
protected static java.lang.Object[] getBestMove(Solution soln, Move[] moves, ObjectiveFunction objectiveFunction, TabuList tabuList, AspirationCriteria aspirationCriteria, boolean maximizing, boolean chooseFirstImprovingMove, TabuSearch This)
          The static method that actually does the work.
 Solution getBestSolution()
          Returns the best solution found by the tabu search.
 Solution getCurrentSolution()
          Returns the current solution being used by the tabu search.
 int getIterationsToGo()
          Returns the number of iterations left for the tabu search to execute.
 MoveManager getMoveManager()
          Returns the move manager being used by the tabu search.
 ObjectiveFunction getObjectiveFunction()
          Returns the objective function being used by the tabu search.
 TabuList getTabuList()
          Returns the tabu list being used by the tabu search.
protected  void internalSetBestSolution(Solution solution)
          Set the best solution and prepare to fire an event.
protected  void internalSetCurrentSolution(Solution solution)
          Set the current solution and prepare to fire an event.
 boolean isChooseFirstImprovingMove()
          Returns whether or not the tabu search engine will choose the first improving move it encounters at each iteration (true) or the best move (false).
protected  boolean isFireImprovingMoveMade()
          Returns whether or not the tabu search plans to fire an improving move made TabuSearchEvent at the end of the iteration.
protected  boolean isFireNewBestSolution()
          Returns whether or not the tabu search plans to fire a new best solution TabuSearchEvent at the end of the iteration.
protected  boolean isFireNewCurrentSolution()
          Returns whether or not the tabu search plans to fire a new current solution TabuSearchEvent at the end of the iteration.
protected  boolean isFireNoChangeInValueMoveMade()
          Returns whether or not the tabu search plans to fire a no change in value move made TabuSearchEvent at the end of the iteration.
protected  boolean isFireUnimprovingMoveMade()
          Returns whether or not the tabu search plans to fire an unimproving move made TabuSearchEvent at the end of the iteration.
static boolean isFirstBetterThanSecond(double[] first, double[] second, boolean maximizing)
          This single method is called many times to compare solutions.
protected  boolean isKeepSolving()
          Returns whether or not the tabu search should keep solving the next chance it gets to quit, like at the start of a new iteration.
 boolean isMaximizing()
          Returns whether or not the tabu search should be maximizing the objective function.
 boolean isSolving()
          Returns whether or not the tabu search is currently solving.
protected static boolean isTabu(Solution soln, Move move, double[] val, TabuList tabuList, AspirationCriteria aspirationCriteria, TabuSearch This)
          Determine if the move is tabu and consider whether or not it satisfies the aspiration criteria.
protected  void performOneIteration()
          This large method goes through one iteration.
 void setAspirationCriteria(AspirationCriteria aspirationCriteria)
          Sets the aspiration criteria, effective at the start of the next iteration.
 void setBestSolution(Solution solution)
          Sets the best solution, effective at the start of the next iteration, and fires an event to registered TabuSearchListeners.
 void setChooseFirstImprovingMove(boolean choose)
          Setting this to true will cause the search to go faster by not necessarily evaluating all of the moves in a neighborhood for each iteration.
 void setCurrentSolution(Solution solution)
          Sets the current solution, effective at the start of the next iteration, and fires an event to registered TabuSearchListeners.
protected  void setFireImprovingMoveMade(boolean b)
          Internally set whether or not an improving move made TabuSearchEvent should be fired at the end of the iteration.
protected  void setFireNewBestSolution(boolean b)
          Internally set whether or not a new best solution TabuSearchEvent should be fired at the end of the iteration.
protected  void setFireNewCurrentSolution(boolean b)
          Internally set whether or not a new current solution TabuSearchEvent should be fired at the end of the iteration.
protected  void setFireNoChangeInValueMoveMade(boolean b)
          Internally set whether or not a no change in value move made TabuSearchEvent should be fired at the end of the iteration.
protected  void setFireUnimprovingMoveMade(boolean b)
          Internally set whether or not an unimproving move made TabuSearchEvent should be fired at the end of the iteration.
 void setIterationsToGo(int iterations)
          Sets the number of iterations that the tabu search has left to go.
protected  void setKeepSolving(boolean keepSolving)
          Tells the tabu search internally whether or not to keep solving the next chance it gets to quit, like at the start of a new iteration.
 void setMaximizing(boolean maximizing)
          Sets whether the tabu search should be maximizing or minimizing the objective function.
 void setMoveManager(MoveManager moveManager)
          Sets the move manager, effective at the start of the next iteration.
 void setObjectiveFunction(ObjectiveFunction function)
          Sets the objective function, effective at the start of the next iteration, and re-evaluates the current and best solution values.
protected  void setSolving(boolean solving)
          Sets the status of either solving or not solving.
 void setTabuList(TabuList tabuList)
          Sets the tabu list, effective at the start of the next iteration.
 void startSolving()
          Starts the tabu search solving in the current thread, blocking until the iterationsToGo property is zero.
 void stopSolving()
          Stops the tabu search and preserves the number of iterations remaining.
 
Methods inherited from class org.coinor.opents.TabuSearchBase
addTabuSearchListener, fireImprovingMoveMade, fireNewBestSolution, fireNewCurrentSolution, fireNoChangeInValueMoveMade, fireTabuSearchStarted, fireTabuSearchStopped, fireUnimprovingMoveMade, getIterationsCompleted, incrementIterationsCompleted, removeTabuSearchListener
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

objectiveFunction

protected ObjectiveFunction objectiveFunction
Objective function.


moveManager

protected MoveManager moveManager
Move manager.


tabuList

protected TabuList tabuList
Tabu list.


aspirationCriteria

protected AspirationCriteria aspirationCriteria
Aspiration criteria.


currentSolution

protected Solution currentSolution
Current solution.


bestSolution

protected Solution bestSolution
Best solution.


iterationsToGo

protected int iterationsToGo
Iterations to go.


maximizing

protected boolean maximizing
Maximizing: true. Minimizing: false.


solving

protected boolean solving
Whether or not the the tabu search is solving.


keepSolving

protected boolean keepSolving
Whether or not the tabu search should keep solving if it gets a chance to quit.


fireNewCurrentSolution

protected boolean fireNewCurrentSolution
Fire new current solution event at the end of the iteration.


fireNewBestSolution

protected boolean fireNewBestSolution
Fire new best solution event at the end of the iteration.


fireUnimprovingMoveMade

protected boolean fireUnimprovingMoveMade
Fire unimproving solution event at the end of the iteration.


fireImprovingMoveMade

protected boolean fireImprovingMoveMade
Fire improving solution event at the end of the iteration.


fireNoChangeInValueMoveMade

protected boolean fireNoChangeInValueMoveMade
Fire no change in value solution event at the end of the iteration.


chooseFirstImprovingMove

protected boolean chooseFirstImprovingMove
Choose first improving neighbor instead of best neighbor overall.


err

protected static java.io.PrintStream err
Print errors to this stream.

Constructor Detail

SingleThreadedTabuSearch

public SingleThreadedTabuSearch()
Constructs a SingleThreadedTabuSearch with no tabu objects set.

Since:
1.0

SingleThreadedTabuSearch

public SingleThreadedTabuSearch(Solution initialSolution,
                                MoveManager moveManager,
                                ObjectiveFunction objectiveFunction,
                                TabuList tabuList,
                                AspirationCriteria aspirationCriteria,
                                boolean maximizing)
Constructs a SingleThreadedTabuSearch with all tabu objects set. The initial solution is evaluated with the objective function, becomes the currentSolution and a copy becomes the bestSolution.

Parameters:
initialSolution - The initial currentSolution
moveManager - The move manager
objectiveFunction - The objective function
tabuList - The tabu list
aspirationCriteria - The aspiration criteria or null if none is to be used
maximizing - Whether or not the tabu search should be maximizing the objective function
Since:
1.0
See Also:
Solution, ObjectiveFunction, MoveManager, TabuList, AspirationCriteria
Method Detail

performOneIteration

protected void performOneIteration()
                            throws NoMovesGeneratedException,
                                   NoCurrentSolutionException
This large method goes through one iteration. It performs these steps:

Throws:
NoMovesGeneratedException
NoCurrentSolutionException
Since:
1.0
See Also:
getBestMove(org.coinor.opents.Solution, org.coinor.opents.Move[], org.coinor.opents.ObjectiveFunction, org.coinor.opents.TabuList, org.coinor.opents.AspirationCriteria, boolean, boolean), isFirstBetterThanSecond(double[], double[], boolean), fireQueuedEvents()

getBestMove

protected java.lang.Object[] getBestMove(Solution soln,
                                         Move[] moves,
                                         ObjectiveFunction objectiveFunction,
                                         TabuList tabuList,
                                         AspirationCriteria aspirationCriteria,
                                         boolean maximizing,
                                         boolean chooseFirstImprovingMove)
Gets the best move--one that should be used for this iteration. By setting chooseFirstImprovingMove to true you tell the tabu search to return the first move it encounters that is improving and non-tabu rather than search through all of the moves. It's not static so that when the MultiThreadedTabuSearch invokes the performOneIteration method the proper method is invoked. Java's weird about overriding static methods...

Since:
1.0

getBestMove

protected static java.lang.Object[] getBestMove(Solution soln,
                                                Move[] moves,
                                                ObjectiveFunction objectiveFunction,
                                                TabuList tabuList,
                                                AspirationCriteria aspirationCriteria,
                                                boolean maximizing,
                                                boolean chooseFirstImprovingMove,
                                                TabuSearch This)
The static method that actually does the work. It's static so that the NeighborhoodHelper in the MultiThreadedTabuSearch can use the same code.

Since:
1.0

isTabu

protected static boolean isTabu(Solution soln,
                                Move move,
                                double[] val,
                                TabuList tabuList,
                                AspirationCriteria aspirationCriteria,
                                TabuSearch This)
Determine if the move is tabu and consider whether or not it satisfies the aspiration criteria.

Since:
1.0

firstIsBetterThanSecond

public static boolean firstIsBetterThanSecond(double[] first,
                                              double[] second,
                                              boolean maximizing)
Deprecated.  

Deprecated and renamed to isFirstBetterThanSecond(double[], double[], boolean) to be named more consistently. This method still works. It simply calls the newly-named version.

Parameters:
first - The first array of doubles
second - The second array of doubles
maximizing - Whether or not the tabu search should be maximizing
Returns:
true if the first array of numbers is better than the second
Since:
1.0

isFirstBetterThanSecond

public static boolean isFirstBetterThanSecond(double[] first,
                                              double[] second,
                                              boolean maximizing)
This single method is called many times to compare solutions. Although all data is stored as doubles, they are cast to floats before they are compared. This ensures that the inevitable errors associated with all floating point numbers do not affect the likely intent of the numbers.

Parameters:
first - The first array of doubles
second - The second array of doubles
maximizing - Whether or not the tabu search should be maximizing
Returns:
true if the first array of numbers is better than the second
Since:
1.0

fireQueuedEvents

protected void fireQueuedEvents()
Fires events that are queued for firing at the end of an iteration.

Since:
1.0

internalSetCurrentSolution

protected void internalSetCurrentSolution(Solution solution)
Set the current solution and prepare to fire an event.

Parameters:
solution - The new current solution
Since:
1.0

internalSetBestSolution

protected void internalSetBestSolution(Solution solution)
Set the best solution and prepare to fire an event.

Parameters:
solution - The new best solution
Since:
1.0

setSolving

protected void setSolving(boolean solving)
Sets the status of either solving or not solving. This does not start and stop the solver--it only sets the reporting flag.

Parameters:
solving - Whether or not the tabu search should be marked as solving or not.
Since:
1.0

setKeepSolving

protected void setKeepSolving(boolean keepSolving)
Tells the tabu search internally whether or not to keep solving the next chance it gets to quit, like at the start of a new iteration.

Parameters:
keepSolving - Whether or not to keep solving
Since:
1.0

isKeepSolving

protected boolean isKeepSolving()
Returns whether or not the tabu search should keep solving the next chance it gets to quit, like at the start of a new iteration.

Returns:
Whether or not to keep solving
Since:
1.0

setFireNewCurrentSolution

protected void setFireNewCurrentSolution(boolean b)
Internally set whether or not a new current solution TabuSearchEvent should be fired at the end of the iteration.

Parameters:
b - Whether or not to fire a new current solution event.
Since:
1.0

setFireNewBestSolution

protected void setFireNewBestSolution(boolean b)
Internally set whether or not a new best solution TabuSearchEvent should be fired at the end of the iteration.

Parameters:
b - Whether or not to fire a new best solution event.
Since:
1.0

setFireUnimprovingMoveMade

protected void setFireUnimprovingMoveMade(boolean b)
Internally set whether or not an unimproving move made TabuSearchEvent should be fired at the end of the iteration.

Parameters:
b - Whether or not to fire an unimproving move made event.
Since:
1.0

setFireImprovingMoveMade

protected void setFireImprovingMoveMade(boolean b)
Internally set whether or not an improving move made TabuSearchEvent should be fired at the end of the iteration.

Parameters:
b - Whether or not to fire an improving move made event.
Since:
1.0-exp7

setFireNoChangeInValueMoveMade

protected void setFireNoChangeInValueMoveMade(boolean b)
Internally set whether or not a no change in value move made TabuSearchEvent should be fired at the end of the iteration.

Parameters:
b - Whether or not to fire a no change in value move made event.
Since:
1.0-exp7

isFireNewCurrentSolution

protected boolean isFireNewCurrentSolution()
Returns whether or not the tabu search plans to fire a new current solution TabuSearchEvent at the end of the iteration.

Returns:
whether or not the tabu search plans to fire a new current solution event
Since:
1.0

isFireNewBestSolution

protected boolean isFireNewBestSolution()
Returns whether or not the tabu search plans to fire a new best solution TabuSearchEvent at the end of the iteration.

Returns:
whether or not the tabu search plans to fire a new best solution event
Since:
1.0

isFireUnimprovingMoveMade

protected boolean isFireUnimprovingMoveMade()
Returns whether or not the tabu search plans to fire an unimproving move made TabuSearchEvent at the end of the iteration.

Returns:
whether or not the tabu search plans to fire an unimproving move made event
Since:
1.0

isFireImprovingMoveMade

protected boolean isFireImprovingMoveMade()
Returns whether or not the tabu search plans to fire an improving move made TabuSearchEvent at the end of the iteration.

Returns:
whether or not the tabu search plans to fire an improving move made event
Since:
1.0-exp7

isFireNoChangeInValueMoveMade

protected boolean isFireNoChangeInValueMoveMade()
Returns whether or not the tabu search plans to fire a no change in value move made TabuSearchEvent at the end of the iteration.

Returns:
whether or not the tabu search plans to fire a no change in value move made event
Since:
1.0-exp7

startSolving

public void startSolving()
Starts the tabu search solving in the current thread, blocking until the iterationsToGo property is zero.

Since:
1.0c
See Also:
TabuSearch.setIterationsToGo(int), TabuSearch.getIterationsToGo()

stopSolving

public void stopSolving()
Stops the tabu search and preserves the number of iterations remaining.

Since:
1.0
See Also:
TabuSearch.setIterationsToGo(int), TabuSearch.getIterationsToGo()

isSolving

public boolean isSolving()
Returns whether or not the tabu search is currently solving.

Returns:
Whether or not the tabu search is currently solving.
Since:
1.0

setObjectiveFunction

public void setObjectiveFunction(ObjectiveFunction function)
Sets the objective function, effective at the start of the next iteration, and re-evaluates the current and best solution values.

Parameters:
function - The new objective function.
Since:
1.0
See Also:
ObjectiveFunction

setMoveManager

public void setMoveManager(MoveManager moveManager)
Sets the move manager, effective at the start of the next iteration.

Parameters:
moveManager - The new move manager.
Since:
1.0
See Also:
MoveManager

setTabuList

public void setTabuList(TabuList tabuList)
Sets the tabu list, effective at the start of the next iteration.

Parameters:
tabuList - The new tabu list.
Since:
1.0
See Also:
TabuList

setAspirationCriteria

public void setAspirationCriteria(AspirationCriteria aspirationCriteria)
Sets the aspiration criteria, effective at the start of the next iteration. A null value means there is no aspiration criteria.

Parameters:
aspirationCriteria - The new aspiration criteria
Since:
1.0
See Also:
AspirationCriteria

setBestSolution

public void setBestSolution(Solution solution)
Sets the best solution, effective at the start of the next iteration, and fires an event to registered TabuSearchListeners.

Parameters:
solution - The new best solution.
Since:
1.0
See Also:
Solution

setCurrentSolution

public void setCurrentSolution(Solution solution)
Sets the current solution, effective at the start of the next iteration, and fires an event to registered TabuSearchListeners.

Parameters:
solution - The new current solution.
Since:
1.0
See Also:
Solution

setIterationsToGo

public void setIterationsToGo(int iterations)
Sets the number of iterations that the tabu search has left to go. If the tabu search was previously idle, that is iterationsToGo was less than or equal to zero, the tabu search will not automatically begin again. In this case the tabu search will not begin again until startSolving() is called.

Parameters:
iterations - The number of iterations left for the tabu earch to execute.
Since:
1.0
See Also:
startSolving()

setMaximizing

public void setMaximizing(boolean maximizing)
Sets whether the tabu search should be maximizing or minimizing the objective function. A value of true means maximize. A value of false means minimize.

Parameters:
maximizing - Whether or not the tabu search should be maximizing the objective function.
Since:
1.0

setChooseFirstImprovingMove

public void setChooseFirstImprovingMove(boolean choose)
Setting this to true will cause the search to go faster by not necessarily evaluating all of the moves in a neighborhood for each iteration. Instead of evaluating all of the moves and selecting the best one for execution, setting this will cause the tabu search engine to select the first move that it encounters that causes an improvement to the current solution. The default value is false.

Parameters:
choose - Whether or not the first improving move will be chosen
Since:
1.0.1

getObjectiveFunction

public ObjectiveFunction getObjectiveFunction()
Returns the objective function being used by the tabu search.

Returns:
The objective function being used by the tabu search.
Since:
1.0
See Also:
ObjectiveFunction

getMoveManager

public MoveManager getMoveManager()
Returns the move manager being used by the tabu search.

Returns:
The move manager being used by the tabu search.
Since:
1.0
See Also:
MoveManager

getTabuList

public TabuList getTabuList()
Returns the tabu list being used by the tabu search.

Returns:
The tabu list being used by the tabu search.
Since:
1.0
See Also:
TabuList

getAspirationCriteria

public AspirationCriteria getAspirationCriteria()
Returns the aspiration criteria. A null value means there is no aspiration criteria.

Returns:
The aspiration criteria
Since:
1.0
See Also:
AspirationCriteria

getBestSolution

public Solution getBestSolution()
Returns the best solution found by the tabu search.

Returns:
The best solution found by the tabu search.
Since:
1.0
See Also:
Solution

getCurrentSolution

public Solution getCurrentSolution()
Returns the current solution being used by the tabu search.

Returns:
The current solution being used by the tabu search.
Since:
1.0
See Also:
Solution

getIterationsToGo

public int getIterationsToGo()
Returns the number of iterations left for the tabu search to execute.

Returns:
The number of iterations left for the tabu search to execute.
Since:
1.0

isMaximizing

public boolean isMaximizing()
Returns whether or not the tabu search should be maximizing the objective function.

Returns:
Whether or not the tabu search should be maximizing the objective function.
Since:
1.0

isChooseFirstImprovingMove

public boolean isChooseFirstImprovingMove()
Returns whether or not the tabu search engine will choose the first improving move it encounters at each iteration (true) or the best move (false).

Returns:
Whether or not the first improving move will be chosen
Since:
1.0.1