problem.rst 1.7 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849
  1. 2. Problem instance
  2. ===================
  3. In this tutorial, we introduce the way of using **Macop** and running your algorithm quickly using the well known `knapsack` problem.
  4. 2.1 Problem definition
  5. ~~~~~~~~~~~~~~~~~~~~~~
  6. The **knapsack problem** is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
  7. The image below provides an illustration of the problem:
  8. .. image:: ../_static/documentation/knapsack_problem.png
  9. :width: 300 px
  10. :align: center
  11. In this problem, we try to optimise the value associated with the objects we wish to put in our backpack while respecting the capacity of the bag (weight constraint).
  12. .. warning::
  13. It is a combinatorial and therefore discrete problem. **Macop** decomposes its package into two parts, which is related to discrete optimisation on the one hand, and continuous optimisation on the other hand. This will be detailed later.
  14. 2.2 Problem implementation
  15. ~~~~~~~~~~~~~~~~~~~~~~~~~~~
  16. During the whole tutorial, the example used is based on the previous illustration with:
  17. .. image:: ../_static/documentation/project_knapsack_problem.png
  18. :width: 600 px
  19. :align: center
  20. Hence, we now define our problem in Python:
  21. - values of each objects
  22. - weight associated to each of these objects
  23. .. code-block:: python
  24. """
  25. Problem instance definition
  26. """
  27. elements_score = [ 4, 2, 10, 1, 2 ] # value of each object
  28. elements_weight = [ 12, 1, 4, 1, 2 ] # weight of each object
  29. Once we have defined the instance of our problem, we will need to define the representation of a solution to that problem.