cz.cuni.mff.ksi.jinfer.iss.heuristics.improvement
Class LocalBranching

java.lang.Object
  cz.cuni.mff.ksi.jinfer.iss.heuristics.improvement.LocalBranching

All Implemented Interfaces:

NamedModule, Heuristics, ImprovementHeuristic

public class LocalBranching
extends Object
implements ImprovementHeuristic

This heuristic works by creating a constrained sub-problem and then solving it. The constraint is as follows: the maximum Hamming distance between the old and new solution is limited to a constant k. Some implementation details:

• When working with AMs and ID sets, the Hamming distance is defined as follows: sum over all AMs of (1 if solutions differ at this AM, 0 otherwise).
• k is fixed to be a ratio of the total AM count.

Local branching always works on the incumbent solution, and adds the new solution to the pool.

Constructor Summary

LocalBranching(double ratio, int timeLimit)
Constructs an instance of this heuristic.

Method Summary

String	getDisplayName() Returns a user friendly name of the module.
String	getModuleDescription() Returns the information about this module's inner workings.
String	getName() Returns a user friendly yet unique name of the module.
void	start(Experiment experiment, List<IdSet> feasiblePool, HeuristicCallback callback) Start the heuristic run.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

LocalBranching

public LocalBranching(double ratio,
                      int timeLimit)

Constructs an instance of this heuristic.

Parameters:

ratio - The total number of AMs is multiplied by this fraction, result is the parameter k - maximum Hamming distance between the old and the new solution.

timeLimit - Time limit in seconds of the GLPK run.

Method Detail

start

public void start(Experiment experiment,
                  List<IdSet> feasiblePool,
                  HeuristicCallback callback)
           throws InterruptedException

Description copied from interface: ImprovementHeuristic

Start the heuristic run. Use the information in the provided experiment to improve the provided pool (possibly only one) of feasible solutions.

Specified by:

start in interface ImprovementHeuristic

Parameters:

experiment - Experiment in context of which to run the heuristic.

feasiblePool - List of feasible solutions found so far.

callback - Callback to be invoked when finished.

Throws:

InterruptedException

getName

public String getName()

Description copied from interface: NamedModule

Returns a user friendly yet unique name of the module.

Specified by:

getName in interface NamedModule

Returns:

Unique module name.

getDisplayName

public String getDisplayName()

Description copied from interface: NamedModule

Returns a user friendly name of the module. This name is not neccessary unique.

Specified by:

getDisplayName in interface NamedModule

Returns:

Displayable module name.

getModuleDescription

public String getModuleDescription()

Description copied from interface: NamedModule

Returns the information about this module's inner workings. Most of the time will be equal to a call to NamedModule.getDisplayName(), but if the module for example consists of more sub-modules, their names should be listed here.

Specified by:

getModuleDescription in interface NamedModule

Returns:

String describing inner structure of the module.