lava.lib.optimization.problems

lava.lib.optimization.problems.bayesian
- lava.lib.optimization.problems.bayesian.models
- lava.lib.optimization.problems.bayesian.processes

lava.lib.optimization.problems.coefficients

digraph inheritancecb1b62d85b { bgcolor=transparent; rankdir=TB; size=""; "CoefficientTensorsMixin" [URL="../lava-lib-optimization/lava.lib.optimization.problems.html#lava.lib.optimization.problems.coefficients.CoefficientTensorsMixin",fillcolor=white,fontname="Vera Sans, DejaVu Sans, Liberation Sans, Arial, Helvetica, sans",fontsize=10,height=0.25,shape=box,style="setlinewidth(0.5),filled",target="_top"]; }

class lava.lib.optimization.problems.coefficients.CoefficientTensorsMixin(*coefficients)

Bases: object

property coefficients

evaluate(x)

Evaluate the polynomial at the given point.

Return type:: ndarray

get_coefficient(order)

property max_degree: Maximum order among the coefficients’ ranks.

lava.lib.optimization.problems.constraints

digraph inheritancec2b33f5f05 { bgcolor=transparent; rankdir=TB; size=""; "ArithmeticConstraints" [URL="../lava-lib-optimization/lava.lib.optimization.problems.html#lava.lib.optimization.problems.constraints.ArithmeticConstraints",fillcolor=white,fontname="Vera Sans, DejaVu Sans, Liberation Sans, Arial, Helvetica, sans",fontsize=10,height=0.25,shape=box,style="setlinewidth(0.5),filled",target="_top"]; "CoefficientTensorsMixin" [URL="../lava-lib-optimization/lava.lib.optimization.problems.html#lava.lib.optimization.problems.coefficients.CoefficientTensorsMixin",fillcolor=white,fontname="Vera Sans, DejaVu Sans, Liberation Sans, Arial, Helvetica, sans",fontsize=10,height=0.25,shape=box,style="setlinewidth(0.5),filled",target="_top"]; "Constraints" [URL="../lava-lib-optimization/lava.lib.optimization.problems.html#lava.lib.optimization.problems.constraints.Constraints",fillcolor=white,fontname="Vera Sans, DejaVu Sans, Liberation Sans, Arial, Helvetica, sans",fontsize=10,height=0.25,shape=box,style="setlinewidth(0.5),filled",target="_top",tooltip="A set of constraints, including both discrete and arithmetic."]; "DiscreteConstraints" [URL="../lava-lib-optimization/lava.lib.optimization.problems.html#lava.lib.optimization.problems.constraints.DiscreteConstraints",fillcolor=white,fontname="Vera Sans, DejaVu Sans, Liberation Sans, Arial, Helvetica, sans",fontsize=10,height=0.25,shape=box,style="setlinewidth(0.5),filled",target="_top",tooltip="Set of constraints involving only discrete variables."]; "EqualityConstraints" [URL="../lava-lib-optimization/lava.lib.optimization.problems.html#lava.lib.optimization.problems.constraints.EqualityConstraints",fillcolor=white,fontname="Vera Sans, DejaVu Sans, Liberation Sans, Arial, Helvetica, sans",fontsize=10,height=0.25,shape=box,style="setlinewidth(0.5),filled",target="_top",tooltip="List of equality constraints defined by tensor coefficients."]; "CoefficientTensorsMixin" -> "EqualityConstraints" [arrowsize=0.5,style="setlinewidth(0.5)"]; "InequalityConstraints" [URL="../lava-lib-optimization/lava.lib.optimization.problems.html#lava.lib.optimization.problems.constraints.InequalityConstraints",fillcolor=white,fontname="Vera Sans, DejaVu Sans, Liberation Sans, Arial, Helvetica, sans",fontsize=10,height=0.25,shape=box,style="setlinewidth(0.5),filled",target="_top",tooltip="List of inequality constraints defined by tensor coefficients."]; "CoefficientTensorsMixin" -> "InequalityConstraints" [arrowsize=0.5,style="setlinewidth(0.5)"]; }

class lava.lib.optimization.problems.constraints.ArithmeticConstraints(eq=None, ineq=None)

Bases: object

property equality: EqualityConstraints object defined by tensor coefficients.

property inequality: InequalityConstraints object defined by tensor coefficients.

class lava.lib.optimization.problems.constraints.Constraints

Bases: object

A set of constraints, including both discrete and arithmetic.

Discrete constraints can be of any arity and are defined by a tuple containing variable subsets and a relation tensor. Arithmetic constraints include equality and inequality constraints and are defined by a series of tensors defining the coefficients of scalar function of the variable vectors.

property arithmetic: Constraints defined via an arithmetic relation.

property discrete: Constraints over discrete variables only, defined via a relation.

class lava.lib.optimization.problems.constraints.DiscreteConstraints(constraints)

Bases: object

Set of constraints involving only discrete variables.

Parameters:

constraints (List of constraints each as an n-tuple where the) –
the (first n-1 elements are the variables related by the n-th element of) –
variables (tuple. The n-th element is a tensor indicating what values of the) –
allowed. (are simultaneously) –
variables) (Although initially intended for tensors of rank=2 (binary) –

:param : :param other ranks simply mean relations between any number of variables and: :param thus are allowed. In this way: :param tensor’s rank corresponds to the Arity of the: :param constraint they define.:

property constraints: User specified constraints.

get_scope_and_relations(constraints)

Extract relations and variable subsets from constraints.

Parameters:

constraints (List of constraints each as an n-tuple where the first) –
the (n-1 elements are the variables related by the n-th element of) –
details. (tuple (a tensor). See class docstring for more) –

property relations: List of tensors specifying discrete constraint over var subsets.

set_relations_var_subsets(constraints)

Set relations and variable subsets from constraints.

Parameters:

constraints (List of constraints each as an n-tuple where the first) –
the (n-1 elements are the variables related by the n-th element of) –
details. (tuple (a tensor). See class docstring for more) –

validate_subsets_and_relations_match(subsets, relations)

Verify relation size match domain sizes of affected variables.

Parameters:

subsets (List of variable subsets affected by the corresponding) –
relation. –
relations (List of tensors specifying discrete constraint over var) –
subsets. –

property var_subsets: List of variable subsets affected by the corresponding relation.

class lava.lib.optimization.problems.constraints.EqualityConstraints(*coefficients)

Bases: CoefficientTensorsMixin

List of equality constraints defined by tensor coefficients.

We consider generalized constraints of arbitrary degree:

h(x) = 0

where the terms of h(x) have the form:

g(x)= \sum_{ijk...} \epsilon_{ijk...} \cdot x_i \cdot x_j \cdot x_k \cdot ...

Parameters:: coefficients (tensor) – coefficients defining the constraints.

class lava.lib.optimization.problems.constraints.InequalityConstraints(*coefficients)

Bases: CoefficientTensorsMixin

List of inequality constraints defined by tensor coefficients.

We consider generalized constraints of arbitrary degree:

g(x) \leq 0

where the terms of g(x) have the form:

\sum_{ijk...} \epsilon_{ijk...} \cdot x_i \cdot x_j \cdot x_k \cdot ...

Parameters:: coefficients (tensor) – coefficients defining the constraints.

lava.lib.optimization.problems.cost

digraph inheritancec9dad303dd { bgcolor=transparent; rankdir=TB; size=""; "CoefficientTensorsMixin" [URL="../lava-lib-optimization/lava.lib.optimization.problems.html#lava.lib.optimization.problems.coefficients.CoefficientTensorsMixin",fillcolor=white,fontname="Vera Sans, DejaVu Sans, Liberation Sans, Arial, Helvetica, sans",fontsize=10,height=0.25,shape=box,style="setlinewidth(0.5),filled",target="_top"]; "Cost" [URL="../lava-lib-optimization/lava.lib.optimization.problems.html#lava.lib.optimization.problems.cost.Cost",fillcolor=white,fontname="Vera Sans, DejaVu Sans, Liberation Sans, Arial, Helvetica, sans",fontsize=10,height=0.25,shape=box,style="setlinewidth(0.5),filled",target="_top",tooltip="Cost function of an optimization problem."]; "CoefficientTensorsMixin" -> "Cost" [arrowsize=0.5,style="setlinewidth(0.5)"]; }

class lava.lib.optimization.problems.cost.Cost(*coefficients, augmented_terms=None)

Bases: CoefficientTensorsMixin

Cost function of an optimization problem.

Parameters:

coefficients (Union[List, _SupportsArray[dtype[Any]], _NestedSequence[_SupportsArray[dtype[Any]]], bool, int, float, complex, str, bytes, _NestedSequence[Union[bool, int, float, complex, str, bytes]]]) – cost tensor coefficients.
augmented_terms (Optional[Tuple[Union[List, _SupportsArray[dtype[Any]], _NestedSequence[_SupportsArray[dtype[Any]]], bool, int, float, complex, str, bytes, _NestedSequence[Union[bool, int, float, complex, str, bytes]]], ...]]) – Tuple of terms not originally defined in the cost

function, e.g. a regularization term or those incorporating constraints into the cost. Tuple elements have the same type as coefficients.

__call__(x)

Evaluate the cost at the given solution.

Return type:: ndarray

property augmented_terms: Augmented terms present in the cost function.

property is_augmented: Whether augmented terms are present in the cost function.

lava.lib.optimization.problems.problems

digraph inheritance3cd82b3b54 { bgcolor=transparent; rankdir=TB; size=""; "ABC" [fillcolor=white,fontname="Vera Sans, DejaVu Sans, Liberation Sans, Arial, Helvetica, sans",fontsize=10,height=0.25,shape=box,style="setlinewidth(0.5),filled",tooltip="Helper class that provides a standard way to create an ABC using"]; "CSP" [URL="../lava-lib-optimization/lava.lib.optimization.problems.html#lava.lib.optimization.problems.problems.CSP",fillcolor=white,fontname="Vera Sans, DejaVu Sans, Liberation Sans, Arial, Helvetica, sans",fontsize=10,height=0.25,shape=box,style="setlinewidth(0.5),filled",target="_top",tooltip="A constraint satisfaction problem."]; "OptimizationProblem" -> "CSP" [arrowsize=0.5,style="setlinewidth(0.5)"]; "ILP" [URL="../lava-lib-optimization/lava.lib.optimization.problems.html#lava.lib.optimization.problems.problems.ILP",fillcolor=white,fontname="Vera Sans, DejaVu Sans, Liberation Sans, Arial, Helvetica, sans",fontsize=10,height=0.25,shape=box,style="setlinewidth(0.5),filled",target="_top",tooltip="Class to instantiate an Integer Linear Programming (ILP) problem in the"]; "IQP" -> "ILP" [arrowsize=0.5,style="setlinewidth(0.5)"]; "IQP" [URL="../lava-lib-optimization/lava.lib.optimization.problems.html#lava.lib.optimization.problems.problems.IQP",fillcolor=white,fontname="Vera Sans, DejaVu Sans, Liberation Sans, Arial, Helvetica, sans",fontsize=10,height=0.25,shape=box,style="setlinewidth(0.5),filled",target="_top",tooltip="Class to instantiate an Integer Quadratic Programming (IQP) problem in the"]; "OptimizationProblem" -> "IQP" [arrowsize=0.5,style="setlinewidth(0.5)"]; "OptimizationProblem" [URL="../lava-lib-optimization/lava.lib.optimization.problems.html#lava.lib.optimization.problems.problems.OptimizationProblem",fillcolor=white,fontname="Vera Sans, DejaVu Sans, Liberation Sans, Arial, Helvetica, sans",fontsize=10,height=0.25,shape=box,style="setlinewidth(0.5),filled",target="_top",tooltip="Interface for any concrete optimization problem."]; "ABC" -> "OptimizationProblem" [arrowsize=0.5,style="setlinewidth(0.5)"]; "QP" [URL="../lava-lib-optimization/lava.lib.optimization.problems.html#lava.lib.optimization.problems.problems.QP",fillcolor=white,fontname="Vera Sans, DejaVu Sans, Liberation Sans, Arial, Helvetica, sans",fontsize=10,height=0.25,shape=box,style="setlinewidth(0.5),filled",target="_top",tooltip="An interface for the QP solver. Equality Constraints should be of the"]; "OptimizationProblem" -> "QP" [arrowsize=0.5,style="setlinewidth(0.5)"]; "QUBO" [URL="../lava-lib-optimization/lava.lib.optimization.problems.html#lava.lib.optimization.problems.problems.QUBO",fillcolor=white,fontname="Vera Sans, DejaVu Sans, Liberation Sans, Arial, Helvetica, sans",fontsize=10,height=0.25,shape=box,style="setlinewidth(0.5),filled",target="_top"]; "OptimizationProblem" -> "QUBO" [arrowsize=0.5,style="setlinewidth(0.5)"]; }

class lava.lib.optimization.problems.problems.CSP(domains=None, constraints=None)

Bases: OptimizationProblem

A constraint satisfaction problem.

The CSP is in usually represented by the tuple (variables, domains, constraints). However, because every variable must have a domain, the user only provides the domains and constraints.

Parameters:

domains (either a list of tuples with values that each variable can take or) –
variable. (a list of integers specifying the domain size for each) –
constraints (Discrete constraints defining mutually allowed values) –
elements (between variables. Has to be a list of n-tuples where the first n-1) –
element (are the variables related by the n-th element of the tuple. The n-th) –
simultaneously (is a tensor indicating what values of the variables are) –
allowed. –

property constraints: Specification of mutually allowed values between variables.

property cost: Constant cost function, CSPs require feasibility not minimization.

property variables: Discrete variables over which the problem is specified.

verify_solution(solution)

class lava.lib.optimization.problems.problems.ILP(c, A, b)

Bases: IQP

Class to instantiate an Integer Linear Programming (ILP) problem in the standard form as:

min c^Tx \\ Ax >= b \\ x >= 0 \\ x in Z

class lava.lib.optimization.problems.problems.IQP(H, c, A, b)

Bases: OptimizationProblem

Class to instantiate an Integer Quadratic Programming (IQP) problem in the standard form as:

min x^THx+c^Tx \\ Ax >= b \\ x >= 0 \\ x in Z

property constraints: Specification of mutually allowed values between variables.

property cost: Cost function.

evaluate_constraints(x)

Evaluate constraints at provided solution as $Ax-b$.

Return type:: ndarray

evaluate_cost(x)

Evaluate cost of provided solution.

Return type:: int

property variables: Discrete variables over which the problem is specified.

class lava.lib.optimization.problems.problems.OptimizationProblem

Bases: ABC

Interface for any concrete optimization problem.

Any optimization problem can be defined by a set of variables, cost and constraints. Although for some problems some of these elements may be absent, the user still has to specify them, e.g., defining constraints as None.

abstract property constraints: Constrains to be satisfied by mutual assignments to variables.

abstract property cost: Function to be optimized and defined over the problem variables.

abstract property variables: Variables over which the optimization problem is defined.

class lava.lib.optimization.problems.problems.QP(hessian=None, linear_offset=None, inequality_constraints_weights=None, inequality_constraints_biases=None, equality_constraints_weights=None, equality_constraints_biases=None)

Bases: OptimizationProblem

An interface for the QP solver. Equality Constraints should be of the form Ax=k. Support for inequality constraints is pending. The cost of the QP is of the form 1/2*x^t*Q*x + p^Tx. The problem has to be preconditioned with a preconditioner. The library currently supports ruiz preconditioning which is a useful preconditioner for block diagonal QPs. Other preconditioners can be added in the future. Calling the precondition_problem method preconditions the problem and modifies the matrices and vectors that constitute the problem.

hessian2-D or 1-D np.array
Quadratic term of the cost function

linear_offset1-D np.array, optional
Linear term of the cost function, defaults vector of zeros of the size of the number of variables in the QP

constraint_hyperplanes2-D or 1-D np.array, optional
Inequality constrainting hyperplanes, by default None

constraint_biases1-D np.array, optional
Ineqaulity constraints offsets, by default None

constraint_hyperplanes_eq2-D or 1-D np.array, optional
Equality constrainting hyperplanes, by default None

constraint_biases_eq1-D np.array, optional
Eqaulity constraints offsets, by default None

ValueError
ValueError exception raised if equality or inequality constraints are not properly defined. Ex: Defining A_eq while not defining k_eq and vice-versa.

property constraint_biases_eq: ndarray

property constraint_biases_ineq: ndarray

property constraint_hyperplanes_eq: ndarray

property constraint_hyperplanes_ineq: ndarray

property constraints: Constrains to be satisfied by mutual assignments to variables.

property cost: Function to be optimized and defined over the problem variables.

evaluate_constraint_violations(sol): Evalue constraint violations A_eq@x - k_eq. Returns a vector of all constraint violations

evaluate_cost(sol): Evaluates the quadratic cost 1/2x^TQx + p^Tx. Returns a scalar cost.

property hessian: ndarray

property linear_offset: ndarray

property num_variables: int

property postconditioner: ndarray

precondition_problem(iterations=5, type='ruiz'): Used to precondition problems before they can be used in the solver. Only ruiz preconditioning supported at the moment. Other preconditioners can be added by following the example of the Ruiz preconditioner.

property variables: Variables over which the optimization problem is defined.

class lava.lib.optimization.problems.problems.QUBO(q)

Bases: OptimizationProblem

property constraints: As an unconstrained problem, QUBO constraints are None.

property cost: Quadratic cost to be minimized.

evaluate_cost(solution)

Return type:: int

property num_variables

validate_input(q)

Validate that cost coefficient is a square, symmetric, int matrix.

Parameters:: q (Quadratic coefficient of the cost function.) –

property variables: Binary variables of the QUBO problem.

verify_solution(solution)

lava.lib.optimization.problems.variables

digraph inheritance0f165fcdb5 { bgcolor=transparent; rankdir=TB; size=""; "ContinuousVariables" [URL="../lava-lib-optimization/lava.lib.optimization.problems.html#lava.lib.optimization.problems.variables.ContinuousVariables",fillcolor=white,fontname="Vera Sans, DejaVu Sans, Liberation Sans, Arial, Helvetica, sans",fontsize=10,height=0.25,shape=box,style="setlinewidth(0.5),filled",target="_top",tooltip="Set of variables to which any values in specified ranges can be assigned."]; "DiscreteVariables" [URL="../lava-lib-optimization/lava.lib.optimization.problems.html#lava.lib.optimization.problems.variables.DiscreteVariables",fillcolor=white,fontname="Vera Sans, DejaVu Sans, Liberation Sans, Arial, Helvetica, sans",fontsize=10,height=0.25,shape=box,style="setlinewidth(0.5),filled",target="_top",tooltip="A set of variables which can only be assigned discrete values."]; "Variable" [URL="../lava-lib-optimization/lava.lib.optimization.problems.html#lava.lib.optimization.problems.variables.Variable",fillcolor=white,fontname="Vera Sans, DejaVu Sans, Liberation Sans, Arial, Helvetica, sans",fontsize=10,height=0.25,shape=box,style="setlinewidth(0.5),filled",target="_top",tooltip="An entity to which a value can be assigned."]; "Variables" [URL="../lava-lib-optimization/lava.lib.optimization.problems.html#lava.lib.optimization.problems.variables.Variables",fillcolor=white,fontname="Vera Sans, DejaVu Sans, Liberation Sans, Arial, Helvetica, sans",fontsize=10,height=0.25,shape=box,style="setlinewidth(0.5),filled",target="_top"]; }

class lava.lib.optimization.problems.variables.ContinuousVariables(num_variables=None, bounds=None)

Bases: object

Set of variables to which any values in specified ranges can be assigned.

Parameters:

bounds (List of 2-tuples defining the range from which each corresponding) –
values. (variable (by index) can take) –

property bounds: Limit values defining the ranges of allowed values for variables.

property num_variables: Number of variables in this set.

property variable_set: List of continuous variables as instances of the Variable class.

class lava.lib.optimization.problems.variables.DiscreteVariables(domains=None)

Bases: object

A set of variables which can only be assigned discrete values.

Parameters:

domains (List of tuples with values that each variable can take or List) –
variable. (of domain sizes for each corresponding (by index)) –

property domain_sizes: Number of elements on the domain of each discrete variable.

property domains: List of tuples containing the values that each variable can take.

property num_variables: Number of variables in this set.

property variable_set: List of discrete variables each an instance of the Variable class.

class lava.lib.optimization.problems.variables.Variable(name=None)

Bases: object

An entity to which a value can be assigned.

Parameters:: name (Optional name for the variable.) –

property value: Variable’s current value.

class lava.lib.optimization.problems.variables.Variables

Bases: object

property continuous

property discrete