ommx.v1

Submodules

• ommx.v1.annotation
• ommx.v1.constraint_hints_pb2
• ommx.v1.constraint_pb2
• ommx.v1.decision_variables_pb2
• ommx.v1.function_pb2
• ommx.v1.instance_pb2
• ommx.v1.linear_pb2
• ommx.v1.one_hot_pb2
• ommx.v1.parametric_instance_pb2
• ommx.v1.polynomial_pb2
• ommx.v1.quadratic_pb2
• ommx.v1.sample_set_pb2
• ommx.v1.solution_pb2
• ommx.v1.sos1_pb2

Attributes

ToSamples	Type alias for convertible types to Samples.
ToState	Type alias for convertible types to State.

Classes

Constraint	Constraints
DecisionVariable	Idiomatic wrapper of ommx.v1.DecisionVariable protobuf message.
Function	Helper class that provides a standard way to create an ABC using
Instance	Idiomatic wrapper of ommx.v1.Instance protobuf message.
Linear	Modeler API for linear function
Parameter	Idiomatic wrapper of ommx.v1.Parameter protobuf message.
ParametricInstance	Idiomatic wrapper of ommx.v1.ParametricInstance protobuf message.
Polynomial	Helper class that provides a standard way to create an ABC using
Quadratic	Helper class that provides a standard way to create an ABC using
SampleSet	The output of sampling-based optimization algorithms, e.g. simulated annealing (SA).
SampledValues
Solution	Idiomatic wrapper of ommx.v1.Solution protobuf message.

Package Contents

class ommx.v1.Constraint(*, function: int | float | DecisionVariable | Linear | Quadratic | Polynomial | Function, equality: constraint_pb2.Equality.ValueType, id: int | None = None, name: str | None = None, description: str | None = None, subscripts: list[int] | None = None, parameters: dict[str, str] | None = None)

Constraints

Examples

>>> x = DecisionVariable.integer(1)
>>> y = DecisionVariable.integer(2)
>>> x + y == 1
Constraint(Function(x1 + x2 - 1) == 0)

To set the name or other attributes, use methods like :py:meth:`add_name`.

>>> (x + y <= 5).add_name("constraint 1")
Constraint(Function(x1 + x2 - 5) <= 0)

add_description(description: str) → Constraint

add_name(name: str) → Constraint

add_parameters(parameters: dict[str, str]) → Constraint

add_subscripts(subscripts: list[int]) → Constraint

static from_bytes(data: bytes) → Constraint

static from_raw(raw: constraint_pb2.Constraint) → Constraint

set_id(id: int) → Constraint

Overwrite the constraint ID.

to_bytes() → bytes

EQUAL_TO_ZERO

LESS_THAN_OR_EQUAL_TO_ZERO

property description: str | None

property equality: constraint_pb2.Equality.ValueType

property function: Function

property id: int

property name: str | None

property parameters: dict[str, str]

raw: constraint_pb2.Constraint

property subscripts: list[int]

class ommx.v1.DecisionVariable

Idiomatic wrapper of ommx.v1.DecisionVariable protobuf message.

Note that this object overloads == for creating a constraint, not for equality comparison for better integration to mathematical programming.

>>> x = DecisionVariable.integer(1)
>>> x == 1
Constraint(...)

To compare two objects, use equals_to() method.

>>> y = DecisionVariable.integer(2)
>>> x.equals_to(y)
False

static binary(id: int, *, name: str | None = None, subscripts: list[int] | None = None, parameters: dict[str, str] | None = None, description: str | None = None) → DecisionVariable

static continuous(id: int, *, lower: float = float('-inf'), upper: float = float('inf'), name: str | None = None, subscripts: list[int] | None = None, parameters: dict[str, str] | None = None, description: str | None = None) → DecisionVariable

equals_to(other: DecisionVariable) → bool

Alternative to == operator to compare two decision variables.

static from_bytes(data: bytes) → DecisionVariable

static integer(id: int, *, lower: float = float('-inf'), upper: float = float('inf'), name: str | None = None, subscripts: list[int] | None = None, parameters: dict[str, str] | None = None, description: str | None = None) → DecisionVariable

static of_type(kind: Kind, id: int, *, lower: float, upper: float, name: str | None = None, subscripts: list[int] | None = None, parameters: dict[str, str] | None = None, description: str | None = None) → DecisionVariable

static semi_continuous(id: int, *, lower: float = float('-inf'), upper: float = float('inf'), name: str | None = None, subscripts: list[int] | None = None, parameters: dict[str, str] | None = None, description: str | None = None) → DecisionVariable

static semi_integer(id: int, *, lower: float = float('-inf'), upper: float = float('inf'), name: str | None = None, subscripts: list[int] | None = None, parameters: dict[str, str] | None = None, description: str | None = None) → DecisionVariable

to_bytes() → bytes

BINARY

CONTINUOUS

INTEGER

Kind

SEMI_CONTINUOUS

SEMI_INTEGER

property bound: decision_variables_pb2.Bound

property description: str

property id: int

property kind: Kind

property name: str

property parameters: dict[str, str]

raw: decision_variables_pb2.DecisionVariable

property subscripts: list[int]

class ommx.v1.Function(inner: int | float | DecisionVariable | Linear | Quadratic | Polynomial | function_pb2.Function)

Helper class that provides a standard way to create an ABC using inheritance.

almost_equal(other: Function, *, atol: float = 1e-10) → bool

Compare two functions have almost equal coefficients as a polynomial

content_factor() → float

For given polynomial \(f(x)\), get the minimal positive factor \(a\) which makes all coefficient of \(a f(x)\) integer. See also https://en.wikipedia.org/wiki/Primitive_part_and_content

Examples

\(\frac{1}{3} x_0 + \frac{3}{2} x_1\) can be multiplied by 6 to make all coefficients integer.

>>> x = [DecisionVariable.integer(i) for i in range(2)]
>>> f = Function((1.0/3.0)*x[0] + (3.0/2.0)*x[1])
>>> a = f.content_factor()
>>> (a, a*f)
(6.0, Function(2*x0 + 9*x1))

This works even for non-rational numbers like \(\pi\) because 64-bit float is actually rational.

>>> import math
>>> f = Function(math.pi*x[0] + 3*math.pi*x[1])
>>> a = f.content_factor()
>>> (a, a*f)
(0.3183098861837907, Function(x0 + 3*x1))

But this returns very large number if there is no multiplier:

>>> f = Function(math.pi*x[0] + math.e*x[1])
>>> a = f.content_factor()
>>> (a, a*f)
(3122347504612692.0, Function(9809143982445656*x0 + 8487420483923125*x1))

In practice, you must check if the multiplier is enough small.

evaluate(state: ToState) → tuple[float, set]

Evaluate the function with the given state.

Examples

Evaluate `2 x1 x2 + 3 x2 x3 + 1` with `x1 = 3, x2 = 4, x3 = 5`

>>> x1 = DecisionVariable.integer(1)
>>> x2 = DecisionVariable.integer(2)
>>> x3 = DecisionVariable.integer(3)
>>> f = Function(2*x1*x2 + 3*x2*x3 + 1)
>>> f
Function(2*x1*x2 + 3*x2*x3 + 1)

>>> f.evaluate({1: 3, 2: 4, 3: 5})
(85.0, {1, 2, 3})

Missing ID raises an error
>>> f.evaluate({1: 3})
Traceback (most recent call last):
...
RuntimeError: Variable id (2) is not found in the solution

static from_bytes(data: bytes) → Function

partial_evaluate(state: ToState) → tuple[Function, set]

Partially evaluate the function with the given state.

Examples

Evaluate `2 x1 x2 + 3 x2 x3 + 1` with `x1 = 3`, yielding `3 x2 x3 + 6 x2 + 1`

>>> x1 = DecisionVariable.integer(1)
>>> x2 = DecisionVariable.integer(2)
>>> x3 = DecisionVariable.integer(3)
>>> f = Function(2*x1*x2 + 3*x2*x3 + 1)
>>> f
Function(2*x1*x2 + 3*x2*x3 + 1)

>>> f.partial_evaluate({1: 3})
(Function(3*x2*x3 + 6*x2 + 1), {1})

to_bytes() → bytes

used_decision_variable_ids() → set[int]

Get the IDs of decision variables used in the function.

raw: function_pb2.Function

property terms: dict[tuple[int, Ellipsis], float]

class ommx.v1.Instance

Idiomatic wrapper of ommx.v1.Instance protobuf message.

Note that this class also contains annotations like title which are not contained in protobuf message but stored in OMMX artifact. These annotations are loaded from annotations while reading from OMMX artifact.

Examples

Create an instance for KnapSack Problem

>>> from ommx.v1 import Instance, DecisionVariable

Profit and weight of items

>>> p = [10, 13, 18, 31, 7, 15]
>>> w = [11, 15, 20, 35, 10, 33]

Decision variables

>>> x = [DecisionVariable.binary(i) for i in range(6)]

Objective and constraint

>>> objective = sum(p[i] * x[i] for i in range(6))
>>> constraint = sum(w[i] * x[i] for i in range(6)) <= 47

Compose as an instance

>>> instance = Instance.from_components(
...     decision_variables=x,
...     objective=objective,
...     constraints=[constraint],
...     sense=Instance.MAXIMIZE,
... )

add_integer_slack_to_inequality(constraint_id: int, slack_upper_bound: int) → float | None

Convert inequality \(f(x) \leq 0\) to inequality \(f(x) + b s \leq 0\) with an integer slack variable s.

• This should be used when convert_inequality_to_equality_with_integer_slack() is not applicable

• The bound of \(s\) will be [0, slack_upper_bound], and the coefficients \(b\) are determined from the lower bound of \(f(x)\).

• Since the slack variable is integer, the yielded inequality has residual error \(\min_s f(x) + b s\) at most \(b\). And thus \(b\) is returned to use scaling the penalty weight or other things.

  • Larger slack_upper_bound (i.e. fined-grained slack) yields smaller b, and thus smaller the residual error. But it needs more bits for the slack variable, and thus the problem size becomes larger.

• Since this method evaluates the bound of \(f(x)\), we may find that:

  • The bound \([l, u]\) is strictly positive, i.e. \(l \gt 0\). This means the instance is infeasible because this constraint never be satisfied. In this case, an error is raised.

  • The bound \([l, u]\) is always negative, i.e. \(u \leq 0\). This means this constraint is trivially satisfied. In this case, the constraint is moved to removed_constraints, and this method returns without introducing slack variable or raising an error.

Returns:

The coefficient \(b\) of the slack variable. If the constraint is trivially satisfied, this returns None.

Examples

Let’s consider a simple inequality constraint \(x_0 + 2x_1 \leq 4\).

>>> from ommx.v1 import Instance, DecisionVariable
>>> x = [
...     DecisionVariable.integer(i, lower=0, upper=3, name="x", subscripts=[i])
...     for i in range(3)
... ]
>>> instance = Instance.from_components(
...     decision_variables=x,
...     objective=sum(x),
...     constraints=[
...         (x[0] + 2*x[1] <= 4).set_id(0)   # Set ID manually to use after
...     ],
...     sense=Instance.MAXIMIZE,
... )
>>> instance.get_constraints()[0]
Constraint(Function(x0 + 2*x1 - 4) <= 0)

Introduce an integer slack variable \(s \in [0, 2]\)

>>> b = instance.add_integer_slack_to_inequality(
...     constraint_id=0,
...     slack_upper_bound=2
... )
>>> b, instance.get_constraints()[0]
(2.0, Constraint(Function(x0 + 2*x1 + 2*x3 - 4) <= 0))

The slack variable is added to the decision variables with name ommx.slack and the constraint ID is stored in subscripts.

>>> instance.decision_variables[["kind", "lower", "upper", "name", "subscripts"]]  
       kind  lower  upper        name subscripts
id
0   integer    0.0    3.0           x        [0]
1   integer    0.0    3.0           x        [1]
2   integer    0.0    3.0           x        [2]
3   integer    0.0    2.0  ommx.slack        [0]

In this case, the slack variable only take \(s = \{ 0, 1, 2 \}\), and thus the residual error is not disappear for \(x_0 = x_1 = 1\) case \(f(x) + b \cdot x = 1 + 2 \cdot 1 + 2 \cdot s - 4 = 2s - 1\).

add_user_annotation(key: str, value: str, *, annotation_namespace: str = 'org.ommx.user.')

Add a user annotation to the instance.

Examples

>>> instance = Instance.empty()
>>> instance.add_user_annotation("author", "Alice")
>>> instance.get_user_annotations()
{'author': 'Alice'}
>>> instance.annotations
{'org.ommx.user.author': 'Alice'}

as_maximization_problem() → bool

Convert the instance to a maximization problem.

If the instance is already a maximization problem, this does nothing.

Returns:

True if the instance is converted, False if already a maximization problem.

Examples

>>> from ommx.v1 import Instance, DecisionVariable
>>> x = [DecisionVariable.binary(i) for i in range(3)]
>>> instance = Instance.from_components(
...     decision_variables=x,
...     objective=sum(x),
...     constraints=[sum(x) == 1],
...     sense=Instance.MINIMIZE,
... )
>>> instance.sense == Instance.MINIMIZE
True
>>> instance.objective
Function(x0 + x1 + x2)

Convert to a maximization problem

>>> instance.as_maximization_problem()
True
>>> instance.sense == Instance.MAXIMIZE
True
>>> instance.objective
Function(-x0 - x1 - x2)

If the instance is already a maximization problem, this does nothing

>>> instance.as_maximization_problem()
False
>>> instance.sense == Instance.MAXIMIZE
True
>>> instance.objective
Function(-x0 - x1 - x2)

as_minimization_problem() → bool

Convert the instance to a minimization problem.

If the instance is already a minimization problem, this does nothing.

Returns:

True if the instance is converted, False if already a minimization problem.

Examples

>>> from ommx.v1 import Instance, DecisionVariable
>>> x = [DecisionVariable.binary(i) for i in range(3)]
>>> instance = Instance.from_components(
...     decision_variables=x,
...     objective=sum(x),
...     constraints=[sum(x) == 1],
...     sense=Instance.MAXIMIZE,
... )
>>> instance.sense == Instance.MAXIMIZE
True
>>> instance.objective
Function(x0 + x1 + x2)

Convert to a minimization problem

>>> instance.as_minimization_problem()
True
>>> instance.sense == Instance.MINIMIZE
True
>>> instance.objective
Function(-x0 - x1 - x2)

If the instance is already a minimization problem, this does nothing

>>> instance.as_minimization_problem()
False
>>> instance.sense == Instance.MINIMIZE
True
>>> instance.objective
Function(-x0 - x1 - x2)

as_parametric_instance() → ParametricInstance

Convert the instance to a ParametricInstance.

as_pubo_format() → dict[tuple[int, Ellipsis], float]

Convert unconstrained polynomial instance to simple PUBO format.

This method is designed for better composability rather than easy-to-use. This does not execute any conversion of the instance, only translates the data format.

as_qubo_format() → tuple[dict[tuple[int, int], float], float]

Convert unconstrained quadratic instance to PyQUBO-style format.

Note

This is a single-purpose method to only convert the format, not to execute any conversion of the instance. Use to_qubo() driver for the full QUBO conversion.

convert_inequality_to_equality_with_integer_slack(constraint_id: int, max_integer_range: int)

Convert an inequality constraint \(f(x) \leq 0\) to an equality constraint \(f(x) + s/a = 0\) with an integer slack variable s.

• Since \(a\) is determined as the minimal multiplier to make the every coefficient of \(af(x)\) integer, \(a\) itself and the range of \(s\) becomes impractically large. max_integer_range limits the maximal range of \(s\), and returns error if the range exceeds it. See also content_factor().

• Since this method evaluates the bound of \(f(x)\), we may find that:

  • The bound \([l, u]\) is strictly positive, i.e. \(l \gt 0\). This means the instance is infeasible because this constraint never be satisfied. In this case, an error is raised.

  • The bound \([l, u]\) is always negative, i.e. \(u \leq 0\). This means this constraint is trivially satisfied. In this case, the constraint is moved to removed_constraints, and this method returns without introducing slack variable or raising an error.

Examples

Let’s consider a simple inequality constraint \(x_0 + 2x_1 \leq 5\).

>>> from ommx.v1 import Instance, DecisionVariable
>>> x = [
...     DecisionVariable.integer(i, lower=0, upper=3, name="x", subscripts=[i])
...     for i in range(3)
... ]
>>> instance = Instance.from_components(
...     decision_variables=x,
...     objective=sum(x),
...     constraints=[
...         (x[0] + 2*x[1] <= 5).set_id(0)   # Set ID manually to use after
...     ],
...     sense=Instance.MAXIMIZE,
... )
>>> instance.get_constraints()[0]
Constraint(Function(x0 + 2*x1 - 5) <= 0)

Introduce an integer slack variable

>>> instance.convert_inequality_to_equality_with_integer_slack(
...     constraint_id=0,
...     max_integer_range=32
... )
>>> instance.get_constraints()[0]
Constraint(Function(x0 + 2*x1 + x3 - 5) == 0)

The slack variable is added to the decision variables with name ommx.slack and the constraint ID is stored in subscripts.

>>> instance.decision_variables[["kind", "lower", "upper", "name", "subscripts"]]  
       kind  lower  upper        name subscripts
id
0   integer    0.0    3.0           x        [0]
1   integer    0.0    3.0           x        [1]
2   integer    0.0    3.0           x        [2]
3   integer    0.0    5.0  ommx.slack        [0]

static empty() → Instance

Create trivial empty instance of minimization with zero objective, no constraints, and no decision variables.

evaluate(state: ToState) → Solution

Evaluate the given State into a Solution.

This method evaluates the problem instance using the provided state (a map from decision variable IDs to their values), and returns a Solution object containing objective value, evaluated constraint values, and feasibility information.

Examples

Create a simple instance with three binary variables and evaluate a solution:

\[\begin{split}\begin{align*} \max & \space x_0 + x_1 + x_2 & \\ \text{ s.t. } & \space x_0 + x_1 \leq 1 & \\ & \space x_0, x_1, x_2 \in \{0, 1\} \end{align*}\end{split}\]

>>> from ommx.v1 import Instance, DecisionVariable
>>> x = [DecisionVariable.binary(i) for i in range(3)]
>>> instance = Instance.from_components(
...     decision_variables=x,
...     objective=sum(x),
...     constraints=[x[0] + x[1] <= 1],
...     sense=Instance.MAXIMIZE,
... )

Evaluate it with a state \(x_0 = 1, x_1 = 0, x_2 = 0\), and show the objective and constraints:

>>> solution = instance.evaluate({0: 1, 1: 0, 2: 0})
>>> solution.objective
1.0
>>> solution.constraints.dropna(axis=1, how="all")  
   equality  value used_ids subscripts
id
12      <=0    0.0   {0, 1}         []

The values of decision variables are also stored in the solution:

>>> solution.decision_variables.dropna(axis=1, how="all")  
      kind  lower  upper subscripts  value
id
0   binary    0.0    1.0         []    1.0
1   binary    0.0    1.0         []    0.0
2   binary    0.0    1.0         []    0.0

If the value is out of the range, this raises an error:

>>> instance.evaluate({0: 1, 1: 0, 2: 2})
Traceback (most recent call last):
    ...
RuntimeError: Decision variable value out of bound: ID=2, value=2, bound=[0, 1]

If some of the decision variables are not set, this raises an error:

>>> instance.evaluate({0: 1, 1: 0})
Traceback (most recent call last):
    ...
RuntimeError: Variable id (2) is not found in the solution

Irrelevant decision variables

Sometimes, the instance contains decision variables that are not used in the objective or constraints.

>>> x = [DecisionVariable.binary(i) for i in range(3)]
>>> instance = Instance.from_components(
...     decision_variables=x,
...     objective=x[0],
...     constraints=[(x[0] + x[1] == 1).set_id(0)],
...     sense=Instance.MAXIMIZE,
... )

This instance does not contain the decision variable \(x_2\) in the objective or constraints. We call such variables “irrelevant”. This is mathematically meaningless, but sometimes useful in data science application. Since the irrelevant variables cannot be determined from the instance, solvers will ignore them, and do not return their values. This function works as well for such cases:

>>> solution = instance.evaluate({0: 1, 1: 0})
>>> solution.objective
1.0
>>> solution.constraints.dropna(axis=1, how="all")  
   equality  value used_ids subscripts
id
0        =0    0.0   {0, 1}         []

The irrelevant decision variable \(x_2\) is also stored in the Solution with the value nearest to 0 within its bound. For example,

• When the bound is \([-1, 1]\) or \((-\infty, \infty)\), the value is 0

• When the bound is \([2, 5]\), the value is 2

• When the bound is \([-3, -1]\), the value is -1

>>> solution.decision_variables.dropna(axis=1, how="all")  
      kind  lower  upper subscripts  value
id
0   binary    0.0    1.0         []    1.0
1   binary    0.0    1.0         []    0.0
2   binary    0.0    1.0         []    0.0

evaluate_samples(samples: ToSamples) → SampleSet

Evaluate the instance with multiple states.

static from_bytes(data: bytes) → Instance

static from_components(*, objective: int | float | DecisionVariable | Linear | Quadratic | Polynomial | function_pb2.Function, constraints: Iterable[Constraint | constraint_pb2.Constraint], sense: instance_pb2.Instance.Sense.ValueType, decision_variables: Iterable[DecisionVariable | decision_variables_pb2.DecisionVariable], description: instance_pb2.Instance.Description | None = None) → Instance

get_constraint(constraint_id: int) → Constraint

Get a constraint by ID.

get_constraints() → list[Constraint]

Get constraints as a list of Constraint instances.

get_decision_variable(variable_id: int) → DecisionVariable

Get a decision variable by ID.

get_decision_variables() → list[DecisionVariable]

Get decision variables as a list of DecisionVariable instances.

get_removed_constraint(removed_constraint_id: int) → RemovedConstraint

Get a removed constraint by ID.

get_removed_constraints() → list[RemovedConstraint]

Get removed constraints as a list of RemovedConstraint instances.

get_user_annotation(key: str, *, annotation_namespace: str = 'org.ommx.user.')

Get a user annotation from the instance.

Examples

>>> instance = Instance.empty()
>>> instance.add_user_annotation("author", "Alice")
>>> instance.get_user_annotation("author")
'Alice'

get_user_annotations(*, annotation_namespace: str = 'org.ommx.user.') → dict[str, str]

Get user annotations from the instance.

See also add_user_annotation().

static load_mps(path: str) → Instance

static load_qplib(path: str) → Instance

log_encode(decision_variable_ids: set[int] = set({}))

Log-encode the integer decision variables

Log encoding of an integer variable \(x \in [l, u]\) is to represent by \(m\) bits \(b_i \in \{0, 1\}\) by

\[x = \sum_{i=0}^{m-2} 2^i b_i + (u - l - 2^{m-1} + 1) b_{m-1} + l\]

where \(m = \lceil \log_2(u - l + 1) \rceil\).

Parameters:

decision_variable_ids – The IDs of the integer decision variables to log-encode. If not specified, all integer variables are log-encoded.

Examples

Let’s consider a simple integer programming problem with three integer variables \(x_0\), \(x_1\), and \(x_2\).

>>> from ommx.v1 import Instance, DecisionVariable
>>> x = [
...     DecisionVariable.integer(i, lower=0, upper=3, name="x", subscripts=[i])
...     for i in range(3)
... ]
>>> instance = Instance.from_components(
...     decision_variables=x,
...     objective=sum(x),
...     constraints=[],
...     sense=Instance.MAXIMIZE,
... )
>>> instance.objective
Function(x0 + x1 + x2)

To log-encode the integer variables \(x_0\) and \(x_2\) (except \(x_1\)), call log_encode():

>>> instance.log_encode({0, 2})

Integer variable in range \([0, 3]\) can be represented by two binary variables:

\[x_0 = b_{0, 0} + 2 b_{0, 1}, x_2 = b_{2, 0} + 2 b_{2, 1}\]

And these are substituted into the objective and constraint functions.

>>> instance.objective
Function(x1 + x3 + 2*x4 + x5 + 2*x6)

Added binary variables are also appeared in decision_variables

>>> instance.decision_variables[["kind", "lower", "upper", "name", "subscripts"]]  
       kind  lower  upper             name subscripts
id
0   integer    0.0    3.0                x        [0]
1   integer    0.0    3.0                x        [1]
2   integer    0.0    3.0                x        [2]
3    binary    0.0    1.0  ommx.log_encode     [0, 0]
4    binary    0.0    1.0  ommx.log_encode     [0, 1]
5    binary    0.0    1.0  ommx.log_encode     [2, 0]
6    binary    0.0    1.0  ommx.log_encode     [2, 1]

The subscripts of the new binary variables must be two elements in form of \([i, j]\) where

• \(i\) is the decision variable ID of the original integer variable

• \(j\) is the index of the binary variable

After log-encoded, the problem does not contains original integer variables, and solver will returns only encoded variables.

>>> solution = instance.evaluate({
...   1: 2,          # x1 = 2
...   3: 0, 4: 1,    # x0 = x3 + 2*x4 = 0 + 2*1 = 2
...   5: 0, 6: 0     # x2 = x5 + 2*x6 = 0 + 2*0 = 0
... })               # x0 and x2 are not contained in the solver result

x0 and x2 are automatically evaluated:

>>> solution.extract_decision_variables("x")
{(0,): 2.0, (1,): 2.0, (2,): 0.0}

The name of the binary variables are automatically generated as ommx.log_encode.

>>> solution.extract_decision_variables("ommx.log_encode")
{(0, 0): 0.0, (0, 1): 1.0, (2, 0): 0.0, (2, 1): 0.0}

partial_evaluate(state: ToState) → Instance

Creates a new instance with specific decision variables fixed to given values.

This method substitutes the specified decision variables with their provided values, creating a new problem instance where these variables are fixed. This is useful for scenarios such as:

• Creating simplified sub-problems with some variables fixed

• Incrementally solving a problem by fixing some variables and optimizing the rest

• Testing specific configurations of a problem

Parameters:

state (ToState) – Maps decision variable IDs to their fixed values. Can be a State object or a dictionary mapping variable IDs to values.

Returns:

A new instance with the specified decision variables fixed to their given values.

Return type:

Instance

Examples

>>> from ommx.v1 import Instance, DecisionVariable
>>> x = DecisionVariable.binary(1)
>>> y = DecisionVariable.binary(2)
>>> instance = Instance.from_components(
...     decision_variables=[x, y],
...     objective=x + y,
...     constraints=[x + y <= 1],
...     sense=Instance.MINIMIZE
... )
>>> new_instance = instance.partial_evaluate({1: 1})
>>> new_instance.objective
Function(x2 + 1)

penalty_method() → ParametricInstance

Convert to a parametric unconstrained instance by penalty method.

Roughly, this converts a constrained problem

\[\begin{split}\begin{align*} \min_x & \space f(x) & \\ \text{ s.t. } & \space g_i(x) = 0 & (\forall i) \\ & \space h_j(x) \leq 0 & (\forall j) \end{align*}\end{split}\]

to an unconstrained problem with parameters

\[\min_x f(x) + \sum_i \lambda_i g_i(x)^2 + \sum_j \rho_j h_j(x)^2\]

where \(\lambda_i\) and \(\rho_j\) are the penalty weight parameters for each constraint. If you want to use single weight parameter, use uniform_penalty_method() instead.

The removed constrains are stored in removed_constraints.

Note

Note that this method converts inequality constraints \(h(x) \leq 0\) to \(|h(x)|^2\) not to \(\max(0, h(x))^2\). This means the penalty is enforced even for \(h(x) < 0\) cases, and \(h(x) = 0\) is unfairly favored.

This feature is intended to use with add_integer_slack_to_inequality().

Examples

>>> from ommx.v1 import Instance, DecisionVariable, Constraint
>>> x = [DecisionVariable.binary(i) for i in range(3)]
>>> instance = Instance.from_components(
...     decision_variables=x,
...     objective=sum(x),
...     constraints=[x[0] + x[1] == 1, x[1] + x[2] == 1],
...     sense=Instance.MAXIMIZE,
... )
>>> instance.objective
Function(x0 + x1 + x2)
>>> pi = instance.penalty_method()

The constraint is put in removed_constraints

>>> pi.get_constraints()
[]
>>> len(pi.get_removed_constraints())
2
>>> pi.get_removed_constraints()[0]
RemovedConstraint(Function(x0 + x1 - 1) == 0, reason=penalty_method, parameter_id=3)
>>> pi.get_removed_constraints()[1]
RemovedConstraint(Function(x1 + x2 - 1) == 0, reason=penalty_method, parameter_id=4)

There are two parameters corresponding to the two constraints

>>> len(pi.get_parameters())
2
>>> p1 = pi.get_parameters()[0]
>>> p1.id, p1.name
(3, 'penalty_weight')
>>> p2 = pi.get_parameters()[1]
>>> p2.id, p2.name
(4, 'penalty_weight')

Substitute all parameters to zero to get the original objective

>>> instance0 = pi.with_parameters({p1.id: 0.0, p2.id: 0.0})
>>> instance0.objective
Function(x0 + x1 + x2)

Substitute all parameters to one

>>> instance1 = pi.with_parameters({p1.id: 1.0, p2.id: 1.0})
>>> instance1.objective
Function(x0*x0 + 2*x0*x1 + 2*x1*x1 + 2*x1*x2 + x2*x2 - x0 - 3*x1 - x2 + 2)

relax_constraint(constraint_id: int, reason: str, **parameters)

Remove a constraint from the instance. The removed constraint is stored in removed_constraints, and can be restored by restore_constraint().

Parameters:

• constraint_id – The ID of the constraint to remove.

• reason – The reason why the constraint is removed.

• parameters – Additional parameters to describe the reason.

Examples

Relax constraint, and restore it.

>>> from ommx.v1 import Instance, DecisionVariable
>>> x = [DecisionVariable.binary(i) for i in range(3)]
>>> instance = Instance.from_components(
...     decision_variables=x,
...     objective=sum(x),
...     constraints=[(sum(x) == 3).set_id(1)],
...     sense=Instance.MAXIMIZE,
... )
>>> instance.get_constraints()
[Constraint(Function(x0 + x1 + x2 - 3) == 0)]

>>> instance.relax_constraint(1, "manual relaxation")
>>> instance.get_constraints()
[]
>>> instance.get_removed_constraints()
[RemovedConstraint(Function(x0 + x1 + x2 - 3) == 0, reason=manual relaxation)]

>>> instance.restore_constraint(1)
>>> instance.get_constraints()
[Constraint(Function(x0 + x1 + x2 - 3) == 0)]
>>> instance.get_removed_constraints()
[]

Evaluate relaxed instance, and show feasible_unrelaxed.

>>> from ommx.v1 import Instance, DecisionVariable
>>> x = [DecisionVariable.binary(i) for i in range(3)]
>>> instance = Instance.from_components(
...     decision_variables=x,
...     objective=sum(x),
...     constraints=[
...         (x[0] + x[1] == 2).set_id(0),
...         (x[1] + x[2] == 2).set_id(1),
...     ],
...     sense=Instance.MINIMIZE,
... )

For x0=0, x1=1, x2=1
- x0 + x1 == 2 is not feasible
- x1 + x2 == 2 is feasible

>>> solution = instance.evaluate({0: 0, 1: 1, 2: 1})
>>> solution.feasible_relaxed
False
>>> solution.feasible_unrelaxed
False

Relax the constraint: x0 + x1 == 2

>>> instance.relax_constraint(0, "testing")
>>> solution = instance.evaluate({0: 0, 1: 1, 2: 1})
>>> solution.feasible_relaxed
True
>>> solution.feasible_unrelaxed
False

restore_constraint(constraint_id: int)

Restore a removed constraint to the instance.

Parameters:

constraint_id – The ID of the constraint to restore.

Note that this drops the removed reason and associated parameters. See relax_constraint() for details.

to_bytes() → bytes

to_qubo(*, uniform_penalty_weight: float | None = None, penalty_weights: dict[int, float] = {}, inequality_integer_slack_max_range: int = 31) → tuple[dict[tuple[int, int], float], float]

Convert the instance to a QUBO format

This is a Driver API for QUBO conversion calling single-purpose methods in order:

1. Convert the instance to a minimization problem by as_minimization_problem().

2. Check continuous variables and raise error if exists.

3. Log-encode integer variables by log_encode().

4. Convert inequality constraints

   • Try convert_inequality_to_equality_with_integer_slack() first with given inequality_integer_slack_max_range.

   • If failed, add_integer_slack_to_inequality()

5. Convert to QUBO with (uniform) penalty method

   • If penalty_weights is given (in dict[constraint_id, weight] form), use penalty_method() with the given weights.

   • If uniform_penalty_weight is given, use uniform_penalty_method() with the given weight.

   • If both are None, defaults to uniform_penalty_weight = 1.0.

6. Finally convert to QUBO format by as_qubo_format().

Please see the document of each method for details. If you want to customize the conversion, use the methods above manually.

Important

The above process is not stable, and subject to change for better QUBO generation in the future versions. If you wish to keep the compatibility, please use the methods above manually.

Examples

Let’s consider a maximization problem with two integer variables \(x_0, x_1 \in [0, 2]\) subject to an inequality:

\[\begin{split}\begin{align*} \max_{x_0, x_1} & \space x_0 + x_1 & \\ \text{ s.t. } & \space x_0 + 2x_1 \leq 3 \end{align*}\end{split}\]

>>> from ommx.v1 import Instance, DecisionVariable
>>> x = [DecisionVariable.integer(i, lower=0, upper=2, name = "x", subscripts=[i]) for i in range(2)]
>>> instance = Instance.from_components(
...     decision_variables=x,
...     objective=sum(x),
...     constraints=[(x[0] + 2*x[1] <= 3).set_id(0)],
...     sense=Instance.MAXIMIZE,
... )

Convert into QUBO format

>>> qubo, offset = instance.to_qubo()
>>> qubo
{(3, 3): -6.0, (3, 4): 2.0, (3, 5): 4.0, (3, 6): 4.0, (3, 7): 2.0, (3, 8): 4.0, (4, 4): -6.0, (4, 5): 4.0, (4, 6): 4.0, (4, 7): 2.0, (4, 8): 4.0, (5, 5): -9.0, (5, 6): 8.0, (5, 7): 4.0, (5, 8): 8.0, (6, 6): -9.0, (6, 7): 4.0, (6, 8): 8.0, (7, 7): -5.0, (7, 8): 4.0, (8, 8): -8.0}
>>> offset
9.0

The instance object stores how converted:

• For the maximization problem, the sense is converted to minimization for generating QUBO, and then converted back to maximization.

>>> instance.sense == Instance.MAXIMIZE
True

• Two types of decision variables are added

  • ommx.slack integer slack variable \(x_2\) by convert_inequality_to_equality_with_integer_slack()

  • ommx.log_encode binary variables \(x_3, \ldots, x_8\) introduced by log_encode().

>>> instance.decision_variables.dropna(axis=1, how="all")  
       kind  lower  upper             name subscripts
id
0   integer    0.0    2.0                x        [0]
1   integer    0.0    2.0                x        [1]
2   integer    0.0    3.0       ommx.slack        [0]
3    binary    0.0    1.0  ommx.log_encode     [0, 0]
4    binary    0.0    1.0  ommx.log_encode     [0, 1]
5    binary    0.0    1.0  ommx.log_encode     [1, 0]
6    binary    0.0    1.0  ommx.log_encode     [1, 1]
7    binary    0.0    1.0  ommx.log_encode     [2, 0]
8    binary    0.0    1.0  ommx.log_encode     [2, 1]

• The yielded objective and removed_constraints only has these binary variables.

>>> instance.objective
Function(-x3*x3 - 2*x3*x4 - 4*x3*x5 - 4*x3*x6 - 2*x3*x7 - 4*x3*x8 - x4*x4 - 4*x4*x5 - 4*x4*x6 - 2*x4*x7 - 4*x4*x8 - 4*x5*x5 - 8*x5*x6 - 4*x5*x7 - 8*x5*x8 - 4*x6*x6 - 4*x6*x7 - 8*x6*x8 - x7*x7 - 4*x7*x8 - 4*x8*x8 + 7*x3 + 7*x4 + 13*x5 + 13*x6 + 6*x7 + 12*x8 - 9)
>>> instance.get_removed_constraint(0)
RemovedConstraint(Function(x3 + x4 + 2*x5 + 2*x6 + x7 + 2*x8 - 3) == 0, reason=uniform_penalty_method)

The solver will returns the solution, which only contains the log-encoded binary variables like:

>>> state = {
...     3: 1, 4: 1,  # x0 = 0 + (2-1)*1 = 2
...     5: 0, 6: 0,  # x1 = 0 + (2-1)*0 = 0
...     7: 1, 8: 0   # x3 = 1 + 2*0 = 1
... }

This can be evaluated by evaluate() method.

>>> solution = instance.evaluate(state)

The log-encoded integer variables are automatically evaluated from the binary variables.

>>> solution.decision_variables.dropna(axis=1, how="all")  
       kind  lower  upper             name subscripts  value
id
0   integer    0.0    2.0                x        [0]    2.0
1   integer    0.0    2.0                x        [1]    0.0
2   integer    0.0    3.0       ommx.slack        [0]    1.0
3    binary    0.0    1.0  ommx.log_encode     [0, 0]    1.0
4    binary    0.0    1.0  ommx.log_encode     [0, 1]    1.0
5    binary    0.0    1.0  ommx.log_encode     [1, 0]    0.0
6    binary    0.0    1.0  ommx.log_encode     [1, 1]    0.0
7    binary    0.0    1.0  ommx.log_encode     [2, 0]    1.0
8    binary    0.0    1.0  ommx.log_encode     [2, 1]    0.0

>>> solution.objective
2.0

>>> solution.constraints.dropna(axis=1, how="all")  
   equality  value            used_ids subscripts          removed_reason
id
0        =0    0.0  {3, 4, 5, 6, 7, 8}         []  uniform_penalty_method

uniform_penalty_method() → ParametricInstance

Convert to a parametric unconstrained instance by penalty method with uniform weight.

Roughly, this converts a constrained problem

\[\begin{split}\begin{align*} \min_x & \space f(x) & \\ \text{ s.t. } & \space g_i(x) = 0 & (\forall i) \\ & \space h_j(x) \leq 0 & (\forall j) \end{align*}\end{split}\]

to an unconstrained problem with a parameter

\[\min_x f(x) + \lambda \left( \sum_i g_i(x)^2 + \sum_j h_j(x)^2 \right)\]

where \(\lambda\) is the uniform penalty weight parameter for all constraints.

The removed constrains are stored in removed_constraints.

Note

Note that this method converts inequality constraints \(h(x) \leq 0\) to \(|h(x)|^2\) not to \(\max(0, h(x))^2\). This means the penalty is enforced even for \(h(x) < 0\) cases, and \(h(x) = 0\) is unfairly favored.

This feature is intended to use with add_integer_slack_to_inequality().

Examples

>>> from ommx.v1 import Instance, DecisionVariable
>>> x = [DecisionVariable.binary(i) for i in range(3)]
>>> instance = Instance.from_components(
...     decision_variables=x,
...     objective=sum(x),
...     constraints=[sum(x) == 3],
...     sense=Instance.MAXIMIZE,
... )
>>> instance.objective
Function(x0 + x1 + x2)
>>> pi = instance.uniform_penalty_method()

The constraint is put in removed_constraints

>>> pi.get_constraints()
[]
>>> len(pi.get_removed_constraints())
1
>>> pi.get_removed_constraints()[0]
RemovedConstraint(Function(x0 + x1 + x2 - 3) == 0, reason=uniform_penalty_method)

There is only one parameter in the instance

>>> len(pi.get_parameters())
1
>>> p = pi.get_parameters()[0]
>>> p.id
3
>>> p.name
'uniform_penalty_weight'

Substitute p = 0 to get the original objective

>>> instance0 = pi.with_parameters({p.id: 0.0})
>>> instance0.objective
Function(x0 + x1 + x2)

Substitute p = 1

>>> instance1 = pi.with_parameters({p.id: 1.0})
>>> instance1.objective
Function(x0*x0 + 2*x0*x1 + 2*x0*x2 + x1*x1 + 2*x1*x2 + x2*x2 - 5*x0 - 5*x1 - 5*x2 + 9)

used_decision_variable_ids() → set[int]

Get the set of decision variable IDs used in the objective and remaining constraints.

Examples

>>> x = [DecisionVariable.binary(i) for i in range(3)]
>>> instance = Instance.from_components(
...     decision_variables=x,
...     objective=sum(x),
...     constraints=[],
...     sense=Instance.MAXIMIZE,
... )
>>> instance.used_decision_variable_ids()
{0, 1, 2}

>>> instance = Instance.from_components(
...     decision_variables=x,
...     objective=x[0],
...     constraints=[(x[1] == 1).set_id(0)],
...     sense=Instance.MAXIMIZE,
... )
>>> instance.used_decision_variable_ids()
{0, 1}

>>> instance.relax_constraint(0, "testing")
>>> instance.used_decision_variable_ids()
{0, 1}

write_mps(path: str)

Outputs the instance as an MPS file.

• The outputted file is compressed by gzip.

• Only linear problems are supported.

• Various forms of metadata, like problem description and variable/constraint names, are not preserved.

Description

MAXIMIZE

MINIMIZE

annotation_namespace = 'org.ommx.v1.instance'

annotations: dict[str, str]

Arbitrary annotations stored in OMMX artifact. Use title or other specific attributes if possible.

authors

Authors of this instance, stored as org.ommx.v1.instance.authors annotation in OMMX artifact.

property constraints: pandas.DataFrame

created

The creation date of the instance, stored as org.ommx.v1.instance.created annotation in RFC3339 format in OMMX artifact.

dataset

Dataset name which this instance belongs to, stored as org.ommx.v1.instance.dataset annotation in OMMX artifact.

property decision_variables: pandas.DataFrame

property description: instance_pb2.Instance.Description

license

License of this instance in the SPDX license identifier. This is stored as org.ommx.v1.instance.license annotation in OMMX artifact.

num_constraints

Number of constraints in this instance, stored as org.ommx.v1.instance.constraints annotation in OMMX artifact.

num_variables

Number of variables in this instance, stored as org.ommx.v1.instance.variables annotation in OMMX artifact.

property objective: Function

raw: instance_pb2.Instance

The raw protobuf message.

property removed_constraints: pandas.DataFrame

property sense: instance_pb2.Instance.Sense.ValueType

title

The title of the instance, stored as org.ommx.v1.instance.title annotation in OMMX artifact.

class ommx.v1.Linear(*, terms: dict[int, float | int], constant: float | int = 0)

Modeler API for linear function

This is a wrapper of linear_pb2.Linear protobuf message.

Examples

Create a linear function :math:`f(x_1, x_2) = 2 x_1 + 3 x_2 + 1`
>>> f = Linear(terms={1: 2, 2: 3}, constant=1)

Or create via DecisionVariable
>>> x1 = DecisionVariable.integer(1)
>>> x2 = DecisionVariable.integer(2)
>>> g = 2*x1 + 3*x2 + 1

Compare two linear functions are equal in terms of a polynomial with tolerance
>>> assert f.almost_equal(g, atol=1e-12)

Note that `f == g` becomes an equality `Constraint`
>>> assert isinstance(f == g, Constraint)

almost_equal(other: Linear, *, atol: float = 1e-10) → bool

Compare two linear functions have almost equal coefficients and constant.

equals_to(other: Linear) → bool

Alternative to == operator to compare two linear functions.

evaluate(state: ToState) → tuple[float, set]

Evaluate the linear function with the given state.

Examples

Evaluate `2 x1 + 3 x2 + 1` with `x1 = 3, x2 = 4, x3 = 5`

>>> f = Linear(terms={1: 2, 2: 3}, constant=1)
>>> value, used_ids = f.evaluate({1: 3, 2: 4, 3: 5}) # Unused ID `3` can be included

2*3 + 3*4 + 1 = 19
>>> value
19.0

Since the value of ID `3` of `state` is not used, the it is not included in `used_ids`.
>>> used_ids
{1, 2}

Missing ID raises an error
>>> f.evaluate({1: 3})
Traceback (most recent call last):
...
RuntimeError: Variable id (2) is not found in the solution

static from_bytes(data: bytes) → Linear

static from_raw(raw: linear_pb2.Linear) → Linear

partial_evaluate(state: ToState) → tuple[Linear, set]

Partially evaluate the linear function with the given state.

Examples

Evaluate `2 x1 + 3 x2 + 1` with `x1 = 3`, yielding `3 x2 + 7`

>>> f = Linear(terms={1: 2, 2: 3}, constant=1)
>>> new_f, used_ids = f.partial_evaluate({1: 3})
>>> new_f
Linear(3*x2 + 7)
>>> used_ids
{1}
>>> new_f.partial_evaluate({2: 4})
(Linear(19), {2})

to_bytes() → bytes

property constant: float

Get the constant term of the linear function

property linear_terms: dict[int, float]

Get the terms of the linear function as a dictionary

raw: linear_pb2.Linear

property terms: dict[tuple[int, Ellipsis], float]

Linear terms and constant as a dictionary

class ommx.v1.Parameter

Idiomatic wrapper of ommx.v1.Parameter protobuf message.

equals_to(other: Parameter) → bool

Alternative to == operator to compare two decision variables.

static from_bytes(data: bytes) → Parameter

static new(id: int, *, name: str | None = None, subscripts: Iterable[int] = [], description: str | None = None)

to_bytes() → bytes

property description: str

property id: int

property name: str

property parameters: dict[str, str]

raw: parametric_instance_pb2.Parameter

property subscripts: list[int]

class ommx.v1.ParametricInstance

Idiomatic wrapper of ommx.v1.ParametricInstance protobuf message.

Examples

Create an instance for KnapSack Problem with parameters

>>> from ommx.v1 import ParametricInstance, DecisionVariable, Parameter

Decision variables

>>> x = [DecisionVariable.binary(i, name="x", subscripts=[i]) for i in range(6)]

Profit and weight of items as parameters

>>> p = [Parameter.new(id=i+6, name="Profit", subscripts=[i]) for i in range(6)]
>>> w = [Parameter.new(id=i+12, name="Weight", subscripts=[i]) for i in range(6)]
>>> W = Parameter.new(id=18, name="Capacity")

Objective and constraint

>>> objective = sum(p[i] * x[i] for i in range(6))
>>> constraint = sum(w[i] * x[i] for i in range(6)) <= W

Compose as an instance

>>> parametric_instance = ParametricInstance.from_components(
...     decision_variables=x,
...     parameters=p + w + [W],
...     objective=objective,
...     constraints=[constraint],
...     sense=Instance.MAXIMIZE,
... )

Substitute parameters to get an instance

>>> p_values = { x.id: value for x, value in zip(p, [10, 13, 18, 31, 7, 15]) }
>>> w_values = { x.id: value for x, value in zip(w, [11, 15, 20, 35, 10, 33]) }
>>> W_value = { W.id: 47 }
>>> instance = parametric_instance.with_parameters({**p_values, **w_values, **W_value})

static empty() → ParametricInstance

Create trivial empty instance of minimization with zero objective, no constraints, and no decision variables and parameters.

static from_bytes(data: bytes) → ParametricInstance

static from_components(*, objective: int | float | DecisionVariable | Linear | Quadratic | Polynomial | function_pb2.Function, constraints: Iterable[Constraint | constraint_pb2.Constraint], sense: instance_pb2.Instance.Sense.ValueType, decision_variables: Iterable[DecisionVariable | decision_variables_pb2.DecisionVariable], parameters: Iterable[Parameter | parametric_instance_pb2.Parameter], description: instance_pb2.Instance.Description | None = None) → ParametricInstance

get_constraint(constraint_id: int) → Constraint

Get a constraint by ID.

get_constraints() → list[Constraint]

Get constraints as a list of :class:`Constraint

get_decision_variable(variable_id: int) → DecisionVariable

Get a decision variable by ID.

get_decision_variables() → list[DecisionVariable]

Get decision variables as a list of DecisionVariable instances.

get_parameter(parameter_id: int) → Parameter

Get a parameter by ID.

get_parameters() → list[Parameter]

Get parameters as a list of Parameter.

get_removed_constraint(removed_constraint_id: int) → RemovedConstraint

Get a removed constraint by ID.

get_removed_constraints() → list[RemovedConstraint]

Get removed constraints as a list of RemovedConstraint instances.

to_bytes() → bytes

with_parameters(parameters: instance_pb2.Parameters | Mapping[int, float]) → Instance

Substitute parameters to yield an instance.

annotation_namespace = 'org.ommx.v1.parametric-instance'

annotations: dict[str, str]

authors

Authors of this instance, stored as org.ommx.v1.parametric-instance.authors annotation in OMMX artifact.

property constraints: pandas.DataFrame

created

The creation date of the instance, stored as org.ommx.v1.parametric-instance.created annotation in RFC3339 format in OMMX artifact.

dataset

Dataset name which this instance belongs to, stored as org.ommx.v1.parametric-instance.dataset annotation in OMMX artifact.

property decision_variables: pandas.DataFrame

license

License of this instance in the SPDX license identifier. This is stored as org.ommx.v1.parametric-instance.license annotation in OMMX artifact.

num_constraints

Number of constraints in this instance, stored as org.ommx.v1.parametric-instance.constraints annotation in OMMX artifact.

num_variables

Number of variables in this instance, stored as org.ommx.v1.parametric-instance.variables annotation in OMMX artifact.

property parameters: pandas.DataFrame

raw: parametric_instance_pb2.ParametricInstance

property removed_constraints: pandas.DataFrame

title

The title of the instance, stored as org.ommx.v1.parametric-instance.title annotation in OMMX artifact.

class ommx.v1.Polynomial(*, terms: dict[Iterable[int], float | int] = {})

Helper class that provides a standard way to create an ABC using inheritance.

almost_equal(other: Polynomial, *, atol: float = 1e-10) → bool

Compare two polynomial have almost equal coefficients

evaluate(state: ToState) → tuple[float, set]

Evaluate the polynomial with the given state.

Examples

Evaluate `2 x1 x2 x3 + 3 x2 x3 + 1` with `x1 = 3, x2 = 4, x3 = 5`

>>> x1 = DecisionVariable.integer(1)
>>> x2 = DecisionVariable.integer(2)
>>> x3 = DecisionVariable.integer(3)
>>> f = 2*x1*x2*x3 + 3*x2*x3 + 1
>>> f
Polynomial(2*x1*x2*x3 + 3*x2*x3 + 1)

>>> f.evaluate({1: 3, 2: 4, 3: 5})
(181.0, {1, 2, 3})

Missing ID raises an error
>>> f.evaluate({1: 3})
Traceback (most recent call last):
...
RuntimeError: Variable id (2) is not found in the solution

static from_bytes(data: bytes) → Polynomial

static from_raw(raw: polynomial_pb2.Polynomial) → Polynomial

partial_evaluate(state: ToState) → tuple[Polynomial, set]

Partially evaluate the polynomial with the given state.

Examples

Evaluate `2 x1 x2 x3 + 3 x2 x3 + 1` with `x1 = 3`, yielding `9 x2 x3 + 1`

>>> x1 = DecisionVariable.integer(1)
>>> x2 = DecisionVariable.integer(2)
>>> x3 = DecisionVariable.integer(3)
>>> f = 2*x1*x2*x3 + 3*x2*x3 + 1
>>> f
Polynomial(2*x1*x2*x3 + 3*x2*x3 + 1)

>>> f.partial_evaluate({1: 3})
(Polynomial(9*x2*x3 + 1), {1})

to_bytes() → bytes

raw: polynomial_pb2.Polynomial

property terms: dict[tuple[int, Ellipsis], float]

class ommx.v1.Quadratic(*, columns: Iterable[int], rows: Iterable[int], values: Iterable[float | int], linear: Linear | None = None)

Helper class that provides a standard way to create an ABC using inheritance.

almost_equal(other: Quadratic, *, atol: float = 1e-10) → bool

Compare two quadratic functions have almost equal coefficients

evaluate(state: ToState) → tuple[float, set]

Evaluate the quadratic function with the given state.

Examples

Evaluate `2 x1 x2 + 3 x2 x3 + 1` with `x1 = 3, x2 = 4, x3 = 5`

>>> x1 = DecisionVariable.integer(1)
>>> x2 = DecisionVariable.integer(2)
>>> x3 = DecisionVariable.integer(3)
>>> f = 2*x1*x2 + 3*x2*x3 + 1
>>> f
Quadratic(2*x1*x2 + 3*x2*x3 + 1)

>>> f.evaluate({1: 3, 2: 4, 3: 5})
(85.0, {1, 2, 3})

Missing ID raises an error
>>> f.evaluate({1: 3})
Traceback (most recent call last):
...
RuntimeError: Variable id (2) is not found in the solution

static from_bytes(data: bytes) → Quadratic

static from_raw(raw: quadratic_pb2.Quadratic) → Quadratic

partial_evaluate(state: ToState) → tuple[Quadratic, set]

Partially evaluate the quadratic function with the given state.

Examples

Evaluate `2 x1 x2 + 3 x2 x3 + 1` with `x1 = 3`, yielding `3 x2 x3 + 6 x2 + 1`

>>> x1 = DecisionVariable.integer(1)
>>> x2 = DecisionVariable.integer(2)
>>> x3 = DecisionVariable.integer(3)
>>> f = 2*x1*x2 + 3*x2*x3 + 1
>>> f
Quadratic(2*x1*x2 + 3*x2*x3 + 1)

>>> f.partial_evaluate({1: 3})
(Quadratic(3*x2*x3 + 6*x2 + 1), {1})

to_bytes() → bytes

property linear: Linear | None

property quad_terms: dict[tuple[int, int], float]

raw: quadratic_pb2.Quadratic

property terms: dict[tuple[int, Ellipsis], float]

class ommx.v1.SampleSet

The output of sampling-based optimization algorithms, e.g. simulated annealing (SA).

• Similar to Solution rather than solution_pb2.State. This class contains the sampled values of decision variables with the objective value, constraint violations, feasibility, and metadata of constraints and decision variables.

• This class is usually created via Instance.evaluate_samples().

Examples

Let’s consider a simple optimization problem:

\[\begin{split}\begin{align*} \max &\quad x_1 + 2 x_2 + 3 x_3 \\ \text{s.t.} &\quad x_1 + x_2 + x_3 = 1 \\ &\quad x_1, x_2, x_3 \in \{0, 1\} \end{align*}\end{split}\]

>>> x = [DecisionVariable.binary(i) for i in range(3)]
>>> instance = Instance.from_components(
...     decision_variables=x,
...     objective=x[0] + 2*x[1] + 3*x[2],
...     constraints=[sum(x) == 1],
...     sense=Instance.MAXIMIZE,
... )

with three samples:

>>> samples = {
...     0: {0: 1, 1: 0, 2: 0},  # x1 = 1, x2 = x3 = 0
...     1: {0: 0, 1: 0, 2: 1},  # x3 = 1, x1 = x2 = 0
...     2: {0: 1, 1: 1, 2: 0},  # x1 = x2 = 1, x3 = 0 (infeasible)
... } # ^ sample ID

Note that this will be done by sampling-based solvers, but we do it manually here. We can evaluate the samples with via Instance.evaluate_samples():

>>> sample_set = instance.evaluate_samples(samples)
>>> sample_set.summary  
           objective  feasible
sample_id
1                3.0      True
0                1.0      True
2                3.0     False

The summary attribute shows the objective value, feasibility of each sample. Note that this feasible column represents the feasibility of the original constraints, not the relaxed constraints. You can get each samples by get() as a Solution format:

>>> solution = sample_set.get(sample_id=0)
>>> solution.objective
1.0
>>> solution.decision_variables  
      kind  lower  upper  name subscripts description substituted_value  value
id
0   binary    0.0    1.0  <NA>         []        <NA>              <NA>    1.0
1   binary    0.0    1.0  <NA>         []        <NA>              <NA>    0.0
2   binary    0.0    1.0  <NA>         []        <NA>              <NA>    0.0

best_feasible() returns the best feasible sample, i.e. the largest objective value among feasible samples:

>>> solution = sample_set.best_feasible()
>>> solution.objective
3.0
>>> solution.decision_variables  
      kind  lower  upper  name subscripts description substituted_value  value
id
0   binary    0.0    1.0  <NA>         []        <NA>              <NA>    0.0
1   binary    0.0    1.0  <NA>         []        <NA>              <NA>    0.0
2   binary    0.0    1.0  <NA>         []        <NA>              <NA>    1.0

Of course, the sample of smallest objective value is returned for minimization problems.

best_feasible() → Solution

Get the best feasible solution

best_feasible_unrelaxed() → Solution

Get the best feasible solution without relaxation

extract_constraints(name: str, sample_id: int) → dict[tuple[int, Ellipsis], float]

Extract evaluated constraint violations for a given constraint name and sample ID.

extract_decision_variables(name: str, sample_id: int) → dict[tuple[int, Ellipsis], float]

Extract sampled decision variable values for a given name and sample ID.

static from_bytes(data: bytes) → SampleSet

get(sample_id: int) → Solution

Get a sample for a given ID as a solution format

to_bytes() → bytes

annotation_namespace = 'org.ommx.v1.sample-set'

annotations: dict[str, str]

Arbitrary annotations stored in OMMX artifact. Use parameters or other specific attributes if possible.

property constraints: pandas.DataFrame

property decision_variables: pandas.DataFrame

end

When the optimization ended, stored as org.ommx.v1.sample-set.end annotation in RFC3339 format in OMMX artifact.

property feasible: dict[int, bool]

Feasibility in terms of the original constraints, an alias to feasible_unrelaxed.

Compatibility

The meaning of this property has changed from Python SDK 1.7.0. Previously, this property represents the feasibility of the remaining constraints only, i.e. excluding relaxed constraints. From Python SDK 1.7.0, this property represents the feasibility of all constraints, including relaxed constraints.

property feasible_relaxed: dict[int, bool]

Feasibility in terms of the remaining (non-removed) constraints.

For each sample_id, this property shows whether the sample is feasible for the all Instance.constraints

property feasible_unrelaxed: dict[int, bool]

Feasibility in terms of the original constraints without relaxation.

For each sample_id, this property shows whether the sample is feasible both for the all Instance.constraints and all Instance.removed_constraints.

instance

The digest of the instance layer, stored as org.ommx.v1.sample-set.instance annotation in OMMX artifact.

property objectives: dict[int, float]

parameters

The parameters used in the optimization, stored as org.ommx.v1.sample-set.parameters annotation as a JSON in OMMX artifact.

raw: sample_set_pb2.SampleSet

property sample_ids: list[int]

solver

The solver which generated this sample set, stored as org.ommx.v1.sample-set.solver annotation as a JSON in OMMX artifact.

start

When the optimization started, stored as org.ommx.v1.sample-set.start annotation in RFC3339 format in OMMX artifact.

property summary: pandas.DataFrame

property summary_with_constraints: pandas.DataFrame

class ommx.v1.SampledValues

as_series() → pandas.Series

raw: sample_set_pb2.SampledValues

class ommx.v1.Solution

Idiomatic wrapper of ommx.v1.Solution protobuf message.

This also contains annotations not contained in protobuf message, and will be stored in OMMX artifact.

extract_constraints(name: str) → dict[tuple[int, Ellipsis], float]

Extract the values of constraints based on the name with subscripts key.

Raises:

ValueError – If the constraint with parameters is found, or if the same subscript is found.

Examples

>>> from ommx.v1 import Instance, DecisionVariable
>>> x = [DecisionVariable.binary(i) for i in range(3)]
>>> c0 = (x[0] + x[1] == 1).add_name("c").add_subscripts([0])
>>> c1 = (x[1] + x[2] == 1).add_name("c").add_subscripts([1])
>>> instance = Instance.from_components(
...     decision_variables=x,
...     objective=sum(x),
...     constraints=[c0, c1],
...     sense=Instance.MAXIMIZE,
... )
>>> solution = instance.evaluate({0: 1, 1: 0, 2: 1})
>>> solution.extract_constraints("c")
{(0,): 0.0, (1,): 0.0}

extract_decision_variables(name: str) → dict[tuple[int, Ellipsis], float]

Extract the values of decision variables based on the name with subscripts key.

Raises:

ValueError – If the decision variable with parameters is found, or if the same subscript is found.

Examples

>>> from ommx.v1 import Instance, DecisionVariable
>>> x = [DecisionVariable.binary(i, name="x", subscripts=[i]) for i in range(3)]
>>> instance = Instance.from_components(
...     decision_variables=x,
...     objective=sum(x),
...     constraints=[sum(x) == 1],
...     sense=Instance.MAXIMIZE,
... )
>>> solution = instance.evaluate({i: 1 for i in range(3)})
>>> solution.extract_decision_variables("x")
{(0,): 1.0, (1,): 1.0, (2,): 1.0}

static from_bytes(data: bytes) → Solution

to_bytes() → bytes

annotation_namespace = 'org.ommx.v1.solution'

annotations: dict[str, str]

Arbitrary annotations stored in OMMX artifact. Use parameters or other specific attributes if possible.

property constraints: pandas.DataFrame

property decision_variables: pandas.DataFrame

end

When the optimization ended, stored as org.ommx.v1.solution.end annotation in RFC3339 format in OMMX artifact.

property feasible: bool

Feasibility of the solution in terms of all constraints, including removed_constraints.

This is an alias for feasible_unrelaxed.

Compatibility

The meaning of this property has changed from Python SDK 1.7.0. Previously, this property represents the feasibility of the remaining constraints only, i.e. excluding relaxed constraints. From Python SDK 1.7.0, this property represents the feasibility of all constraints, including relaxed constraints.

property feasible_relaxed: bool

Feasibility of the solution in terms of remaining constraints, not including relaxed (removed) constraints.

property feasible_unrelaxed: bool

Feasibility of the solution in terms of all constraints, including relaxed (removed) constraints.

instance

The digest of the instance layer, stored as org.ommx.v1.solution.instance annotation in OMMX artifact.

This Solution is the solution of the mathematical programming problem described by the instance.

property objective: float

property optimality: solution_pb2.Optimality.ValueType

parameters

The parameters used in the optimization, stored as org.ommx.v1.solution.parameters annotation as a JSON in OMMX artifact.

raw: solution_pb2.Solution

The raw protobuf message.

property relaxation: solution_pb2.Relaxation.ValueType

solver

The solver which generated this solution, stored as org.ommx.v1.solution.solver annotation as a JSON in OMMX artifact.

start

When the optimization started, stored as org.ommx.v1.solution.start annotation in RFC3339 format in OMMX artifact.

property state: solution_pb2.State

ommx.v1.ToSamples: typing_extensions.TypeAlias

Type alias for convertible types to Samples.

ommx.v1.ToState: typing_extensions.TypeAlias

Type alias for convertible types to State.