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. The model converts the matrix to a Poly.

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 two things. Add a Poly that represents the objective function and a Constraint or ConstraintList that defines 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 with either an objective function or constraints, you can pass a single instance to the constructor of the Model class. Pass a Poly (or Matrix) instance to represent the objective function. Pass 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 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)

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

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. A Matrix is the exception, because the model converts it to a Poly.

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)