5. Model Formulation#

A combinatorial optimization problem comprises decision variables, objective functions, and constraints. In β€œ2. Creating Decision Variables,” β€œ3. Polynomials and Objective Functions,” and β€œ4. Constructing Constraints,” we explained that you can create decision variables using VariableGenerator. At the same time, you can construct objective functions and constraints using Poly and Constraint.

This page describes how these can be combined and used together to express combinatorial optimization problems in program code.

See also

In addition to the Poly class, you can use instances of the coefficient matrix Matrix class as an objective function. When you construct the objective function as Matrix, you can use it in the same way described on this page.

For details on the format of the coefficient matrix, see β€œObjective Function with a Coefficient Matrix”.

5.1. Model construction#

The Amplify SDK represents combinatorial optimization problems as instances of the Model class.

For a combinatorial optimization problem with an objective function and constraints, a simple way is to add a Poly representing the objective function and a Constraint or ConstraintList defining the constraints.

from amplify import VariableGenerator, Model, equal_to, one_hot

gen = VariableGenerator()
q = gen.array("Binary", shape=(2, 3))

objective = q[0, 0] * q[0, 1] - q[0, 2]
constraint1 = equal_to(q[0, 0] + q[0, 1] - q[0, 2], 0)
constraint2 = one_hot(q[1, :])
constraint_list = constraint1 + constraint2

  • Constructing the model by adding the objective function and constraints:

>>> model = objective + constraint1
>>> print(model)
minimize:
  q_{0,0} q_{0,1} - q_{0,2}
subject to:
  q_{0,0} + q_{0,1} - q_{0,2} == 0 (weight: 1)

  • Constructing the model by adding the objective function and the constraint list:

>>> model = objective + constraint_list
>>> print(model)
minimize:
  q_{0,0} q_{0,1} - q_{0,2}
subject to:
  q_{0,0} + q_{0,1} - q_{0,2} == 0 (weight: 1),
  q_{1,0} + q_{1,1} + q_{1,2} == 1 (weight: 1)

For a combinatorial optimization problem consisting of either an objective function or constraints, you can pass a Poly (or Matrix) instance to the constructor of the Model class to represent the objective function or a Constraint or ConstraintList instance to represent the constraints.

  • Constructing a model from the objective function (Poly):

>>> model = Model(objective)
>>> print(model)
minimize:
  q_{0,0} q_{0,1} - q_{0,2}

  • Constructing a model from a single constraint object (Constraint):

>>> model = Model(constraint1)
>>> print(model)
minimize:
  0
subject to:
  q_{0,0} + q_{0,1} - q_{0,2} == 0 (weight: 1)

  • Constructing a model from multiple constraint objects (ConstraintList):

>>> model = Model(constraint_list)
>>> print(model)
minimize:
  0
subject to:
  q_{0,0} + q_{0,1} - q_{0,2} == 0 (weight: 1),
  q_{1,0} + q_{1,1} + q_{1,2} == 1 (weight: 1)

You can also add constraints (Constraint or {py:class}`~amplify.ConstraintList) after the model is constructed.

>>> model = Model(objective)
>>> print(model)
minimize:
  q_{0,0} q_{0,1} - q_{0,2}
>>> model += constraint1
>>> print(model)
minimize:
  q_{0,0} q_{0,1} - q_{0,2}
subject to:
  q_{0,0} + q_{0,1} - q_{0,2} == 0 (weight: 1)

If the model has the objective function as an instance of the polynomial Poly class, addition and subtraction of the objective function are also possible.

>>> model += q[0, 0] * q[0, 1]
>>> print(model)
minimize:
  2 q_{0,0} q_{0,1} - q_{0,2}
subject to:
  q_{0,0} + q_{0,1} - q_{0,2} == 0 (weight: 1)

>>> model -= q[0, 0]
>>> print(model)
minimize:
  2 q_{0,0} q_{0,1} - q_{0,0} - q_{0,2}
subject to:
  q_{0,0} + q_{0,1} - q_{0,2} == 0 (weight: 1)

5.2. Model attributes#

The objective property allows you to retrieve the objective function of the Model class.

from amplify import VariableGenerator, equal_to

gen = VariableGenerator()
q = gen.array("Binary", 2, 3)

objective = q[0,0] * q[0,1] - q[0,2]
constraint = equal_to(q[0,0] + q[0,1] - q[0,2], 0)
model = objective + constraint

>>> print(model.objective)
q_{0,0} q_{0,1} - q_{0,2}

The constraints property allows the user to retrieve the constraints the Model class holds. This property returns an instance of the ConstraintList class.

>>> print(model.constraints)
[q_{0,0} + q_{0,1} - q_{0,2} == 0 (weight: 1)]

Note

Note that the Model stores the objective function and constraints without copying them. Therefore, changing the objective function or constraints in the model will also change the variables before model construction.

model = Model(objective)
model += q[0, 0]
assert model.objective == objective

5.3. Changing the constraint weight in the model#

After the model is constructed, you may want to change the weight of the constraint included in the model.

Note

See β€œPenalty function weight” for information on adjusting the weights of constraints.

In the following example, the weight of a constraint is doubled.

>>> print(model)
minimize:
  q_{0,0} q_{0,1} - q_{0,2}
subject to:
  q_{0,0} + q_{0,1} - q_{0,2} == 0 (weight: 1)
>>> model.constraints[0] *= 2
>>> print(model)
minimize:
  q_{0,0} q_{0,1} - q_{0,2}
subject to:
  q_{0,0} + q_{0,1} - q_{0,2} == 0 (weight: 2)