Interval Subset Sum Problem (ISSP)
The Interval Subset Sum Problem (ISSP) is a generalization of the Subset Sum Problem. Given $n$ integer intervals $[l_i, u_i]$ $(0\leq i\leq n-1)$ and an upper bound $T$, the goal is to choose an integer value
\[\begin{aligned} v_i &\in \lbrace 0\rbrace \cup [l_i, u_i] && (i = 0,1,\dots,n-1), \end{aligned}\]so as to satisfy the constraint
\[\begin{aligned} \sum_{i=0}^{n-1} v_i \leq T, \end{aligned}\]and maximize the objective:
\[\begin{aligned} \sum_{i=0}^{n-1} v_i. \end{aligned}\]HUBO formulation of the ISSP
An integer variable can be represented by multiple binary variables using a binary encoding. In PyQBPP, such integer variables can be defined easily using var() with the between= keyword.
Let $v_i$ $(0\leq i\leq n-1)$ be an integer variable that can take a value in $[l_i, u_i]$. We also introduce a binary variable $s_i$ $(0\leq i\leq n-1)$ such that $s_i=1$ if and only if interval $i$ is selected.
To model ISSP, we use the product $s_i v_i$ as the selected value:
\[\begin{aligned} s_iv_i &= 0 && \text{if } s_i= 0\\ &\in [l_i,u_i] && \text{if } s_i= 1 \end{aligned}\]Let
\[\begin{aligned} \text{sum} &= \sum_{i=0}^{n-1} s_i v_i . \end{aligned}\]In PyQBPP, we impose this inequality constraint via a penalty term:
\[\begin{aligned} \text{constraint} &= \bigr(0\leq \sum_{i=0}^{n-1} s_iv_i \leq T\bigl) \end{aligned}\]Since $s_i v_i$ is quadratic in binary variables, $\text{sum}$ is quadratic and $\text{constraint}$ becomes quartic.
Because the ISSP maximizes the sum under the upper bound $T$, we minimize the negative sum:
\[\begin{aligned} \text{objective} &= -\sum_{i=0}^{n-1} s_iv_i \end{aligned}\]Finally, we combine the objective and the constraint penalty into a single HUBO function:
\[\begin{aligned} f &= \text{objective} + P\times\text{constraint}, \end{aligned}\]where $P$ is a sufficiently large constant to prioritize feasibility.
PyQBPP program (HUBO formulation)
The following PyQBPP program solves an ISSP instance with 8 intervals. The lower and upper bounds $[l_i,u_i]$ are stored in the lists lower and upper, and $T=100$.
import pyqbpp as qbpp
lower = qbpp.array([18, 17, 21, 18, 20, 14, 14, 23])
upper = qbpp.array([19, 17, 22, 19, 20, 16, 15, 25])
T = 100
n = len(lower)
v = [qbpp.var(f"v{i}", between=(lower[i], upper[i])) for i in range(n)]
s = qbpp.var("s", shape=n)
total = qbpp.sum(v * s)
constraint = (0 <= total) & (qbpp.same <= T)
f = -total + 1000 * constraint
f.simplify_as_binary()
solver = qbpp.EasySolver(f)
sol = solver.search(target_energy=-T)
for i in range(n):
if sol(s[i]) == 1:
print(f"Interval {i}: val = {sol(v[i])}")
print(f"sum = {sol(total)}")
First, we define a list v of integer variables where each v[i] takes an integer value in [lower[i], upper[i]]. We also define an array s of binary variables, where s[i] = 1 means interval i is selected. The expression total represents $\sum_i v_i s_i$.
The inequality constraint (0 <= total) & (qbpp.same <= T) is stored in constraint. In PyQBPP, such a constraint is internally converted into a nonnegative penalty term that becomes zero when the constraint is satisfied.
Finally, we construct the HUBO objective function f as f = -total + P * constraint (with P = 1000 in this example). Minimizing f therefore maximizes total while heavily penalizing any violation of the constraint.
We set the target energy to -T because if the solver finds a feasible solution with total = T, then the penalty term is zero and the objective term becomes -T, i.e., the global minimum reaches -T.
For the obtained solution, the selected intervals and their values are printed. For example:
Interval 0: val = 18
Interval 1: val = 17
Interval 2: val = 22
Interval 4: val = 20
Interval 7: val = 23
sum = 100
This output confirms that a feasible solution achieving the maximum possible sum ($=T$) was obtained.
QUBO formulation for the ISSP
The HUBO formulation above contains quartic terms because it uses products $s_i v_i$. We can avoid quartic terms by introducing auxiliary integer variables.
Let $a_i$ $(0\leq i\leq n-1)$ be an integer variable that can take a value in $[0,\, u_i-l_i]$. We also use a binary variable $s_i$ $(0\leq i\leq n-1$) such that $s_i=1$ if and only if interval $i$ is selected.
We define
\[\begin{aligned} v_i &= l_is_i + a_i && (0\leq i\leq n-1) \\ \end{aligned}\]To ensure that $v_i$ becomes 0 when $s_i=0$, we add the following penalty term using the negated literal $\overline{s_i}$:
\[\begin{aligned} \text{constraint1} &= \sum_{i=0}^{n-1} \overline{s_i}\,a_i \end{aligned}\]Since $a_i \ge 0$ and $\overline{s_i} \ge 0$, we have $\text{constraint1}\ge 0$. Moreover, $\text{constraint1}=0$ holds if and only if $a_i=0$ whenever $s_i=0$. Therefore, the selected value $v_i$ satisfies
\[\begin{aligned} v_i & = 0 && \text{if } s_i=0,\\ & \in [l_i,u_i] &&\text{if } s_i=1. \end{aligned}\]because $v_i = l_i + a_i$ and $a_i \in [0,u_i-l_i]$ when $s_i=1$.
Let
\[\begin{aligned} \text{sum} &= \sum_{i=0}^{n-1} v_i. \end{aligned}\]The ISSP constraint is:
\[\begin{aligned} \text{constraint2} &= \bigr(0\leq \sum_{i=0}^{n-1} v_i \leq T\bigl) \end{aligned}\]Finally, since ISSP maximizes $\text{sum}$ under the upper bound $T$, we minimize
\[\begin{aligned} \text{objective} &= -\sum_{i=0}^{n-1} v_i \end{aligned}\]Combining the objective and the penalties, we obtain the QUBO expression:
\[\begin{aligned} f &= \text{objective} + P\times(\text{constraint1}+\text{constraint2}), \end{aligned}\]where $P$ is a sufficiently large constant to prioritize feasibility.
PyQBPP program (QUBO formulation)
The following PyQBPP program solves the same ISSP instance using the QUBO formulation:
import pyqbpp as qbpp
lower = qbpp.array([18, 17, 21, 18, 20, 14, 14, 23])
upper = qbpp.array([19, 17, 22, 19, 20, 16, 15, 25])
T = 100
n = len(lower)
a = [qbpp.var(f"a{i}", between=(0, upper[i] - lower[i])) for i in range(n)]
s = qbpp.var("s", shape=n)
v = [s[i] * lower[i] + a[i] for i in range(n)]
total = 0
for i in range(n):
total += v[i]
constraint1 = 0
for i in range(n):
constraint1 += ~s[i] * a[i]
constraint2 = (0 <= total) & (qbpp.same <= T)
f = -total + 1000 * (constraint1 + constraint2)
f.simplify_as_binary()
solver = qbpp.EasySolver(f)
sol = solver.search(target_energy=-T)
for i in range(n):
if sol(s[i]) == 1:
print(f"Interval {i}: val = {sol(v[i])}")
print(f"sum = {sol(total)}")
First, we define a list a of integer variables, where each a[i] takes an integer value in [0, upper[i] - lower[i]]. We also define an array s of binary variables. Using a and s, we construct v[i] = s[i] * lower[i] + a[i], which corresponds to $v_i = s_i l_i + a_i$. The expression constraint1 += ~s[i] * a[i] penalizes any solution with a[i] > 0 when s[i] = 0, thereby enforcing v[i] = 0 for unselected intervals. The inequality constraint constraint2 = (0 <= total) & (qbpp.same <= T) ensures that the total selected sum does not exceed T.
Finally, we minimize f = -total + P * (constraint1 + constraint2) with a sufficiently large penalty constant P. As in the previous example, passing target_energy=-T to search() allows the solver to stop early if it finds a feasible solution achieving total = T (in which case the penalty terms are zero and the objective term becomes -T).
This produces the same result as the HUBO formulation.
Using qbpp.cons() for the constraint
The constraint can also be marked with qbpp.cons(). Starting from the HUBO formulation, the only change is to wrap (0 <= total) & (qbpp.same <= T) in qbpp.cons(). Here total is quadratic (it is $\sum_i s_i v_i$), and qbpp.cons() accepts such a nonlinear constraint body directly, so the auxiliary-variable QUBO reformulation is not needed:
import pyqbpp as qbpp
lower = qbpp.array([18, 17, 21, 18, 20, 14, 14, 23])
upper = qbpp.array([19, 17, 22, 19, 20, 16, 15, 25])
T = 100
n = len(lower)
v = [qbpp.var(f"v{i}", between=(lower[i], upper[i])) for i in range(n)]
s = qbpp.var("s", shape=n)
total = qbpp.sum(v * s)
f = -total + 1000 * qbpp.cons((0 <= total) & (qbpp.same <= T))
f.simplify_as_binary()
solver = qbpp.EasySolver(f)
sol = solver.search(target_energy=-T)
for i in range(n):
if sol(s[i]) == 1:
print(f"Interval {i}: val = {sol(v[i])}")
print(f"sum = {sol(total)}")
The bundled solvers handle (0 <= total) & (qbpp.same <= T) as a constraint. The output is the same, for example:
Interval 0: val = 19
Interval 2: val = 22
Interval 4: val = 20
Interval 6: val = 15
Interval 7: val = 24
sum = 100