Knapsack Problem

[Kashyapaman2812]

Hi everyone,
I was trying to solve Knapsack Problem using SB Algorithm, but I came across one issue that how exactly are we supposed to handle inequality integer constraints in Ising Formulation. And upon reference from Lucas' paper, I got an idea that slack variable might be a way to go. But then how do we handle 2 binary variables (Xi [Knapsack Variable] and Yi [Slack Variable]). I tried to follow your code, but it is not very clear from it that what method was employed to solve the Knapsack.

Any comments or help is welcomed.

[BusyBeaver-42]

Hi there,

Thank you for reaching out. The $y_i$ variables correspond to ancillary spins, they are not slack variables as in the context of constrained continuous optimization.

In the context of reframing combinatorial optimization problems into Ising models, ancillary spins are additional spins introduced to embed interractions that would require terms of degree higher than 2.

Here is the interpration of the hamiltonian $H = H_A + H_B$ in Lucas' paper. $H_B$ is the quantity you want to minimize (the opposite of the cost). $H_A$ is such that it is minimal if and only if the constraints are satisfied. By setting $A$ to a large enough value (compared to $B$), you can achieve: ($H$ is minimized) $\implies$ ($H_A$ is minimized). The interpretation is that violating the constraints gives you a penalty stricly larger than any benefit you can gain from it. Minimizing $H$ implies that you are minimizing $H_B$ over the spin vectors which satisfies the constraints.

Note: SB is an approximation algorithm so the output does not necessarily achieve the minimal energy. Since the constraints are embedded by ensuring that the energy of a spin vector violating the constraints cannot be minimal, the output can still violate the constraints.

I am not really sure I understood your question properly, please let me know if you need further explanations.

[Kashyapaman2812]

Hi, thanks for replying.
Actually, I got the idea how exactly Lucas is trying to formulate the Ising Model of the Knapsack Problem and I also understood that Yi is an auxiliary spin (not particularly slack variable). But as far as I understand the Simulated Bifurcation Algorithm, let's say we have 6 objects (represented by Xi), out of which we need some to pack into the Knapsack. So, we map these objects to Kerr Oscillators and the sign of displacement gives us the answer whether it is included (+1) or not (-1) in the knapsack. Now, what I am not able to follow is that here we have two types of binary variables (Xi and Yi), in such a case how will we frame our interaction matrix and bias matrix (in reference to your code, 'matrix' and 'vector'). I am not able to get the intuition for this. How are these 2 binary variables being mapped to the idea of oscillators?
I would be gratefully if you can clarify this doubt of mine.

[BusyBeaver-42]

Oh I understand the question now. You just put everything in the same vector and matrix and read the output only at locations corresponding to $X$.

For instance, let's say you pack your variable spins and your ancillary spins in a vector as follows.

$$V = \begin{pmatrix} X \\ Y \end{pmatrix}$$

Let $A$ be the matrix embedding the interactions between your variable spins, let $B$ be the matrix embedding the interactions between your ancillary spins, let $C$ be the matrix embedding the interactions between your variable spins and your ancillary spins, and let $C_1$, $C_2$ be two matrices such that $C = C_1 + C_2$. Usually $C_2 = 0$ or $C_2 = C_1$ depending on what is the easiest to generate. Then your matrix looks like that (it is a block matrix).

$$\begin{pmatrix} A & C_1 \\\ {C_2}^T & B \end{pmatrix}$$

[Kashyapaman2812]

Hi @BusyBeaver-42 , Thanks for the reply, now I have better idea about the implementation. Thanks.

[bqth29]

Hi @Kashyapaman2812,

Here is a quick note in addition to @BusyBeaver-42's answer.

About Lucas' paper

In the case of the Knapsack problem, the $y_i$'s variables are introduced to model all the reachable total weights of the knapsack. Say the maximum weight you allow is 5 and that all your items have an integer weight, then all the admissible combinations of items will have a cumulated weights of 0, 1, 2, 3, 4 or 5. The goal here is to ensure that only one of these reachable weights is actually reached (your knapsack cannot have to different weights at once) and that this weight is exactly equal to the sum of the weights of the items you picked.

In the following, we denote the weights of the items $w_\alpha$ and their costs $c_\alpha$ as in Lucas' paper. The $x_\alpha$ are binary variables which indicate whether the item $\alpha$ is picked.

Thus, we need to introduce 6 ancillary binary variables $y_0$ to $y_5$ and add two constraints in the definition of $H_A$:

1. $H_{\mbox{one weight}} = \left (1 - \sum y_i \right ) ^ 2$ which is null if and only if only one $y_i$ is 1 (and the others are all 0)
2. $H_{\mbox{coherent total weight}} = \left (\sum i y_i - \sum w_\alpha x_\alpha \right ) ^ 2$ which is null if and only if the total weight in the knapsack ($\sum w_\alpha x_\alpha$) is exactly the weight intrinsically carried by the only $y_i$ selected ($\sum i y_i$)

Then, setting $H_A = A \times (H_{\mbox{one weight}} + H_{\mbox{coherent total weight}})$, you can embed both constraints in one Hamiltonian. Besides, by choosing $A > \sum c_\alpha$ (the highest value of the objective function) and $B = 1$, you ensure that:

• either $H_A$ is null and thus your total Hamiltonian $H = H_A + H_B$ is negative which means that SB has found a valid solution for the problem (it may not be the best though)
• either at least one constraint is violated and thus your total Hamiltonian $H$ is positive because $H_A$'s penalty is bigger than any value (in absolute value) that $H_B$ can have

A good way to know if the solution found by SB is admissible is to check whether the objective function is negative (success) or positive (fail).

Knapsack problem implementation

The good news is that the Integer-Weights Knapsack problem is already implemented in the repository. It is not part of the last PyPI release (1.2.0) because it was added pretty recently. If you wish to use our implementation, please consider downloading the dev version of SB with pip install git+https://github.com/bqth29/simulated-bifurcation-algorithm.git.

Then, you can use the Knapsack model from the simulated_bifurcation.models module:

from simulated_bifurcation.models import Knapsack

knapsack_problem = Knapsack(weights=[5, 2, 3, 4, 8, 1], costs=[4, 12, 3, 4, 15, 5], max_weight=10)
knapsack_problem.minimize() # We seek to minimize the Ising energy of the Lucas' Knapsack Hamiltonian

print(knapsack_problem.summary)

Running this code snippet on my computer I got {'items': [0, 1, 5], 'total_cost': 21.0, 'total_weight': 8.0, 'status': 'success'} which you may interpret as follow:

• you need to take the first, second and sixth items with respective weights 5, 2 and 1 and respective costs 4, 12 and 5
• their cumulated weight is 15
• their cumulated cost is 8
• the success status indicates that no constraint is violated so the solution is valid

I hope this answer helped you. Please feel free to ask any further question and we will be happy to help.

[Kashyapaman2812]

Hi @bqth29,
Thanks for replying. I have mentioned my confusion in the above comment please have a look. Hope what I am trying to understand makes sense. It would be great if you could help me in that regard.

[Kashyapaman2812]

Hi @bqth29 ,
Thanks for the reply the formulation is now clear to me. But I would like to point out that when I tried running the code you mentioned in the above comment it throws an error. Maybe, there is some issue, or maybe I only did something wrong. Please have a look and I will also try again.

[bqth29]

Hi @Kashyapaman2812 ,

The Knapsack class of sb.models starts with an upper-cased K. I think you wrote it with a lower-cased K in your code. Try replacing knapsack(weights=... by Knapsack(weights=... and it should work.

Otherwise tell me and I will investigate this problem with more attention.

All the best

[Kashyapaman2812]

Hi @bqth29 ,

I reverified my implementation, but still looks like something is missing in the main code. Please have a look.

[bqth29]

Hi @Kashyapaman2812,

I understand what is happening. The code snippet I wrote was using the package's version of the main branch of this repository (1.2.1.dev0) instead of the PyPI version (1.2.0).

In the PyPI version, some new features of the Knpasack model are missing (like the summary property to display the optimization results). Besides, the math definition we used for the model had an ill-defined coefficient which led to incorrect results (this is why we fixed this with PR #29).

I see 3 ways for you to overcome the problem:

1. Install the main branch version with pip:

pip install git+https://github.com/bqth29/simulated-bifurcation-algorithm.git

2. Copy the code snippet to a Google Colab notebook and add the following command in the top cell to install the main branch version:

!pip install git+https://github.com/bqth29/simulated-bifurcation-algorithm.git

(besides, thanks to Google Colab, you can run SB on GPUs which is pretty awesome for big instances)
3. Wait for version 1.2.1 that should be released within two weeks and which will have the latest updates on the Knapsack model among other fixes

Option 1 is the easiest workaround if your pip version allows downloads from Git repositories directly.

I hope this could help 😄