Knapsack problems with setup

Abstract

This research studies three integer programming models which can be applied to order acceptance in make-to-order manufacturing or regional project selection in multiple periods. All three models are the variations of the binary knapsack problems and they are called the knapsack problem with setup (KPS), the multiple knapsacks problem with setup (MKPS) and the multiple-choice knapsack problem with setup (MCKS), respectively. In all three models, jobs belong to different families and some variables represent setup for a family of jobs: if a setup is not done, no jobs in this family can be processed; if two jobs are processed sequentially, no setup is required. Branch-and-bound algorithms are used to obtain the optimal solutions to all three models. Setup variables are branched on. After all setup variables are fixed, the models are transformed to a (several) knapsack problem(s). For each model, an independent linear knapsack problem is developed to give an upper bound. When a setup variable is fixed during branching, we update certain variables in the linear knapsack problem. The optimal objective of the updated linear knapsack problem is an upper bound on the generated sub-problem. The rounded LP solution of the linear knapsack problem for KPS or MCKS corresponds to an incumbent of KPS or MCKS. A greedy algorithm is developed to obtain a lower bound on MKPS. Computational experiments show the effectiveness of these algorithms.