Robust Constrained Binary Optimization#

`RobustConstrainedBinaryReinforceOptimizer`([...])	The `RobustConstrainedBinaryReinforceOptimizer` is a modification from `RobustBinaryReinforceOptimizer` where only the Bernoulli distribution modeling the random variable is replaced with a generalized conditional Bernoulli model that inherently models budget/cost constraints.
`RobustConstrainedBinaryReinforceOptimizerConfigs`(*)	Configuration dataclass for the `RobustConstrainedBinaryReinforceOptimizer`.
`RobustConstrainedBinaryReinforceOptimizerResults`(*)	Container for results/data generated by the `RobustBinaryReinforceOptimizerResults`.

A module providing access to multiple Robust Binary optimization routines.

class RobustConstrainedBinaryReinforceOptimizerConfigs(*, debug=False, verbose=False, output_dir='./_PYOED_RESULTS_', size=None, name='RobustConstrainedBinaryReinforceOptimizer: Robust Constrained Binary Optimization via Stochastic Learning', screen_output_iter=1, file_output_iter=100, fun=None, initial_policy=None, maximize=True, def_stepsize=0.1, decay_step=False, Newton_step=False, stochastic_gradient_sample_size=32, baseline='optimal', optimal_baseline_batch_size=32, optimal_sample_size=5, objective_value_tracker=None, maxiter=100, pgtol=1e-12, monitor_iterations=True, random_seed=None, antithetic=True, uniform_random_sample_size=0, num_resets=0, uncertain_parameter_size=None, maxmin=True, fun_grad_parameter=None, fun_grad_design=None, uncertain_parameter_sample=<factory>, uncertain_parameter_bounds=None, solve_by_relaxation=False, reset_initial_guess=False, deterministic_optimization_routine='Scipy-L-BFGS-B', tol=1e-12, outer_opt_maxiter=1000, inner_opt_maxiter=10000, uncertain_parameter_max_num_digits=12, budgets=None)[source]#

Bases: RobustBinaryReinforceOptimizerConfigs

Configuration dataclass for the RobustConstrainedBinaryReinforceOptimizer. This inherits all keys/configurations/attributes of RobustBinaryReinforceOptimizerConfigs with the additional keys/attributes described below.

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_policy (ndarray | Iterable | None) – the initial probabilistic policy parameter (activation/success probability of the Bernoulli distribution)
maximize (bool) – if True the objective is to be maximized, otherwise minimization is assumed
def_stepsize (float) – default step size (learning rate) in the direction (or the opposite) of the gradient. Default is 1.
decay_step (bool) – if True reduce the learning rate (step size) as the algorithm proceeds
Newton_step (bool) – if True use second-order derivative to define the update direction
stochastic_gradient_sample_size (int) – size of the sample to generate (from current policy at each iteration) to estimate (using MC) the policy gradient
baseline (str | None) –
name/type of the baseline used to reduce variability of the stochastic estimate of the gradient to use (if any); possible values are None, ‘none’, ‘optimal’, ‘heuristic’. These are explained as follows:
- ’none’ | None: no baseline is used.
- ’heuristic’: evaluate an empirical baseline \((J(0)+J(1))/2\) with \(J\) being the passed fun.
- ’optimal’: a constant baseline is found by approximating the optimal baseline where optimality is defined as minimum variability of the estimator.
optimal_baseline_batch_size (int) – size of the batch/sample to use for optimal baseline estimation; used if baseline==True.
optimal_sample_size (int) – size of the sample to return from the final/optimal policy upon termination of the optimizer
objective_value_tracker (dict | None) –
a dictionary that holds values of the objective function for sampled binary vectors. 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.

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 contain another copy of the objective_value_tracker with updated sampled binary vectors and corresponding objectives.
uniform_random_sample_size (int) – size of a random sample generated uniformly (0.5 probability) for performance evaluation.
num_resets (None | int) – number of resets during optimization
uncertain_parameter_size (int | None) – The dimension/size of the uncertain parameter
maxmin (bool) – if True, a max-min optimization prolem is assumed, otherwise, a min-max problem is considere.
fun_grad_parameter (Callable | None) – If this is callable, it is (similar to fun configuration required by the parent class,) a function that accepts a binary design, and a realization of the the uncertain parameter (design, parameter). This is a function that calculates the gradient of of the objective function ‘fun’ with respect to the uncertainty paramter. If None, finite differences is used to calculate such gradient, though this will be expensive.
fun_grad_design (Callable | None) – if given, a function that calculates the gradient of fun with respect to the relaxed design; similar to fun, this function accepts two paramters (design, param).
maxiter (int) – maximum number of iterations of Polyak algorithm. This controls the number of times the algorithms alternates between updating the policy/design and the uncertain parameter. The updates for each of those is carried out by the corresponding optimizers which have their own number of iterations set by outer_opt_maxiter and inner_opt_maxiter, respectively.
outer_opt_maxiter (int) – maximum number of iterations of the optimizaer solving the outer optimization problem (maximization of the design/policy). This sets the maximum number of iterations of the optimization algorithm that updates the policy (outer optimization). This controls maxiter passed to the stochastic (or relaxed) optimization algorithm that optimizes for a design or policy parameters.
inner_opt_maxiter (int) – maximum number of iterations of the inner optimization problem. This is passed to the inner loop optimizer that solves the inner optimization for an optimal uncertain parameter.
uncertain_parameter_sample (Iterable[ndarray]) – sample from the uncertain parameter space (param). This is used as the initializer of the tracker used while solving the optimization problem.
uncertain_parameter_bounds (Tuple[None, None] | Iterable[Tuple[float | None, float | None]] | None) – bounds/domain of the uncertain parameter.
solve_by_relaxation (bool) – whether to allow relaxation of the design or use stochastic binary approach if True, then fun_grad_design should be given, otherwise finite differences is used to approximate it.
deterministic_optimization_routine (str) – Name of the optimization routine to be used for the inner optimization problem (over the uncertain parameter. This is also used for the outer optimization problem is solve_by_relaxation is True.
tol (float) – tolerance used for termination of inner optimization steps (over the uncertain parameter). This is different from pgtol used for the outer stochastic binary optimization termination.
budgets (Iterable[int] | None) – None, a non-negative number ranging from 0 to the size of the distribution, or an iterable (e.g., list) of non-negative numbers from 0 to the size of the distribution. If passed, this defines the budget constraint(s).

budgets: Iterable[int] | None#

__init__(*, debug=False, verbose=False, output_dir='./_PYOED_RESULTS_', size=None, name='RobustConstrainedBinaryReinforceOptimizer: Robust Constrained Binary Optimization via Stochastic Learning', screen_output_iter=1, file_output_iter=100, fun=None, initial_policy=None, maximize=True, def_stepsize=0.1, decay_step=False, Newton_step=False, stochastic_gradient_sample_size=32, baseline='optimal', optimal_baseline_batch_size=32, optimal_sample_size=5, objective_value_tracker=None, maxiter=100, pgtol=1e-12, monitor_iterations=True, random_seed=None, antithetic=True, uniform_random_sample_size=0, num_resets=0, uncertain_parameter_size=None, maxmin=True, fun_grad_parameter=None, fun_grad_design=None, uncertain_parameter_sample=<factory>, uncertain_parameter_bounds=None, solve_by_relaxation=False, reset_initial_guess=False, deterministic_optimization_routine='Scipy-L-BFGS-B', tol=1e-12, outer_opt_maxiter=1000, inner_opt_maxiter=10000, uncertain_parameter_max_num_digits=12, budgets=None)#

class RobustConstrainedBinaryReinforceOptimizerResults(*, optimal_policy=None, optimal_policy_sample=None, optimal_policy_sample_objval=None, optimal_design=<factory>, optimal_design_objval=None, uncertain_parameter_sample=None, optimal_uncertain_parameter=None, optimization_trajectory=None, optimization_trajectory_objval=None, optimization_trajectory_stoch_objval=None, inner_optimization_results=None, outer_optimization_results=None, converged=False, maxiter_reached=False, message=<property object>, objective_value_tracker=None, configurations=None, budgets=None)[source]#

Bases: RobustBinaryReinforceOptimizerResults

Container for results/data generated by the RobustBinaryReinforceOptimizerResults. This is similar to RobustBinaryReinforceOptimizerResults with the following added attributes.

Parameters:

optimal_policy (ndarray | None) – the parameters of the optimal policy (probability of activation of each entry of the design)
optimal_policy_sample (ndarray | None) – design sample generated by sampling the optimal policy (Bernoulli samples with probababilities set to the optimal policy parameters optimal_policy_parameters)
optimal_policy_sample_objval (ndarray | None) – value of the objective function \(J\) evaluated at each design in optimal_sample
optimal_design (ndarray) – the optimal design (binary vector) sampled from the optimal_policy.
optimal_design_objval (float | None) – the value of the objective function evaluated at the above optimal design.
uncertain_parameter_sample (list[ndarray] | None) – sample from the uncertain parameter space (param) expanded by the solution algorithm
optimal_uncertain_parameter (ndarray | None) – the value of the uncertain parameter corresponding the the optimal solution.
optimization_trajectory (list[ndarray, ndarray] | None) – trajectory (consecutive parameters) of the policy parameters generated along the optimization iterations; populated only if monitor_iterations configuration is set to True. The optimization trajectory is on the form [(d0, p0), (d1, p1), ...] where di is either the design (binary) variable or the Bernoulli parameters, and pi is the uncertain parameter.
optimization_trajectory_objval (list[float] | None) – value of the deterministic objective function, that is \(J\) along the optimization trajectory; populated only if solve_by_relaxation configuration is set to True. This is the fomr [J(d0, p0), J(d1, p1), ...] where `J is the fun in the configurations.
optimization_trajectory_stoch_objval (list[float] | None) – value (MC estimate) of the stochastic objective function, that is \(E[J]\) along the optimization trajectory; populated only if solve_by_relaxation configuration is set to False. This is the fomr [E(J(d0, p0)), E(J(d1, p1)), ...] where the expection E is estimated by averaging (monte carlo estimate).
inner_optimization_results (list[dict] | None) – a list holding results for each of the inner optimization iterations.
outer_optimization_results (list[dict] | None) – a list holding results for each of the outer optimization iterations.
converged (bool) – True if the algorithm converged, False otherwise.
msg – 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.
configurations (None | dict) – a dictionary holding problem configurations. This can be obtained by calling asdict() of the configurations object used by the optimizer, e.g., BinaryReinforceOptimizerConfigs.
budgets (Iterable[int] | None) – None, a non-negative number ranging from 0 to the size of the distribution, or an iterable (e.g., list) of non-negative numbers from 0 to the size of the distribution. If passed, this defines the budget constraint(s).

budgets: Iterable[int] | None#

__init__(*, optimal_policy=None, optimal_policy_sample=None, optimal_policy_sample_objval=None, optimal_design=<factory>, optimal_design_objval=None, uncertain_parameter_sample=None, optimal_uncertain_parameter=None, optimization_trajectory=None, optimization_trajectory_objval=None, optimization_trajectory_stoch_objval=None, inner_optimization_results=None, outer_optimization_results=None, converged=False, maxiter_reached=False, message=<property object>, objective_value_tracker=None, configurations=None, budgets=None)#

class RobustConstrainedBinaryReinforceOptimizer(configs=None)[source]#

Bases: RobustBinaryReinforceOptimizer

The RobustConstrainedBinaryReinforceOptimizer is a modification from RobustBinaryReinforceOptimizer where only the Bernoulli distribution modeling the random variable is replaced with a generalized conditional Bernoulli model that inherently models budget/cost constraints.

Details of the probabilistic approach to binary optimization with budget constraints employed here can be found in [1].

References:

Ahmed Attia. “Probabilistic Approach to Black-Box Binary Optimization with Budget Constraints: Application to Sensor Placement.” arXiv preprint arXiv:2406.05830 (2024).

__init__(configs=None)[source]#

create_stochastic_optimizer()[source]#

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 RobustConstrainedBinaryReinforceOptimizerConfigs are validated. Finally, super classes validators are called.

Parameters:

configs (dict | RobustConstrainedBinaryReinforceOptimizerConfigs) – 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 RobustBinaryReinforceOptimizerConfigs.
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

register_budgets(budgets)[source]#

Set the budget (the sum of the Bernoulli random variable to condition on) The budget could be a number (integer) or set of numbers. The probability of each budget/size is recalculated. In the former case, the distribution is identical to the parent class. In the latter, the probability is calculated by conditioning on the union of all budgets.

Parameters:: budgets (int|iterable(int)) – either an integer or an iterable e.g., list of integers, defining acceptable budgets (sum of the Bernoulli random variable).
Raises:: TypeError – if the type of budgets is not acceptable.

check_registered_budgets()[source]#

Check/validate registerd budgets and their probabilities.

Returns:: the registerd budgets/sizes and the corresponding probabilities.
Raises:: TypeError if no valid budget is registered

reset_budget_constraints()[source]#: Remove any budget constraints. To add/register constraints call register_budget_constraint().

get_feasible_budgets()[source]#: Retrieve a list of all feasible budgets based on the registered constraints.

is_feasible(design)[source]#

Test if the passed design satisfies feasibility (initially budget) constraints

Parameters:: design
Returns:: bool; True if the design satisfies all constraints

solve(initial_guess=None, parameter_sample=None)[source]#: This mirrors RobustBinaryReinforceOptimizer.solve(). The only difference is that the result is transformed into an instance of RobustConstrainedBinaryReinforceOptimizerResults for consistency, with registered budgets added to the results object.

update_bruteforce_results(bruteforce_results=None, parameter_sample=None, saveto=None)[source]#: A wrapper around RobustBinaryReinforceOptimizer.update_bruteforce_results(). The only difference is that the num_active is set to the registered budgets here.

plot_results(results, overwrite=False, bruteforce_results=None, num_active=None, uncertain_parameter_sample=None, exhaustive_parameter_search_results=None, show_legend=True, output_dir=None, keep_plots=False, fontsize=20, line_width=2, usetex=True, show_axis_grids=True, axis_grids_alpha=(0.25, 0.4), plots_format='pdf', **kwargs)[source]#: A wrapper around RobustBinaryReinforceOptimizer.plot_results(). The only difference is that the num_active is set to the registered budgets here.

property budgets#: Return the registerd budtet sizes iterable (range/list/etc.)