.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "generated/tutorials/knapsack.py"
.. LINE NUMBERS ARE GIVEN BELOW.

.. only:: html

    .. note::
        :class: sphx-glr-download-link-note

        :ref:`Go to the end <sphx_glr_download_generated_tutorials_knapsack.py>`
        to download the full example code.

.. rst-class:: sphx-glr-example-title

.. _sphx_glr_generated_tutorials_knapsack.py:


The knapsack problem
====================

This tutorial demonstrates how to formulate and solve a binary integer linear
program with JuMPy. Given a collection of items and a capacity, we choose the
items with the greatest combined profit whose combined weight fits within the
capacity.

This is a Python translation and adaptation of JuMP's
`knapsack tutorial <https://github.com/jump-dev/JuMP.jl/blob/b1888e6e9e6f07b03529340216fc07ba95f91fd5/docs/src/tutorials/linear/knapsack.jl>`_.
The original tutorial was adapted to the current JuMPy API and its compiled
HiGHS backend.

The model is

.. math::

   \begin{aligned}
   \max \quad & \sum_{i=1}^n c_i x_i \\
   \text{s.t.} \quad & \sum_{i=1}^n w_i x_i \leq C, \\
   & x_i \in \{0, 1\}, \quad i = 1, \ldots, n,
   \end{aligned}

where :math:`C` is the capacity and item :math:`i` has profit :math:`c_i` and
weight :math:`w_i`.

.. GENERATED FROM PYTHON SOURCE LINES 33-73




.. rst-class:: sphx-glr-script-out

 .. code-block:: none

    Chosen item indices: [0, 3, 4]
    Total profit: 16.0






|

.. code-block:: Python


    import jumpy as jp

    # Data
    # ----
    #
    # Our example has five items and a capacity of 10 units.

    profit = [5.0, 3.0, 2.0, 7.0, 4.0]
    weight = [2.0, 8.0, 4.0, 2.0, 5.0]
    capacity = 10.0
    n = len(weight)

    # Formulation
    # -----------
    #
    # A binary variable records whether each item is selected.

    model = jp.Model()
    x = model.variables(n, binary=True, name="x")

    # JuMPy expressions use ordinary Python arithmetic. Here, ``sum`` constructs
    # the capacity constraint and objective one term at a time.

    model.constraint(sum(weight[i] * x[i] for i in range(n)) <= capacity)
    model.objective = jp.maximize(sum(profit[i] * x[i] for i in range(n)))

    # Solution
    # --------

    model.optimize()
    items_chosen = [i for i in range(n) if model.value(x[i]) > 0.5]
    total_profit = sum(profit[i] for i in items_chosen)

    print(f"Chosen item indices: {items_chosen}")
    print(f"Total profit: {total_profit}")

    # The assertions below are executed when the script or documentation runs, but
    # they are removed from the rendered tutorial.



.. rst-class:: sphx-glr-timing

   **Total running time of the script:** (0 minutes 0.388 seconds)


.. _sphx_glr_download_generated_tutorials_knapsack.py:

.. only:: html

  .. container:: sphx-glr-footer sphx-glr-footer-example

    .. container:: sphx-glr-download sphx-glr-download-jupyter

      :download:`Download Jupyter notebook: knapsack.ipynb <knapsack.ipynb>`

    .. container:: sphx-glr-download sphx-glr-download-python

      :download:`Download Python source code: knapsack.py <knapsack.py>`

    .. container:: sphx-glr-download sphx-glr-download-zip

      :download:`Download zipped: knapsack.zip <knapsack.zip>`


.. only:: html

 .. rst-class:: sphx-glr-signature

    `Gallery generated by Sphinx-Gallery <https://sphinx-gallery.github.io>`_