Brute Force Minimization

Types

The brute-force minimization functions in Forge rely on custom types for problem specification, constraints, and results.

class qcware.types.optimization.PolynomialObjective(polynomial: Dict[Tuple[int, ], int], num_boolean_variables: int, variable_name_mapping: Optional[Dict[int, str]] = None, validate_types: bool = True)

Integer-valued polynomial of boolean variables with int coefficients.

Objects of this class specify polynomials of some number of boolean variables with integer coefficients. When we use the term “boolean”, we mean that variables take on the values 0 and 1. These are pseudo-boolean functions.

Objects of this class are meant to be treated as objective functions for optimization. They do not know about constraints. Constraints can be specified separately using a Constraints object.

Polynomials are specified with a dict that specifies the coefficients for the polynomial. For example, suppose that we are interested in the polynomial of three boolean variables defined by

p(x, y, z) = 12 x - 2 y z + x y z - 50

The three variables should be associated with the integers 0, 1, and 2. We choose the association x ~ 0, y ~ 1, and z ~ 2.

There are four terms in p. Consider the term -2yz. We can specify this term by matching the tuple (1, 2), which represents yz, with the coefficient -2. This can be encoded with an entry in a dict (1, 2): -2. Overall, p can be defined by

{ (): -50, (0,): 12, (1, 2): -2, (0, 1, 2): -50 }

.

Note that this object does not automatically simplify a given PolynomialObjective. For example, {(0, 1): 2, (1, 0): 3} is the same thing as {(0, 1): 5}. However, we do provide a simplified method returns a version of the same polynomial with simplifications performed.

The number of variables must be specified explicitly, even if it seems obvious how many variables there are. The reason for this is to allow for the possibility that there are more variables than appear explicitly in the polynomial. For example, the polynomial p(a, b) = 12 b might be mistaken for q(b) = 12 b.

polynomial

The polynomial is specified by a dict in the standard way. We only use tuples of int as keys and the range of ints must be from 0 to num_boolean_variables - 1. Values for the dict must be type int. This is because we are only treating integer-coefficient polynomials.

Type

Dict[Tuple[int, ..], int]

variables

Set of ints representing variables.

Type

Set[int]

num_boolean_variables

The number of variables for the polynomial. This number can be larger than the actual number of variables that appear in pubo.

Type

int

degree

The degree of the polynomial. This is not the mathematically correct degree. It is instead the length of the longest key in the pubo dict or -inf in the case when the pubo dict is {}. For example, the PolynomialObjective {(1,): 12, (0, 1): 0} has mathematical degree 1 but the attribute degree is 2.

Type

Union[int, float]

clone()

Make a copy of this PolynomialObjective.

pretty_str()

Make a string that presents the polynomial algebraically.

The names of variables can be controlled with the attribute variable_name_mapping.

Adapted from qubovert–thanks to Joseph T. Iosue.

simplified(preserve_num_variables=True) → qcware.types.optimization.problem_spec.objective.PolynomialObjective

Get a simplified copy of the PolynomialObjective.

Parameters
  • preserve_num_variables – If True, the resulting PolynomialObjective will

  • the same number of variables stored as the original PolynomialObjective. (have) –

  • Otherwise

  • will match the actual number of variables (num_boolean_variables) –

  • appear in the polynomial with nonzero coefficients. (that) –

classmethod validate_type(v)

This validator only confirms that we are dealing with an object of the expected type. This does not validate internal consistency of attributes for the Objective function because that is done by __init__.

class qcware.types.optimization.Constraints(constraints: Dict[qcware.types.optimization.predicate.Predicate, List[qcware.types.optimization.problem_spec.objective.PolynomialObjective]], num_boolean_variables: int, validate_types: bool = True)

Specification of constraints on boolean variables.

An object of class Constraints does not have information about the objective function on which the constraints are applied. It is simply a collection of constraints which can then be imposed on something.

To specify constraints, we use a “constraint dict”. The format of this dict is

{type of constraint: list of constraints of that type}.

The “type of constraint” means a Predicate object. The list of constraints of a given Predicate are a list of `PolynomialObjective`s.

This can be understood fairly easily by example. Suppose that f is an PolynomialObjective with 3 boolean variables. We take

f(x, y, z) = (x + y + z - 1)^2

which is minimized when exactly one of the three variables is 1.

If we want to impose the condition that either x or z is zero, we can roughly use the constraint dict

{Predicate.ZERO: [p]}

where p is the PolynomialObjective representing the function

p(x, y, z) = OR(x, z) = x + z - x z

(To build this, see the documentation for PolynomialObjective.) If we additionally want to add the constraint that the sum of the three variables is at least 2, we can make our dict

{Predicate.ZERO: [p], Predicate.POSITIVE: [q]}

where q is a PolynomialObjective representing q(x, y, z) = x + y + z - 1. The reason that we are using [p] and [q] instead of just p and q is that we can add additional constraints of those types in this fashion by adding more entries to the lists.

constraint_exists(order: Optional[Union[int, Iterable[int]]] = None, predicate: Optional[qcware.types.optimization.predicate.Predicate] = None)

Return True iff a constraint exists with given order or predicate.

order can be an int or an iterable of ints. predicate is a Predicate object.

If order and predicate are both None, this function returns True iff any constraint exists.

get_constraint_group(predicate: qcware.types.optimization.predicate.Predicate, order: Optional[Union[int, Iterable[int]]] = None)

Iterate over constraints with specified predicate and order.

If order is not specified, all orders are generated.

num_constraints(predicate: Optional[qcware.types.optimization.predicate.Predicate] = None)

Return the number of constraints.

If a predicate is specified, only return the number of constraints for that predicate.

class qcware.types.optimization.BruteOptimizeResult(*, value: int = None, arguments: List[str] = [], solution_exists: bool = True)

Return type for brute force maximization and minimization.

When solution_exists == False, we must have value is None and arguments == [].

int_argument() → List[List[int]]

Convert arguments to a list of list of ints.

Functions

qcware.optimization.brute_force_minimize(objective: qcware.types.optimization.problem_spec.objective.PolynomialObjective, constraints: Optional[qcware.types.optimization.problem_spec.constraints.Constraints] = None, backend: str = 'qcware/cpu')

Minimize given objective polynomial subject to constraints.

Arguments:

Parameters
  • objective (types.PolynomialObjective) – The integer-coefficient polynomial to be evaluated should be specified by a PolynomialObjective. See documentation for PolynomialObjective for more information. Note that variables are boolean in the sense that their values are 0 and 1.

  • constraints (Optional[types.Constraints]) – Optional constraints are specified with an object of class Constraints. See its documentation for further information., defaults to None

  • backend (str) – String specifying the backend. Currently only [qcware/cpu] available, defaults to qcware/cpu

Returns

BruteOptimizeResult object specifying the minimum value of the objective function (that does not violate a constraint) as well as the variables that attain this value.

Return type

types.BruteOptimizeResult