cpsat-autotune 0.2.0

A tool to automatically tune the hyperparameters of the OR-Tools' CP-SAT solver.

cpsat-autotune: A Hyperparameter Tuning Tool for Google's OR-Tools CP-SAT Solver

cpsat-autotune is a Python library designed to optimize the hyperparameters of Google's OR-Tools CP-SAT solver for specific problem instances. While CP-SAT is already highly optimized for a broad range of generic problems, fine-tuning its parameters for particular problem sets can yield significant performance gains. This tool leverages the optuna optimization library to systematically explore and suggest optimal hyperparameter configurations tailored to your needs.

Also check out our other projects:

• The CP-SAT Primer: A comprehensive guide to Google's OR-Tools CP-SAT solver.
• CP-SAT Log Analyzer: A tool to analyze the logs generated by Google's OR-Tools CP-SAT solver.

Use Case

cpsat-autotune is not a universal solution that guarantees a performance boost for all uses of the CP-SAT solver. Instead, it is specifically designed to enhance solver efficiency in targeted scenarios, particularly within the context of Adaptive Large Neighborhood Search (ALNS).

Adaptive Large Neighborhood Search (ALNS) Context

In ALNS, the CP-SAT solver is frequently invoked with a strict time limit to solve similar problem instances as part of a larger iterative optimization process. The goal is to incrementally improve a solution by exploring different neighborhoods of the problem space. In this context, achieving even modest performance gains on average instances can significantly impact the overall efficiency of the search process, even if it results in occasional performance drops on outlier instances.

Benefits of Tuning in ALNS

• Average Performance Gains: By tuning the solver’s hyperparameters to optimize performance on typical instances, cpsat-autotune can reduce the average time per iteration. This is particularly valuable in ALNS, where a large number of solver calls are made.
• Tolerance for Outliers: In an ALNS framework, occasional slower iterations due to deteriorated performance on outlier instances are generally acceptable, as the search process can recover in subsequent iterations. Thus, the focus can be on enhancing the solver's average performance rather than ensuring consistent performance across all instances.
• Augmented Solver Strategies: Instead of completely replacing the CP-SAT solver with a single tuned configuration, cpsat-autotune allows you to tune hyperparameters for one or more specific instance sets and incorporate these as additional strategies within ALNS. This means you can maintain the default CP-SAT parameters while augmenting the solver's capability with tailored configurations. ALNS can then automatically select the most effective strategy for each iteration, leveraging the diverse set of tuned hyperparameters alongside the default configuration for optimal performance.

Installation

You can install cpsat-autotune using pip:

pip install -U cpsat-autotune

Make sure to update the package before every use to ensure you have the latest version, as this project is still a prototype.

Basic Usage

Here is a basic example of how to use cpsat-autotune to optimize the time required to find an optimal solution for a CP-SAT model:

from cpsat_autotune import import_model, tune_time_to_optimal

# Load your model from a protobuf file
model = import_model("models/medium_hg.pb")

# Tune the model to minimize the time to reach an optimal solution
best = tune_time_to_optimal(
    model,
    max_time_in_seconds=3,  # Enter a time limit slightly above what the solver with default parameters needs
    n_samples_for_trial=5,  # Number of samples for each trial
    n_samples_for_verification=20,  # Number of samples for each statistically relevant comparison.
    n_trials=50,  # Number of trials to run with Optuna
)

Sample output:

────────────────────────────────────────────── OPTIMIZED PARAMETERS ───────────────────────────────────────────────
┏━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━┳━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━┓
┃ #   ┃ Parameter                     ┃ Value ┃ Contribution ┃ Default Value ┃
┡━━━━━╇━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━╇━━━━━━━━━━━━━━╇━━━━━━━━━━━━━━━┩
│ 1   │ binary_minimization_algorithm │   3   │    14.41%    │       1       │
│ 2   │ cp_model_probing_level        │   1   │    19.12%    │       2       │
│ 3   │ search_branching              │   7   │    20.91%    │       0       │
│ 4   │ cut_level                     │   0   │    45.56%    │       1       │
└─────┴───────────────────────────────┴───────┴──────────────┴───────────────┘
────────────────────────────────────────────────── Descriptions ───────────────────────────────────────────────────
1. binary_minimization_algorithm Specifies the algorithm used for binary clause minimization during conflict
analysis. The options are:

 • 0 NO_BINARY_MINIMIZATION.
 • 1 BINARY_MINIMIZATION_FIRST
 • 2 BINARY_MINIMIZATION_WITH_REACHABILITY
 • 3 EXPERIMENTAL_BINARY_MINIMIZATION
 • 4 BINARY_MINIMIZATION_FIRST_WITH_TRANSITIVE_REDUCTION

2. cp_model_probing_level Defines the intensity of probing during presolve, where variables are temporarily fixed
to infer more information about the problem. Higher levels of probing can result in a more simplified problem but
require more computation time during presolve.

3. search_branching Defines the branching strategy the solver uses to navigate the search tree. The options are:

 • 0 (AUTOMATIC_SEARCH): The solver automatically selects the most appropriate strategy.
 • 1 (FIXED_SEARCH): Follows a fixed variable order, as specified by the user or the problem model.
 • 2 (PORTFOLIO_SEARCH): Uses a combination of multiple strategies to explore the search space.
 • 3 (LP_SEARCH): Branches based on the LP relaxation of the problem, leveraging the reduced costs of variables.
 • 4 (PSEUDO_COST_SEARCH): Branches using pseudo-costs, which are estimates of the impact of branching decisions
   based on past experiences.
 • 5 (PORTFOLIO_WITH_QUICK_RESTART_SEARCH): Quickly explores different heuristics with low conflict limits, aiming
   to find a good initial solution.
 • 6 (HINT_SEARCH): Prioritizes decisions based on hints provided by the user or the problem model.
 • 7 (PARTIAL_FIXED_SEARCH): Begins with a fixed strategy, then switches to automatic search for the remaining
   decisions.
 • 8 (RANDOMIZED_SEARCH): Introduces randomization into branching decisions to diversify the search.

4. cut_level Sets the level of effort the solver will invest in generating cutting planes, which are linear
constraints added to remove infeasible regions. Properly applied, cuts can significantly reduce the search space
and help the solver find an optimal solution more quickly.
───────────────────────────────────────────────────────────────────────────────────────────────────────────────────
┏━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━┳━━━━━━┳━━━━━━┳━━━━━━━━━━┓
┃ Metric                 ┃ Mean ┃  Min ┃  Max ┃ #Samples ┃
┡━━━━━━━━━━━━━━━━━━━━━━━━╇━━━━━━╇━━━━━━╇━━━━━━╇━━━━━━━━━━┩
│ Default Metric Value   │ 1.68 │ 1.33 │ 2.21 │       20 │
│ Optimized Metric Value │ 0.76 │ 0.54 │  0.9 │       20 │
└────────────────────────┴──────┴──────┴──────┴──────────┘
───────────────────────────────────────────────────────────────────────────────────────────────────────────────────
╭──────────────────────────────────────────────────── WARNING ────────────────────────────────────────────────────╮
│                                                                                                                 │
│      The optimized parameters listed above were obtained based on a sampling approach                           │
│      and may not fully capture the complexities of the entire problem space.                                    │
│      While statistical reasoning has been applied, these results should be considered                           │
│      as a suggestion for further evaluation rather than definitive settings.                                    │
│                                                                                                                 │
│      It is strongly recommended to validate these parameters in larger, more comprehensive                      │
│      experiments before adopting them in critical applications.                                                 │
│                                                                                                                 │
╰─────────────────────────────────────────────────────────────────────────────────────────────────────────────────╯

Available Tuning Methods

cpsat-autotune provides two primary methods for tuning:

1. tune_time_to_optimal

This method tunes the CP-SAT solver's hyperparameters to minimize the time required to find an optimal solution. It is useful when you need a guaranteed solution without a fixed time limit.

Parameters:

• model: The CP-SAT model you wish to tune.
• max_time_in_seconds: The maximum time allowed for each solve operation. This parameter influences the runtime of the tuning process, so it should be set carefully.
• relative_gap_limit: (Optional) The relative optimality gap for considering a solution as optimal. A value of 0.0 requires exact optimality. Defaults to 0.0.
• n_samples_for_trial: (Optional) The number of samples taken in each trial. Defaults to 10.
• n_samples_for_verification: (Optional) The number of samples used to verify parameters after tuning. Defaults to 30.
• n_trials: (Optional) The number of trials to run. Defaults to 100.

Returns:

• dict: The best parameters found during the tuning process.

Notes:

• The concrete analysis, including baseline performance and the evaluation of the best parameters, is printed to the console.

2. tune_for_quality_within_timelimit

This method tunes hyperparameters to maximize or minimize the objective value within a specified time limit. It is useful when you need to find a good solution within a fixed time frame without requiring guarantees.

Parameters:

• model: The CP-SAT model to be tuned.
• max_time_in_seconds: The time limit for each solve operation in seconds. This value should be less than the time required for the solver to find an optimal solution with default parameters.
• obj_for_timeout: The objective value to return if the solver times out. This value should be worse than a trivial solution.
• direction: Specify 'maximize' or 'minimize' depending on whether you want to optimize for the best or worst solution quality.
• n_samples_for_trial: (Optional) The number of samples taken in each trial. Defaults to 10.
• n_samples_for_verification: (Optional) The number of samples used to verify parameters after tuning. Defaults to 30.
• n_trials: (Optional) The number of trials to run. Defaults to 100.

Returns:

• dict: The best parameters found during the tuning process.

Notes:

• The concrete analysis, including baseline performance and the evaluation of the best parameters, is printed to the console.

Using the cpsat-autotune CLI

The cpsat-autotune CLI is a command-line interface for tuning CP-SAT hyperparameters to optimize the performance of your models. Below are the instructions on how to use the CLI.

Commands

The cpsat-autotune CLI provides two main commands: time and quality.

time Command

The time command tunes CP-SAT hyperparameters to minimize the time required to find an optimal solution.

Usage

cpsat-autotune time [OPTIONS] MODEL_PATH

Options

• MODEL_PATH: Path to the model file (required).
• --max-time: Maximum time allowed for each solve operation in seconds (required).
• --relative-gap: Relative optimality gap for considering a solution as optimal (default: 0.0).
• --n-trials: Number of trials to execute in the tuning process (default: 100).
• --n-samples-trial: Number of samples to take in each trial (default: 10).
• --n-samples-verification: Number of samples for verifying parameters (default: 30).

Example

cpsat-autotune time --max-time 60 --relative-gap 0.01 --n-trials 50 --n-samples-trial 5 --n-samples-verification 20 path/to/model/file

quality Command

The quality command tunes CP-SAT hyperparameters to maximize or minimize solution quality within a given time limit.

Usage

cpsat-autotune quality [OPTIONS] MODEL_PATH

Options

• MODEL_PATH: Path to the model file (required).
• --max-time: Time limit for each solve operation in seconds (required).
• --obj-for-timeout: Objective value to return if the solver times out (required).
• --direction: Direction to optimize the objective value (maximize or minimize, required).
• --n-trials: Number of trials to execute in the tuning process (default: 100).
• --n-samples-trial: Number of samples to take in each trial (default: 10).
• --n-samples-verification: Number of samples for verifying parameters (default: 30).

Example

cpsat-autotune quality --max-time 60 --obj-for-timeout 100 --direction maximize --n-trials 50 --n-samples-trial 5 --n-samples-verification 20 path/to/model/file

Help

For more information on each command and its options, you can use the --help flag:

cpsat-autotune time --help
cpsat-autotune quality --help

This will display detailed descriptions and usage instructions for each command.

The Importance of Avoiding Overfitting

While tuning hyperparameters can improve solver performance for specific instances, it also increases the risk of overfitting. Overfitting occurs when the solver's performance is significantly improved on the training set of problems but deteriorates on new, slightly different instances. For example, tuning may reduce solve times on a set of similar problems but could result in excessive solve times or failure on problems that deviate from the training set.

How does the Tuning Work?

cpsat-autotune uses the optuna library to perform hyperparameter tuning on a preselected set of parameters. The output of optuna is then further refined and the significance of certain parameters is evaluated. Based on the assumption that the default parameters are already well-tuned for a broad range of problems, cpsat-autotune identifies the most significant changes to the default configuration and suggests these as potential improvements. It does take a few shortcuts to speed things up, while collecting more samples for important values.

Recommendations:

• Robust Performance: If consistent performance across a variety of instances is crucial, stick with the default CP-SAT parameters.
• Targeted Performance: If you are solving a large number of similar problems and can tolerate potential performance drops on outliers, use the suggested parameters after careful consideration.

Contributing

Contributions are welcome. Please ensure that your code adheres to the project's style guidelines and includes appropriate tests.

License

This project is licensed under the MIT License.