Solving Optimization Problems with OMMX Adapter

Solving Optimization Problems with OMMX Adapter#

OMMX provides OMMX Adapter software to enable interoperability with existing mathematical optimization tools. By using OMMX Adapter, you can convert optimization problems expressed in OMMX schemas into formats acceptable to other optimization tools, and convert the resulting data from those tools back into OMMX schemas.

Here, we introduce how to solve a 0-1 Knapsack Problem via OMMX PySCIPOpt Adapter.

Installing the Required Libraries#

First, install OMMX PySCIPOpt Adapter with:

pip install ommx-pyscipopt-adapter

Two Steps for Running the Optimization#

Flow for solving 0-1 Knapsack Problem via OMMX PySCIPOpt Adapter

Fig. 4 Flow for solving 0-1 Knapsack Problem with OMMX PySCIPOpt Adapter.#

To solve the 0-1 Knapsack Problem through the OMMX PySCIPOpt Adapter, follow these two steps:

  1. Prepare the 0-1 Knapsack problem instance.

  2. Run the optimization via OMMX Adapter.

In Step 1, we create an ommx.v1.Instance object defined in the OMMX Message Instance schema. There are several ways to generate this object, but in this guide, we’ll illustrate how to write it directly using the OMMX Python SDK.

Tip

There are four ways to prepare an ommx.v1.Instance:

  1. Write ommx.v1.Instance directly with the OMMX Python SDK.

  2. Convert an MPS file to ommx.v1.Instance using the OMMX Python SDK.

  3. Convert a problem instance from a different optimization tool into ommx.v1.Instance using an OMMX Adapter.

  4. Export ommx.v1.Instance from JijModeling.

In Step 2, we convert ommx.v1.Instance into a PySCIPOpt Model object and run optimization with SCIP. The result is obtained as an ommx.v1.Solution object defined by the OMMX Message Solution schema.

Step 1: Preparing a 0-1 Knapsack Problem Instance#

The 0-1 Knapsack problem is formulated as:

\[\begin{split} \begin{align*} \mathrm{maximize} \quad & \sum_{i=0}^{N-1} v_i x_i \\ \mathrm{s.t.} \quad & \sum_{i=0}^{n-1} w_i x_i - W \leq 0, \\ & x_{i} \in \{ 0, 1\} \end{align*} \end{split}\]

We set the following data as parameters for this model.

# Data for 0-1 Knapsack Problem
v = [10, 13, 18, 31, 7, 15]   # Values of each item
w = [11, 25, 20, 35, 10, 33] # Weights of each item
W = 47  # Capacity of the knapsack
N = len(v)  # Total number of items

Below is an example code using the OMMX Python SDK to describe this problem instance.

from ommx.v1 import Instance, DecisionVariable

# Define decision variables
x = [
    # Define binary variable x_i
    DecisionVariable.binary(
        # Specify the ID of the decision variable
        id=i,
        # Specify the name of the decision variable
        name="x",
        # Specify the subscript of the decision variable
        subscripts=[i],
    )
    # Prepare binary variables for the number of items
    for i in range(N)
]

# Define the objective function
objective = sum(v[i] * x[i] for i in range(N))

# Define the constraint
constraint = sum(w[i] * x[i] for i in range(N)) - W <= 0
# Specify the name of the constraint
constraint.add_name("Weight limit")

# Create an instance
instance = Instance.from_components(
    # Register all decision variables included in the instance
    decision_variables=x,
    # Register the objective function
    objective=objective,
    # Register all constraints
    constraints=[constraint],
    # Specify that it is a maximization problem
    sense=Instance.MAXIMIZE,
)

Step 2: Running Optimization with OMMX Adapter#

To optimize the instance prepared in Step 1, we convert it to a PySCIPOpt Model and run SCIP optimization via the OMMX PySCIPOpt Adapter.

from ommx_pyscipopt_adapter import OMMXPySCIPOptAdapter

# Obtain an ommx.v1.Solution objection through a PySCIPOpt model.
solution = OMMXPySCIPOptAdapter.solve(instance)

The variable solution is an ommx.v1.Solution object that holds the results returned by SCIP.

Analyzing the Results#

From the solution in Step 2, we can check:

  • The optimal solution (which items to pick to maximize total value)

  • The optimal value (maximum total value)

  • The status of constraints (how close we are to the knapsack weight limit)

We can do this with various properties in the ommx.v1.Solution class.

Analyzing the Optimal Solution#

The decision_variables property returns a pandas.DataFrame containing information on each variable, such as ID, type, name, and value:

solution.decision_variables
kind lower upper name subscripts description substituted_value value
id
0 binary 0.0 1.0 x [0] <NA> <NA> 1.0
1 binary 0.0 1.0 x [1] <NA> <NA> 0.0
2 binary 0.0 1.0 x [2] <NA> <NA> 0.0
3 binary 0.0 1.0 x [3] <NA> <NA> 1.0
4 binary 0.0 1.0 x [4] <NA> <NA> 0.0
5 binary 0.0 1.0 x [5] <NA> <NA> 0.0

Using this pandas.DataFrame, for example, you can easily create a table in pandas that shows which items are included in the knapsack.

import pandas as pd

df = solution.decision_variables
pd.DataFrame.from_dict(
    {
        "Item number": df.index,
        "Include in knapsack?": df["value"].apply(lambda x: "Include" if x == 1.0 else "Exclude"),
    }
)
Item number Include in knapsack?
id
0 0 Include
1 1 Exclude
2 2 Exclude
3 3 Include
4 4 Exclude
5 5 Exclude

From this analysis, we see that choosing items 0 and 3 maximizes the total value while satisfying the knapsack’s weight constraint.

Analyzing the Optimal Value#

objective stores the best value found. In this case, it should match the sum of items 0 and 3.

import numpy as np
# The expected value is the sum of the values of items 0 and 3
expected = v[0] + v[3]
assert np.isclose(solution.objective, expected)

Analyzing Constraints#

The constraints property returns a pandas.DataFrame that includes details about each constraint’s equality or inequality, its left-hand-side value ("value"), name, and more.

solution.constraints
equality value used_ids name subscripts description dual_variable removed_reason
id
0 <=0 -1.0 {0, 1, 2, 3, 4, 5} Weight limit [] <NA> <NA> <NA>

Specifically, The "value" is helpful for understanding how much slack remains in each constraint. Here, item 0 weighs \(11\), item 3 weighs \(35\), and the knapsack’s capacity is \(47\). Therefore, for the weight constraint

\[ \begin{align*} \sum_{i=0}^{n-1} w_i x_i - W \leq 0 \end{align*} \]

the left-hand side “value” is \(-1\), indicating there is exactly 1 unit of slack under the capacity.