problem.rst 1.6 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647
  1. 2. Problem instance
  2. ===================
  3. In this tutorial, we introduce the way of using `macop` and running your algorithm quickly using a well the 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. 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.
  13. 2.2 Problem implementation
  14. ~~~~~~~~~~~~~~~~~~~~~~~~~~~
  15. Hence, we define our problem in Python:
  16. - values of each objects
  17. - weight associated to each of these objects
  18. .. code:: python
  19. """
  20. imports part
  21. """
  22. import random
  23. """
  24. Problem definition
  25. """
  26. random.seed(42)
  27. elements_score = [ random.randint(1, 20) for _ in range(30) ] # value of each object
  28. elements_weight = [ random.randint(5, 25) for _ in range(30) ] # 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.