Add a tutorial about the knapsack problem

[clausia]

Summary

Adds a tutorial about the knapsack problem

Details and comments

[CLAassistant]

All committers have signed the CLA.

[clausia]

Sorry! I saw that it was outdated with respect to the main branch and I told it to merge so that it was up-to-date, and because of that it launched the checks again.

[woodsp-ibm]

Can you please change the heading levels so that only the first heading - the title of the notebook - is a level one heading ie. has one '#'. Other that are now level one like Classical Approach, Quantum Approach, References and Solve with Qiskit could become level 2 ie '##'. When the docs are generated from the html, the level one heading becomes the index link for the tutorial - if we have multiple then it generates multiple entries for the notebook which we don;t want to have.

If you want to look at documentation, as it comes out from the build. where it says 'All checks have passed' click the 'Show all checks' link on the right. Then click on any one of the 'Details' links. Above the main pain showing the detailed information, on the top right, to the left of the 'Re-run all jobs' button you will see 'Artifacts' with a down arrow for the drop down list. At the bottom of the list (you may need to scroll down it) is 'tutorials3.8' entry. Click that to download it and unpack it. In that you will see an index.html and you will see how things look.

And as a question/comment - I looked down the notebook and came to references and thought at first I was at the end of the notebook. Do you think having references in the middle like that is the best place - or maybe move the references to the end of the notebook?

Also I notice some text does not seem to format correctly e.g. since we want their values to be only chosen = :math:1 or not chosen = :math:0, as defined by equation is how it comes out in the html.

[clausia]

Thank you very much for your comments @woodsp-ibm I have placed the references at the end, as you say is the best. I have also fixed the heading levels, as well as the problem of text not being formatted correctly. That 'Artifacts' thing has been very useful, thanks.

[woodsp-ibm]

Hi, looks better. I think there still some minor formatting issues. With bullet lists Sphinx has to have a blank line preceding the list; while it shows as a list when viewing the notebook unfortunately Sphinx sees the text as part of the paragraph and includes it. E.g this at the end of the classical section

Now two possibilities can take place: - Fill wj in the given column. - Do not fill wj in the given column.

where in the notebook itself those are two bullet points after the colon character.

Also in the references in the html I see this. Somehow the first two items have an extra number in them and have lost part of the text (the first initial is 'lost' - which I worked out seems to have been converted to their numeric position in alphabet - H is 8th, S is 19th) not sure why.

compared to what is the notebook

Also I note that the links given for the last two A.Lucas references are identical - I imagine that is an error - I would assume the 2nd should link to some different content

[clausia]

Hi @woodsp-ibm Sorry for all the inconvenience. I have fixed the mentioned issues. Apparently, Sphinx detects "H." as a numbered list (with letters), so it is interpreted with an "8".

[t-imamichi]

Thank you for the detailed tutorial. I have a minor comment.

[t-imamichi]

I notice that "Quantum approach" contains almost same texts of Section 5.2 of Lucas 2019. I think it is beyond citation. Could you rewrite that part by yourself?

Lucas 2019

This PR

Reference

• A. Lucas, Hard combinatorial problems and minor embeddings on lattice graphs, Quantum Information Processing, vol. 18, no. 7, (2019).

[clausia]

Sure! I will do rewrite that part

[t-imamichi]

Could you confirm that the other sections do not contain copies of other papers or articles? Thanks.

[clausia]

Could you confirm that the other sections do not contain copies of other papers or articles? Thanks.

As I remember not, but I will review everything to be sure I will let you know!

[clausia]

Hi @t-imamichi, I'm so sorry for the delay. I have rewritten the section you asked. Regards

[clausia]

Hi @manoelmarques,

Last merge with 'main' branch has provoked an assertion error in tests:

Captured traceback:
~~~~~~~~~~~~~~~~~~~
    Traceback (most recent call last):

      File "D:\a\qiskit-optimization\qiskit-optimization\test\optimization_test_case.py", line 47, in wrapper
    test_item(self, *args)

      File "D:\a\qiskit-optimization\qiskit-optimization\test\algorithms\test_recursive_optimization.py", line 155, in test_recursive_warm_qaoa
    np.testing.assert_array_almost_equal(cplex_result.x, result.x, 4)

      File "c:\miniconda\envs\scsenv\lib\site-packages\numpy\testing\_private\utils.py", line 1046, in assert_array_almost_equal
    assert_array_compare(compare, x, y, err_msg=err_msg, verbose=verbose,

      File "c:\miniconda\envs\scsenv\lib\site-packages\numpy\testing\_private\utils.py", line 844, in assert_array_compare
    raise AssertionError(msg)

    AssertionError: 
Arrays are not almost equal to 4 decimals

And I think this is not affecting the code in this PR, what can I do in order to have all the checks pass?

Thanks in advance

[t-imamichi]

I reran the test and it passed. Windows seems to have have some random problem.

[clausia]

I reran the test and it passed. Windows seems to have have some random problem.

Thank you @t-imamichi

When you have some time, please review my last changes, I hope they are ok, any further changes that should be made I will happily do it

[t-imamichi]

Thank you for the revision. I have two comments. It's nice to mention Lucas' papers in "Quantum approach"; but it is a bit misleading because it is not what Qiskit optimization does. You have examples of Hamiltonian and VQE, but they are not derived using Lucas' approach.

As we wrote in the converter tutorial, we use a generic scheme to convert an optimization problem into a Hamiltonian. We also use a mapping of an integer variable to qubits based on [1] (the paper is also mentioned in the tutorial). [1] "Sahar Karimi, Pooya Ronagh (2017), Practical Integer-to-Binary Mapping for Quantum Annealers. arxiv:1706.01945

So, I would suggest to simplify the "Quantum approach" section mentioning the converter tutorial.

A minor point is the file name. Because the title is "Knapsack problem", it would be consistent to make the file name "12_knapsack_problem.ipynb".

[clausia]

@t-imamichi Thank you very much for your comments, I will update considering your suggestions.

Regarding the file name, I was just trying to follow the convention name of these tutorials:

• 06_examples_max_cut_and_tsp.ipynb, titled as Max-Cut and Traveling Salesman Problem
• 07_examples_vehicle_routing.ipynb, titled as Vehicle Routing

This convention changed?

[t-imamichi]

Sorry. I missed other example tutorials. The current file name is fine. It is consistent with other example tutorials. Thanks!

[coveralls]

Pull Request Test Coverage Report for Build 2265768350

• 0 of 0 changed or added relevant lines in 0 files are covered.
• No unchanged relevant lines lost coverage.
• Overall coverage remained the same at 91.246%

---

Totals
Change from base Build 2263161952:	0.0%
Covered Lines:	4211
Relevant Lines:	4615

---

💛 - Coveralls

[clausia]

The last comments have been addressed, please review when you have a chance.

[clausia]

@t-imamichi, what do you think of the changes?

[t-imamichi]

I found the introduction section of this PR is almost a copy of a textbook "Knapsack Problem". Even if you refer the book, It is definitely unacceptable to copy texts from copyright point of view. I pointed out the problem in the past already. https://github.com/Qiskit/qiskit-optimization/pull/202#issuecomment-886470734 So, I asked whether there is no copy or not and you replied there is no more copy... https://github.com/Qiskit/qiskit-optimization/pull/202#issuecomment-886826210

• Knapsack Problem, Hans Kellerer, Ulrich Pferschy, David Pisinger, https://link.springer.com/book/10.1007/978-3-540-24777-7

---

this PR

textbook

this PR

textbook

this PR

textbook

this PR

textbook

this PR

textbook

this PR

textbook

this PR

textbook

[t-imamichi]

The DP code seems copied from this site and the original code is attributed to a different person "Bhavya Jain". The variable names and the comment are same.

This PR

https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/

[clausia]

I found the introduction section of this PR is almost a copy of a textbook "Knapsack Problem". Even if you refer the book, It is definitely unacceptable to copy texts from copyright point of view. I pointed out the problem in the past already. #202 (comment) So, I asked whether there is no copy or not and you replied there is no more copy... #202 (comment)

• Knapsack Problem, Hans Kellerer, Ulrich Pferschy, David Pisinger, https://link.springer.com/book/10.1007/978-3-540-24777-

@t-imamichi

I'm very sorry, when I answered that I really thought I had solved that, I haven't done this on purpose, I must have been confused, I don't want to justify myself, I just want to try to understand a little what happened.

I'll let you know when it is fixed

I'm really sorry

[t-imamichi]

@clausia Do you have any updates? If not, we will close this PR.

[clausia]

@t-imamichi Hi, thanks for asking, I think it's best to close this PR and open another one when the update is ready