Greedy Binary Optimization#

`GreedyBinaryOptimizer`([configs])	Implementation of the Greedy Binary optimization approach. The algorithm is as follows::.
`GreedyBinaryOptimizerConfigs`(*[, debug, ...])	Configuration dataclass for the `GreedyBinaryOptimizer`.
`GreedyBinaryOptimizerResults`(*[, ...])	Container for results/data generated by the `GreedyBinaryOptimizer`.

A module providing access to multiple Binary optimization routines.

class GreedyBinaryOptimizerConfigs(*, debug=False, verbose=False, output_dir='./_PYOED_RESULTS_', size=None, name='GreedyBinaryOptimizer: Greedy Binary Optimization', screen_output_iter=1, file_output_iter=100, fun=None, budgets=None, maximize=True, objective_value_tracker=None, use_stochastic_greedy=False, stochastic_epsilon=0.1, stochastic_batch_size=None, random_seed=None)[source]#

Bases: OptimizerConfigs

Configuration dataclass for the GreedyBinaryOptimizer.

Parameters:

verbose (bool) – a boolean flag to control verbosity of the object.
debug (bool) – a boolean flag that enables adding extra functionlity in a debug mode
output_dir (str | Path) – the base directory where the output files will be saved.
name (str) – name of the optimizer. Default is None.
screen_output_iter (int) – iteration interval for screen output. Default is 1. Note that this should be a positive integer to enforce proper effect.
file_output_iter (int) – iteration interval for file output. Default is 1. Note that this should be a positive integer to enforce proper effect.
size (int | None) – dimension of the target/solution variable. Must be a positive integer
fun (Callable | None) – the objective function to be optimization. For a given binary state/design of size size it returns a scalar.
budgets (list[int] | None) – the budgets for the optimization problem. This must be passed, and must be a list of positive integers.
maximize (bool) – Whether the objective is to be maximized or minimized. Default is True.
objective_value_tracker (dict | None) –
a dictionary that holds values of the objective function. This can be helpful if the optimizer was run previously and objective values have been saved. This is used as the initializer of the tracker used while solving the optimization problem.

Note

The objective_value_tracker in the configurations object is not updated in-place as the solver proceeds. It is only used as the initializer of the internal tracker. The results returned from the optimizer contains the updated tracker.
use_stochastic_greedy (bool) – Whether to use the stochastic variant of greedy optimization. See the docstring of GreedyBinaryOptimizer for more details. Default is False.
stochastic_epsilon (float) – Desired epsilon to attain the 1 - 1/e - epsilon approximation guarantee of this algorithm. Default is 0.1.
stochastic_batch_size (None | int) – Size of explored batch per stochastic greedy iteration. Default is None, in which case the size of (size / max(budgets)) log(1/epsilon) is used.
random_seed (int | None) – Random seed for randomization in stochastic greedy.

fun: Callable | None#

budgets: list[int] | None#

maximize: bool#

objective_value_tracker: dict | None#

use_stochastic_greedy: bool#

stochastic_epsilon: float#

stochastic_batch_size: None | int#

random_seed: int | None#

__init__(*, debug=False, verbose=False, output_dir='./_PYOED_RESULTS_', size=None, name='GreedyBinaryOptimizer: Greedy Binary Optimization', screen_output_iter=1, file_output_iter=100, fun=None, budgets=None, maximize=True, objective_value_tracker=None, use_stochastic_greedy=False, stochastic_epsilon=0.1, stochastic_batch_size=None, random_seed=None)#

class GreedyBinaryIntermediateResults(*, iteration=None, best_design_idx=None, best_design_objval=None, trajectory=None)[source]#

Bases: OptimizerResults

Container for intermediate results/data generated by the

Parameters:

iteration (int | None) – the iteration number at which the intermediate results were generated.
best_design_idx (ndarray | None) – the index of the best design found at the above iteration.
best_design_objval (float | None) – the value of the objective function evaluated at the above best design.
improvement – the improvement in the objective function value from the previous iteration.
trajectory (dict[int, float] | None) – a dictionary containing the value of the objective function evaluated through the course of the algorithm. The dictionary is indexed by the integer indexes of the generated binary states. Only saved if save_trajectory is set to True in the user passed configurations.

iteration: int | None#

best_design_idx: ndarray | None#

best_design_objval: float | None#

trajectory: dict[int, float] | None#

__init__(*, iteration=None, best_design_idx=None, best_design_objval=None, trajectory=None)#

class GreedyBinaryOptimizerResults(*, optimal_design=<factory>, optimal_design_objval=None, message=<property object>, converged=False, objective_value_tracker=<factory>, intermediate_results=None, configurations=None)[source]#

Bases: OptimizerResults

Container for results/data generated by the GreedyBinaryOptimizer.

Parameters:

optimal_design (ndarray) – the optimal design (binary vector).
optimal_design_objval (float | None) – the value of the objective function evaluated at the above optimal design.
message (str) – a string message describing the final status of the algorithm
objective_value_tracker (dict | None) – a dictionary containing the value of the objective function evaluated through the course of the algorithm. The dictionary is indexed by the integer indexes of the generated binary states.
intermediate_results (list[GreedyBinaryIntermediateResults] | None) – a list of GreedyBinaryIntermediateResults objects containing intermediate results of the optimization algorithm.
configurations (GreedyBinaryOptimizerConfigs | dict | None) – an object holding problem configurations.

optimal_design: ndarray#

optimal_design_objval: float | None#

converged: bool#

objective_value_tracker: dict | None#

intermediate_results: list[GreedyBinaryIntermediateResults] | None#

configurations: GreedyBinaryOptimizerConfigs | dict | None#

property x: ndarray#: The optimal solution of the optimization problem.

property success: bool#: Whether or not the optimizer exited successfully.

message: str#

property fun: float#: Value of objective function at the optimal solution x.

property nfev: int#: Number of evaluations of the objective functions.

property njev: int#: Number of evaluations of the the Jacobian of the objective function.

property nhev: int#: Number of evaluations of the the Hessian of the objective function.

property nit: int#: Number of iterations performed by the optimizer.

__init__(*, optimal_design=<factory>, optimal_design_objval=None, message=<property object>, converged=False, objective_value_tracker=<factory>, intermediate_results=None, configurations=None)#

class GreedyBinaryOptimizer(configs=None)[source]#

Bases: Optimizer, RandomNumberGenerationMixin

Implementation of the Greedy Binary optimization approach. The algorithm is as follows:

Start with an empty design.
For i = 1 to max_budget:
    a. Update the design by adding the sensor that maximizes the objective function
Return the discovered design

If use_stochastic_greedy is True, then instead this performs the stochastic greedy variant. This is as follows:

1. Start with an empty design.
2. For i = 1 to max_budget:
    a. Select s random, yet unactivated, sensors.
    b. Update the design by adding the sensor from a. that best improves the
       objective function
3. Return the discovered design

note::

Stochastic Greedy is research from the following paper:

Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi, Jan Vondrák, and Andreas Krause. 2015. Lazier than lazy greedy. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI’15). AAAI Press, 1812–1818.

__init__(configs=None)[source]#

Constructor for the Greedy Binary Optimizer.

Parameters:: configs (GreedyBinaryOptimizerConfigs | dict | None) – configurations for the optimizer. This can be an instance of GreedyBinaryOptimizerConfigs, a dictionary, or None. If None, default configurations are used.

validate_configurations(configs, raise_for_invalid=True)[source]#

Check the passed configuratios and make sure they are conformable with each other, and with current configurations once combined. This guarantees that any key-value pair passed in configs can be properly used

Note

Here only the locally-defined configurations in GreedyBinaryOptimizerConfigs are validated. Finally, super classes validators are called.

Parameters:

configs (dict | GreedyBinaryOptimizerConfigs) – full or partial (subset) configurations to be validated
raise_for_invalid (bool) – if True raise TypeError for invalid configrations type/key. Default True

Returns:

flag indicating whether passed configurations dictionary is valid or not

Raises:

AttributeError – if any (or a group) of the configurations does not exist in the model configurations GreedyBinaryOptimizerConfigs.
PyOEDConfigsValidationError – if the configurations are invalid and raise_for_invalid is set to True.

Return type:

bool

update_configurations(**kwargs)[source]#

Take any set of keyword arguments, and lookup each in the configurations, and update as nessesary/possible/valid

Raises:: PyOEDConfigsValidationError – if invalid configurations passed

reset_objective_value_tracker()[source]#: Reset the objective value tracker and set it to the tracker in the configurations.

clear_objective_value_tracker()[source]#: Remove all entries from the objective value tracker; set it to empty dictionary.

objective_function_value(design)[source]#

A function to prevent redundant computations of the objective (utility function) by looking up tracker before evaluation

Parameters:: design – binary state/design variable to evaluate objective value at
Returns:: value of the objective/utility function at the passed design
Raises:: TypeError if the passed design is not of the right size

bruteforce_objective_values(fun=None, num_active=None)[source]#

Evaluate the value of the objective (obj) at all possible binary combinations;

Returns:: a dictionary of objective values evaluated for each possible binary instance. The dictionary indexed by unique integer indexes.
Return type:: dict[int, float]

..note::: This function should be used ONLY for testing in small-dimensional problems.

solve()[source]#

Start solving the binary optimization problem using the greedy formulation.

Returns:: an instance of GreedyBinaryOptimizerResults.

plot_results(results, num_random_samples=64, random_seed=None, bruteforce=False, fun_symbol='U', output_dir=None, keep_plots=False, fontsize=22, usetex=True, plots_format='pdf', **kwargs)[source]#

property size#: Dimension/size of the optimziation variable.

property budgets#: Budget for the optimization problem.

property objective_value_tracker#: Reference to the objective value tracker dictionary for easy access

property use_stochastic_greedy#

property stochastic_epsilon#

property stochastic_batch_size#

class FederovExchangeOptimizerConfigs(*, debug=False, verbose=False, output_dir='./_PYOED_RESULTS_', size=None, name='FederovExchangeOptimizer', screen_output_iter=1, file_output_iter=100, fun=None, initial_design=None, budget=None, tolerance=1e-06, exchange_loops=None, maximize=True, objective_value_tracker=None, random_seed=123)[source]#

Bases: OptimizerConfigs

Configuration dataclass for the FederovExchangeOptimizer.

Parameters:

verbose (bool) – a boolean flag to control verbosity of the object.
debug (bool) – a boolean flag that enables adding extra functionlity in a debug mode
output_dir (str | Path) – the base directory where the output files will be saved.
name (str) – name of the optimizer. Default is None.
screen_output_iter (int) – iteration interval for screen output. Default is 1. Note that this should be a positive integer to enforce proper effect.
file_output_iter (int) – iteration interval for file output. Default is 1. Note that this should be a positive integer to enforce proper effect.
size (int | None) – dimension of the target/solution variable. Must be a positive integer
fun (Callable | None) – the objective function to be optimization. For a given binary state/design of size size it returns a scalar.
initial_design (ndarray | None) – a binary vector that represents the initial design. If not passed, a random design is used.
budget (int) – the budget for the optimization problem. This must be passed, and must be a a positive integer.
tolerance (float) – the relative tolerance for the exchange; if the best swap has improvement less than tolerance then the algorithm will terminate. Default is 1e-6.
exchange_loops (int) – the number of loops for the exchange optimization. If not passed, the default will be budget.
maximize (bool) – Whether the objective is to be maximized or minimized. Default is True.
objective_value_tracker (dict | None) – a dictionary that holds values of the objective function. This can be helpful if the optimizer was run previously and objective vlaues have been saved. This is used as the initializer of the tracker used while solving the optimization problem.
random_seed (int) –
seed for the random number generator. If not passed, 123 is used.

Note

The objective_value_tracker in the configurations object is not updated as the solver proceeds. It is only used as the initializer of the internal tracker. The results returned from the optimizer contains the updated tracker.

fun: Callable | None#

initial_design: ndarray | None#

budget: int#

tolerance: float#

exchange_loops: int#

maximize: bool#

objective_value_tracker: dict | None#

random_seed: int#

__init__(*, debug=False, verbose=False, output_dir='./_PYOED_RESULTS_', size=None, name='FederovExchangeOptimizer', screen_output_iter=1, file_output_iter=100, fun=None, initial_design=None, budget=None, tolerance=1e-06, exchange_loops=None, maximize=True, objective_value_tracker=None, random_seed=123)#

class FederovExchangeIntermediateResults(*, iteration=None, best_design_idx=None, best_design_objval=None, swap=None)[source]#

Bases: OptimizerResults

Container for intermediate results/data generated by the

Parameters:

iteration (int | None) – the iteration number at which the intermediate results were generated.
best_design_idx (ndarray | None) – the index of the best design found at the above iteration.
best_design_objval (float | None) – the value of the objective function evaluated at the above best design.
improvement – the improvement in the objective function value from the previous iteration.
swap (tuple[int, int] | None) – the indices of the sensors that were swapped in the above iteration.

iteration: int | None#

best_design_idx: ndarray | None#

best_design_objval: float | None#

swap: tuple[int, int] | None#

__init__(*, iteration=None, best_design_idx=None, best_design_objval=None, swap=None)#

class FederovExchangeOptimizerResults(*, optimal_design=<factory>, optimal_design_objval=None, message='', objective_value_tracker=<factory>, intermediate_results=None, configurations=None)[source]#

Bases: OptimizerResults

Container for results/data generated by the FederovExchangeOptimizer.

Parameters:

optimal_design (ndarray) – the optimal design (binary vector).
optimal_design_objval (float | None) – the value of the objective function evaluated at the above optimal design.
messae – a string message describing the final status of the algorithm
objective_value_tracker (dict | None) – a dictionary containing the value of the objective function evaluated through the course of the algorithm. The dictionary is indexed by the integer indexes of the generated binary states.
intermediate_results (list[FederovExchangeIntermediateResults] | None) – a list of FederovExchangeIntermediateResults objects containing intermediate results of the optimization algorithm.
configurations (FederovExchangeOptimizerConfigs | dict | None) – an object holding problem configurations.

optimal_design: ndarray#

optimal_design_objval: float | None#

message: str#

objective_value_tracker: dict | None#

intermediate_results: list[FederovExchangeIntermediateResults] | None#

configurations: FederovExchangeOptimizerConfigs | dict | None#

__init__(*, optimal_design=<factory>, optimal_design_objval=None, message='', objective_value_tracker=<factory>, intermediate_results=None, configurations=None)#

class FederovExchangeOptimizer(configs=None)[source]#

Bases: Optimizer, RandomNumberGenerationMixin

An implementation of the Federov Exchange optimization approach. See [Federov_1972] for more details.

[Federov_1972]

Fedorov, V. V. Theory of Optimal Experiments. Academic Press, 1972.

__init__(configs=None)[source]#

Constructor for the Federov Exchange Optimizer.

Parameters:: configs (FederovExchangeOptimizerConfigs | dict | None) – configurations for the optimizer. This can be an instance of FederovExchangeOptimizerConfigs, a dictionary, or None. If None, default configurations are used.

validate_configurations(configs, raise_for_invalid=True)[source]#

Check the passed configuratios and make sure they are conformable with each other, and with current configurations once combined. This guarantees that any key-value pair passed in configs can be properly used

Note

Here only the locally-defined configurations in FederovExchangeOptimizerConfigs are validated. Finally, super classes validators are called.

Parameters:

configs (dict | FederovExchangeOptimizerConfigs) – full or partial (subset) configurations to be validated
raise_for_invalid (bool) – if True raise TypeError for invalid configrations type/key. Default True

Returns:

flag indicating whether passed configurations dictionary is valid or not

Raises:

AttributeError – if any (or a group) of the configurations does not exist in the model configurations FederovExchangeOptimizerConfigs.
PyOEDConfigsValidationError – if the configurations are invalid and raise_for_invalid is set to True.

Return type:

bool

update_configurations(**kwargs)[source]#

Take any set of keyword arguments, and lookup each in the configurations, and update as nessesary/possible/valid

Raises:: PyOEDConfigsValidationError – if invalid configurations passed

reset_objective_value_tracker()[source]#: Reset the objective value tracker and set it to the tracker in the configurations.

clear_objective_value_tracker()[source]#: Remove all entries from the objective value tracker; set it to empty dictionary.

objective_function_value(design)[source]#

A function to prevent redundant computations of the objective (utility function) by looking up tracker before evaluation

Parameters:: design – binary state/design variable to evaluate objective value at
Returns:: value of the objective/utility function at the passed design
Raises:: TypeError if the passed design is not of the right size

bruteforce_objective_values(fun=None, num_active=None)[source]#

Evaluate the value of the objective (obj) at all possible binary combinations;

Returns:: a dictionary of objective values evaluated for each possible binary instance. The dictionary indexed by unique integer indexes.
Return type:: dict[int, float]

..note::: This function should be used ONLY for testing in small-dimensional problems.

solve()[source]#

Start solving the binary optimization problem using the greedy formulation.

Returns:: an instance of FederovExchangeOptimizerResults.

plot_results(results, num_random_samples=64, random_seed=None, bruteforce=False, fun_symbol='U', output_dir=None, keep_plots=False, fontsize=22, usetex=True, plots_format='pdf')[source]#

property size#: Dimension/size of the optimziation variable.

property budget#: Budget for the optimization problem.

property exchange_loops#: Number of loops for the exchange optimization.

property tolerance#: Relative tolerance for the exchange; if the best swap has improvement less than tolerance then the algorithm will terminate.

property maximize#: Flag indicating whether the objective is to be maximized or minimized.

property initial_design#: Initial design for the optimization problem.

property objective_value_tracker#: Reference to the objective value tracker dictionary for easy access