Gray Box Tuning

The overall tuning runtime is mainly driven by the runtime of the underlying target algorithm. In general, you can limit this runtime by providing a cpu timeout per evaluation via --cpuTimeout. To reduce the runtime, wasted on out-timing target algorithm runs, the OPTANO Algorithm Tuner (OAT) provides an innovative gray box extension, which aims for detecting and cancelling these runs at runtime, before the specified time limit is actually reached.

Background

Technically, the gray box extension of OAT tries to classify timeouts and non-timeouts at runtime. For this purpose, it makes use of a balanced random forest classifier, trained on the target algorithm's runtime features during the tuning. For example, a runtime feature of a MIP solver might be the current MIP gap, (un-)explored node count or the count of feasible solutions. This classification is repeated regularly over time until the target algorithm finishes or reaches the given timeout. Whenever the random forest predicts a timeout, the evaluation is stopped and its current result (e.g. a MIP Gap) is reported/treated as a timeout result.

Training of Gray Box Classifier

The gray box random forest is trained with data that is gathered during the first k generations of the tuning. Afterwards, the timeout detection is started. To benefit from the additional information that is collected during the tuning, it is re-trained after every following generation.

Parameters

You can adapt the behaviour of the gray box extension with the following parameters:

--enableDataRecording={BOOL} [false]
If this option is enabled, this OPTANO Algorithm Tuner instance will record the target algorithm's runtime features and write data log files, potentially used for gray box tuning. To enable gray box tuning, this option and the gray box tuning option need to be enabled.
--dataRecordUpdateInterval={NUMBER} [5% of CPU timeout]
Sets the update interval of the data recorder in seconds. Every dataRecordUpdateInterval seconds a data point is recorded and the gray box classifier is applied, if gray box tuning is enabled.
--enableGrayBox={BOOL} [false]
If this option is enabled, this OPTANO Algorithm Tuner instance will use gray box tuning in order to minimize the overall tuning time.
--grayBoxConfidenceThreshold={NUMBER} [0.75]
Sets the confidence threshold of the gray box random forest. The current target algorithm run is cancelled by the gray box, if the confidence of the random forest exceeds this threshold.
--grayBoxStartGeneration={NUMBER} [5]
Sets the 0-indexed gray box start generation. Before this generation, no target algorithm run is cancelled by the gray box.
--grayBoxStartTimePoint={NUMBER} [5% of CPU timeout]
Sets the gray box start time point during a target algorithm run in seconds. Before this time point, no target algorithm run is cancelled by the gray box.

Note that you can also record the target algorithm's runtime features without making use of the presented gray box extension by enabling the data recording option (i.e. --enableDataRecording=true), but not the gray box tuning option (i.e. enableGrayBox=false).

In addition, you might want to set the following technical parameters:

--dataRecordDirectory={ABSOLUTE_PATH} [current directory/DataLogFiles]
Sets the path to the directory where the data log files should be written to.
--removeDataRecordsFromMemoryAfterTraining={BOOL} [false]
If this option is enabled, this OPTANO Algorithm Tuner instance will remove the list of data records from memory after training the gray box random forest and read in all data log files again in every generation. This option will decrease the memory usage, but increase the time, needed to read in the data log files in every generation.

How to support gray box tuning?

In order to support gray box tuning you need to implement the following two interfaces in your custom target algorithm adapter.

IGrayBoxTargetAlgorithm

The interface IGrayBoxTargetAlgorithm comes with the following two events / methods.

  • The event OnNewDataRecord should be invoked by the target algorithm adapter every DataRecordUpdateInterval seconds to record a data point and apply the gray box classifier. The GrayBoxHandler of OAT makes use of the AdapterDataRecord, passed with this invokation, to construct a new data record entry (see Data Record Entry) and applies the gray box classifier.
  • The method CancelByGrayBox is responsible for cancelling the current target algorithm run, if the gray box classifier predicts a timeout.

ICustomGrayBoxMethods

The interface ICustomGrayBoxMethods comes with the following two methods.

  • The method GetGrayBoxFeaturesFromDataRecord is responsible for returning the desired gray box features, used by the gray box random forest, from a given data record entry.
  • The method GetGrayBoxFeatureNamesFromDataRecord is responsible for returning the desired gray box feature names, used for logging, from a given data record entry.

Exemplary Implementation

The provided Gurobi adapter gives an example on how to make use of the presented gray box extension and on how to implement the corresponding interfaces.

Notes on the Data Recorder

Data Record Entry

A data record entry consists of the following two subclasses.

  • The TunerDataRecord contains all data, which is available in the tuner.
    • NodeID
    • GenerationID
    • TournamentID
    • RunID
    • InstanceID
    • GenomeID: This column contains the serialized GenomeDoubleRepresentation.
    • GrayBoxConfidence
    • Genome: These columns contain the GenomeDoubleRepresentation, grouped by columns.
    • FinalResult
  • The AdapterDataRecord contains all data, which is available in the target algorithm adapter.
    • TargetAlgorithmName
    • TargetAlgorithmStatus
    • ExpendedCpuTime
    • ExpendedWallClockTime
    • TimeStamp
    • AdapterFeatures: These columns contain the target algorithm's runtime features.
    • CurrentGrayBoxResult: These columns contain the result, which is returned, if the current evaluation is cancelled by the gray box.

Note that OAT provides the base class AdapterFeaturesBase to support the implementation of your own adapter features (e.g. see Gurobi adapter).

Data Record Directory

By enabling the data recording option, OAT will write the following files to the data record directory during the tuning.

  • dataLog_generation_{GenerationId}_process_{ProcessId}_id_{EvaluationActorId}_{TargetAlgorithmStatus}.csv contains the presented data record entries.
  • generationGenomeComposition.csv contains all genomes, sorted by generations.
  • generationInstanceComposition.csv contains all instances, sorted by generations.

By enabling the gray box tuning option, OAT will write the following additional files.

  • grayBoxRandomForest.rdf contains the serialized gray box random forest.
  • featureImportance.csv contains the feature importance, given by the gray box random forest, sorted by generations.