# Genetic Algorithm for the Retailers' Shelf Space Allocation Profit Maximization Problem
## 5 Genetic Algorithm
### Pallet Solution Recursion  
The products that must be placed on a pallet shelf cannot be allocated to the other shelves, so there is only one shelf available for the pallet products. Allocating products to this pallet shelf corresponds to selecting items in a knapsack problem. In knapsack problems, a subset of items is chosen, each of which is characterized by a specific weight and value so that the resultant total value is maximized without exceeding the capacity of the knapsack. In other words, the total weight of selected items must not exceed the predefined capacity of the knapsack. Even the simplest discrete model is binary NP-hard. Most of the Knapsack problems considered are key pseudo-polynomially solvable [40].  
In our case, each product has its facing width (weight) and the unit profit (value) achieved after selling this product. The shelf length represents the related weight limit of the knapsack. Because of this, we implemented a knapsack-like algorithm for the pallet. Dynamic programming is one of the exact methods for solving the knapsack problem.  
We implemented a recursive algorithm that solved the classical knapsack problem with the shelf length constraint and then stored the values in an auxiliary table. The auxiliary table has a number of rows equal to the number of products and a number of columns equal to shelf length (i.e., different size values from 0 to maximum shelf length with step 1). The table models the situation when the knapsack is empty, with 0 size and the bottom-right cell models the situation when the knapsack size is the maximum possible, and it is full of items so that there is no free space on the shelf.  
In the next step, we added the constraints of a limited number of facings (14) and (15). Next, we added grouping possibilities, i.e., if products are only represented by facings, or facings and cappings, or facings and nestings, and added the constraints (16)-(19). Adding a group of facings with cappings, and facings with nestings, models the situation when there is a \"bonus\" if we select more of the same products, i.e., when we add capping or nesting, the knapsack capacity is not reduced, but the profit is increased. Evidently, constraints (11) and (12) are satisfied because we have only one shelf for pallet type products. Constraint (13), which restricts the supply limit of the products, can also be recalculated into the notion of facings, facings and cappings, and facings and nestings. There are no virtual segments on a pallet, so it is not necessary to add virtual segment constraints here. This finishes our dynamic programming algorithm section.  
In this study, the pallet has more constraints than the general knapsack. We added the shelf weight limit constraint to the recursive algorithm proportionally to each value of the shelf length. After including the shelf height constraint (2), the subset of items represented by facings, facings and cappings, and facings and nestings was recalculated. Obviously, the constraint (2) can be implemented more easily. All pallet products must be placed on a pallet. The facings number never equals 0, so there is no need to write the omitting division by 0 constructions. To save time, we subtract from the item set all lower bound values for placing them on a shelf, we reduce the shelf size (length and weight), and process only the remaining size of the shelf as the knapsack capacity. So, at this point, the auxiliary table does not represent all length and weight parameters, groups of facings, cappings or nestings. This algorithm solves the pallet part of the main problem very fast, but the solution may be not optimal. For this reason, the list algorithms are implemented on a pallet, generating a set of different solutions (they are fast enough), and a pallet also takes part in the crossover procedure. There are separate crossover methods for pallet solutions and for regular shelves.