The Group Interview Online Knapsack Problem

We address a new generalization of the online knapsack problem (OKP) where a group of items is received each time step. The group interview online knapsack problem (GIOK) is defined as follows. A decision maker is sequentially presented with a group of items and is required to select from among them his best subset to be carried in a limited capacity knapsack. The number of items per group varies from one group to another and is only revealed at arrival. No prior information is available about the potential items (concerning their desirability) until they are received, except of their total number. Each new stage, a new group of items is received and the already inspected groups are recalled and reconsidered in the selection. The selection process is stopped when the knapsack is full. Therefore, a decision rule is required to help the decision maker to identify the best items that maximize his total profit, in an online manner, and without exceeding the capacity of the knapsack. We propose a dynamic programming approach to solve the GIOK in an online fashion. We illustrate the proposed approach by a numerical experimentation and analyze the obtained results.