Volume 10, Number 16, November 2020

Local Branching Strategy-Based Method for the Knapsack Problem with Setup

  Authors

Samah Boukhari¹, Isma Dahmani² and Mhand Hifi³, ¹LaROMaD, USTHB, Algérie, ²AMCD-RO, USTHB, Algerie, ³EPROAD EA4669, UPJV, France

  Abstract

In this paper, we propose to solve the knapsack problem with setups by combining mixed linear relaxation and local branching. The problem with setups can be seen as a generalization of 0–1 knapsack problem, where items belong to disjoint classes (or families) and can be selected only if the corresponding class is activated. The selection of a class involves setup costs and resource consumptions thus affecting both the objective function and the capacity constraint. The mixed linear relaxation can be viewed as driving problem, where it is solved by using a special blackbox solver while the local branching tries to enhance the solutions provided by adding a series of invalid / valid constraints. The performance of the proposed method is evaluated on benchmark instances of the literature and new large-scale instances. Its provided results are compared to those reached by the Cplex solver and the best methods available in the literature. New results have been reached.

  Keywords

Knapsack, Setups, Local Branching, Relaxation.