Skip to content

LNS

This page gives an overview of the LNS class with all its methods. If you want to modify the LNS adjusting these methods is the best start to do so. Most LNS parameters are stored inside a LNSOptions instance. Default values can be accessed via the provided presets.

Note

UNSET can used as a marker to differentiate between parameters that were not set and those that were explicitly set to None. Before starting the search, all remaining UNSET parameters will be set to None. Additional default parameters can be set using the preset argument/option. Use fastlane -h to see all available presets and their parameter values.

LNS

Class handling and performing LNS.

Attributes:

Name Type Description
options LNSOptions

LNSOptions object.
logger LNSLogger

Logger object.
files list[str]

List of problem encoding files.
step_c int

Step/iteration counter.
new_model Optional[Model]

The newly obtained model.
current_model Model

The current model.
best_model Model

The best model found so far.
stats list[dict[str, Any]]

List of statistics dictionaries.
_config_catalog ConfigCatalog

Parsed config catalog.
_active_config ActiveConfig

Active config for the current iteration.
prev_fixed_atoms set[Symbol]

Set of previously fixed atoms.
_is_variable bool

Indicates if the problem is variable.
_adaptive_strategy AdaptiveStrategy

Adaptive strategy object.
init_solver_config SolverConfig

Initial solver configuration.
lns_solver_config SolverConfig

LNS solver configuration.
timer Timer

Timer object.
_printout bool

Indicates if printout is enabled.
_iter_format str

Iteration format string.

__init__(files: list[str], args: Optional[dict[str, Any]] = None, options: Optional[LNSOptions] = None)

Initialization of the lns object.

Parameters:

Name Type Description Default
files list[str]

Problem encodings.

 required
args Optional[dict[str, Any]]

Parsed arguments.

 None
options Optional[LNSOptions]

LNSOptions object.

 None

accepted() -> None

New model is accepted.

better() -> None

New model is better than the best model.

check_accept() -> bool

Check whether new model is accepted. Accept if desired variability is achieved.

Returns:

Type Description
bool

Whether new model is accepted or not.

check_better() -> bool

Check whether new model is better.

Returns:

Type Description
bool

Whether new model is better or not.

check_stop() -> bool

Check whether to stop LNS.

Stop if: max # of steps exceeded, overall time limit exceeded or solver finished or stopped.

Returns:

Type Description
bool

Whether to stop LNS or not.

destroy() -> set[Symbol]

Destroy portion of atoms.

Returns:

Type Description
set[Symbol]

Fixed (not destroyed) atoms.

get_first_solution() -> bool

Find initial solution.

Returns:

Type Description
bool

Whether a solution was found or not

main() -> None

Run Large-Neighbourhood Search according to set parameters.

parse_options(args: dict[str, Any]) -> None

Parse options from args.

Parameters:

Name Type Description Default
args dict[str, Any]

Parsed arguments.

 required

post_first_solution() -> None

Get LNS configuration catalog and prepare heuristics if needed.

post_repair() -> None

Get new configuration from adaptive strategy.

post_setup() -> None

Ground the base ASP program.

pre_destroy() -> None

Load operator specifications and check variability of the configuration before destruction.

pre_next_iteration() -> None

Prepare for the next iteration. Update time and solve limits.

pre_setup() -> None

Get solver configurations, prepare time limits and set random seed.

print_result() -> None

Print the result of the LNS process.

repair(fixed_atoms: set[Symbol]) -> Optional[Model]

Repair solution and collect some statistics.

Parameters:

Name Type Description Default
fixed_atoms set[Symbol]

Fixed atoms.

 required

Returns:

Type Description
Optional[Model]

Repaired model.

setup_solver() -> None

Setup the solver for LNS.

update_stats(new_model: Optional[Model]) -> None

Update statistics after each iteration.

Parameters:

Name Type Description Default
new_model Optional[Model]

The new model obtained after repair.

 required

LNSOptions dataclass

Configuration for LNS.

Parameters:

Name Type Description Default
log_level int

Logging level.

 30
solver Solver

Solver to be used.

 ClingoSolver()
seed Optional[int]

Seed used for both solving and random destruction.

 None
time_limit Optional[int]

Overall time limit for the search in seconds.

 None
max_steps Optional[int]

Step limit for the search.

 None
status_interval int

Interval in steps for logging the current status.

 50
parallel_mode Optional[str]

Clingo parallel mode, see clingo -t option.

 None
clingo_args Optional[str]

Additional arguments passed to the solver.

 None
context Any

Context for grounding.

 None
minimize_variable Optional[Symbol]

Variable to minimize, used by clingo-dl.

 None
preset Optional[str]

Options preset to be applied.

 None
lex_weight int

Weight factor for scalarizing lexicographic costs.

 1000
learning_rate float

Learning rate for updating config weights.

 0.5
default_adaptive_strategy_name str

Default adaptive strategy for selecting LNS configurations in each iteration.

 'static'
init_time_limit Optional[int]

Time limit for the initial solve call in seconds.

 10
init_solve_limit Optional[str]

Stop initial solve call after this many conflicts and restarts, None or "umax,umax" for no limit.

 None
init_cutoff Optional[int]

Time limit to find new model during initial solving.

 None
init_configuration Optional[str]

Solver configuration for initial solving.

 None
init_opt_strategy Optional[str]

Optimization strategy for initial solving.

 None
init_opt_heuristic Optional[str]

Optimization heuristic for initial solving.

 None
init_restart_on_model Optional[bool]

Restart on model for initial solving.

 None
init_opt_mode Optional[str]

Optimization mode for initial solving.

 None
constrained bool

Whether to use constrained LNS, Short-hand for lns-opt-mode={"mode": "opt", "nf": 0, "modifier": "dynamic"}.

 False
destruction tuple[str, int]

Destruction type ["simple","declarative"] and destruction percent for "simple" destruction, "auto" for automatic destruction rate.

 ('simple', 40)
_declarative bool

Whether to use declarative destruction. Can cause issue when set directly, use destruction attribute.

 False
_destruction_rate int

Destruction rate for simple destruction. Can cause issue when set directly, use destruction attribute.

 40
auto_converter AutoDestructionConverter

Automatic destroy percentage converter.

 LastImprovementDestructionConverter()
fix str

How to fix atoms during repair ["assumptions", "heuristics"].

 'assumptions'
accept_variability int

Required variability for accepting new model in percent. 0 = always accept

 0
accept_improvement int

Required improvement for accepting new model in percent. 20 = solution can be upto 20% worse and still accepted 0 = solution has to be strictly better

 0
lns_time_limit Optional[int]

Time limit for solver in each LNS step.

 5
lns_solve_limit Optional[str]

Stop solver in each LNS step after this many conflicts and restarts, None or "umax,umax" for no limit.

 None
lns_cutoff Optional[int]

Time limit to find new model during LNS solving.

 None
lns_configuration Optional[str]

Solver configuration for LNS solving.

 None
lns_opt_strategy Optional[str]

Optimization strategy for LNS solving.

 None
lns_opt_heuristic Optional[str]

Optimization heuristic for LNS solving.

 None
lns_restart_on_model Optional[bool]

Restart on model for LNS solving.

 None
lns_heuristic Optional[str]

Heuristic to use in LNS solving.

 'Domain'
lns_opt_mode dict[str, Optional[str]]

Optimization mode for LNS solving.

 (lambda: {'mode': None, 'nf': None, 'modifier': None})()
lns_time_limit_increase_rate int

Increase lns solver time limit after each iteration in percent.

 0
lns_solve_limit_increase_rate int

Increase lns solver solve limit after each iteration in percent.

 0
lns_cutoff_threshold Optional[int]

Increase cutoff after times no better solution could be found.

 None
lns_cutoff_increase_rate int

Increase lns solver cutoff after each iteration in percent.

 0

apply_overrides(overrides: dict[str, Any]) -> None

Apply overrides to this config.

UNSET values are ignored, all other values (including None) are applied.

Parameters:

Name Type Description Default
overrides dict[str, Any]

Candidate override values.

 required

apply_preset() -> None

Apply preset configuration if specified.

build_adaptive_strategy(strategy_name: str, logger: Logger) -> AdaptiveStrategy

Build adaptive strategy instance from selected strategy name.

get_init_solver_configuration() -> SolverConfig

Get the initial solver configuration.

Returns:

Type Description
SolverConfig

Initial Solver configuration.

get_lns_solver_configuration() -> SolverConfig

Get the LNS solver configuration.

Returns:

Type Description
SolverConfig

LNS solver configuration.

get_supported_adaptive_strategy_names() -> list[str] classmethod

Return supported adaptive strategy names.

prepare() -> None

Prepare configuration by replacing UNSET with None and resolving any other parameters.

Helper classes

Model

Simplified Model class

Attributes:

Name Type Description
shown set[Symbol]

Set of shown atoms.
true set[Symbol]

Set of true atoms.
cost list[int]

List of costs.
assignments list[str]

List of assignments.

get_cost_str() -> str

Get cost of model as string.

Returns:

Type Description
str

Cost as string.

print_model() -> str

Print model.

Returns:

Type Description
str

Printed string.

Timer

Timer class for measuring time intervals.

Attributes:

Name Type Description
_started bool

Indicates if the timer has started.
_ringing bool

Indicates if the timer is ringing (time limit reached).
_start_time float

The time when the timer was started.
_time_limit Optional[int]

The time limit in seconds (None for no limit).

is_ringing: bool property

Check if the timer is ringing (i.e., if the time limit has been reached).

__init__() -> None

Initialize the timer.

get_elapsed_time() -> float

Get the elapsed time since the timer started.

Returns:

Type Description
float

Elapsed time in seconds.

remaining_time() -> int

Get the remaining time before the timer rings.

Returns:

Type Description
int

Remaining time in seconds, -1 for infinite.

reset() -> None

Reset the timer.

restart() -> None

Restart the timer with the same time limit.

start(time_limit: Optional[int]) -> None

Start the timer with a specified time limit. None for no time limit.

Parameters:

Name Type Description Default
time_limit Optional[int]

Time limit in seconds.

 required