Bio

Xavier Roy is a theoretical physicist. During his PhD and postdoc, he developed several mathematical models, algorithms and numerical simulations to describe and study perturbations in cosmology and the evolution of the universe.

Project: The knapsack problem

The knapsack problem is a linear problem of combinatory optimization with constraints.

Given a set of n elements i of profits and costs c_i, it consists in finding the solutions x_i (the number of copies) that maximize the objective function ∑ p_i x_i while satisfying the constraint ∑ c_i x_i ⩽ C, with C a given parameter.

The 0-1 knapsack problem restricts the number of copies to 1 (an item i can be either picked (x_i = 1) or not (x_i = 0)), the bounded knapsack allows for a number of n_c copies and the unbounded version for an unlimited number of copies.

Other possible extensions consider multiple objective functions ∑ p_i x_i → ∑ p _ij x_i), multiple constraints ( ∑ c_i x_i ⩽ C → ∑ c_ij x_i ⩽ C_j) or combination of them.

The aim of the project is to explore the knapsack problem, implement in Mathematica an algorithm to solve it efficiently and define a user-friendly function from it.

References

• Pisinger, D. (1995). Algorithms for Knapsack Problems. Thesis. University of Copenhagen.
• Knapsack Problem. (n.d.). In Wikipedia.