.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "api/gallery/optimization/linear_programming/plot_02_branch_and_bound.py"
.. LINE NUMBERS ARE GIVEN BELOW.

.. only:: html

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

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

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

.. _sphx_glr_api_gallery_optimization_linear_programming_plot_02_branch_and_bound.py:


Branch and bound: integer versus relaxed optimum
======================================================

The LP relaxation of an integer program can have a fractional optimum
that rounding does not repair. Branch and bound (Land and Doig, 1960)
finds the true integer optimum; here it is at a different vertex from
the relaxation's.

.. GENERATED FROM PYTHON SOURCE LINES 12-17

.. code-block:: Python

    import matplotlib.pyplot as plt
    import numpy as np

    from mathematicskit.optimization import integer_linear_program, linear_program








.. GENERATED FROM PYTHON SOURCE LINES 18-20

maximize 5x + 4y s.t. 6x + 4y <= 24, x + 2y <= 6
-----------------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 20-30

.. code-block:: Python


    c = np.array([-5.0, -4.0])
    a_ub = np.array([[6.0, 4.0], [1.0, 2.0]])
    b_ub = np.array([24.0, 6.0])
    relaxed = linear_program(c, a_ub=a_ub, b_ub=b_ub)
    integer = integer_linear_program(c, a_ub=a_ub, b_ub=b_ub)
    print(f"LP relaxation: x = {relaxed.x}, objective {-relaxed.fun:.2f}")
    print(f"integer optimum: x = {integer.x.round() + 0.0}, objective {-integer.fun:.2f}")
    print(f"rounding the relaxation down gives {np.floor(relaxed.x)}, objective {5 * np.floor(relaxed.x[0]) + 4 * np.floor(relaxed.x[1]):.2f}")





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

 .. code-block:: none

    LP relaxation: x = [3.  1.5], objective 21.00
    integer optimum: x = [4. 0.], objective 20.00
    rounding the relaxation down gives [3. 1.], objective 19.00




.. GENERATED FROM PYTHON SOURCE LINES 31-33

Feasible region and lattice points
-----------------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 33-45

.. code-block:: Python


    fig, ax = plt.subplots()
    ax.fill([0, 4, 3, 0], [0, 0, 1.5, 3], color="0.9", label="LP feasible region")
    gx, gy = np.meshgrid(np.arange(5), np.arange(4))
    feasible = (6 * gx + 4 * gy <= 24) & (gx + 2 * gy <= 6)
    ax.plot(gx[feasible], gy[feasible], "k.", label="integer feasible points")
    ax.plot(*relaxed.x, "s", color="tab:blue", ms=9, label="LP optimum")
    ax.plot(*integer.x, "*", color="tab:red", ms=14, label="integer optimum")
    ax.set_xlabel("x")
    ax.set_ylabel("y")
    ax.legend()
    ax.set_title("Integer programming by branch and bound (Land & Doig, 1960)")



.. image-sg:: /api/gallery/optimization/linear_programming/images/sphx_glr_plot_02_branch_and_bound_001.png
   :alt: Integer programming by branch and bound (Land & Doig, 1960)
   :srcset: /api/gallery/optimization/linear_programming/images/sphx_glr_plot_02_branch_and_bound_001.png
   :class: sphx-glr-single-img


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

 .. code-block:: none


    Text(0.5, 1.0, 'Integer programming by branch and bound (Land & Doig, 1960)')




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

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


.. _sphx_glr_download_api_gallery_optimization_linear_programming_plot_02_branch_and_bound.py:

.. only:: html

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

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

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

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

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

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

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


.. only:: html

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

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