knapsack.md

Application to a multiple knapsack problem

This page describes the multiple knapsack problem considered in the folder src/examples/knapsack.

Problem definition

This problem considers knapsack of capacity and objects. Each object has a weight and a value . The objective is to assign objects to knapsacks such that the value of the objects in the knapsack is maximal and that the sum of the weights of the objects in each knapsack does not exceed . This can be modelled by an ILP in which binary variable is equal to if and only if object is in knapsack :

Resolution methods considered

In this example, we consider two heuristic resolution methods:

• heuristique : randomly add objects to random knapsacks ;

• heuristique : sort the objects by decreasing ratio and add objects to one of the fullest knapsack.