Effect of Valid Cardinality Constraints in Local Branching: The Case of the Knapsack Problem with Setup

S.Boukhari, I.Dahmani and M.Hifi

Abstract


In this paper, we study the effect of the cardinality constraint when injected into an iterative local branching-based method, especially when tackling the knapsack problem with setup. The designed method is based upon three features: (i) solving a series of mixed linear relaxations, (ii) inducing valid cardinality constraints around some decision variables and,(iii) introducing the local branching strategy for intensifying the search process. First, the mixed linear relaxation can be viewed as driving problem, where it is solved by applying a special black-box solver. Second, the valid cardinality constraints are built according to some favored variables for tightening both lower and upper bounds. Third, the local branching is applied for iteratively intensifying and enhancing the solutions at hand. The performance of the proposed method is evaluated on benchmark instances of the literature, where its achieved results are compared to those reached by the state-of-the-art Cplex solver and the best methods available in the literature. Encouraging results have been obtained.

Keywords


Cardinality constraints, Knapsack, Local Branching, Relaxation.

References


Md-M. Akbar, MS. Rahman, M. Kaykobad, EG. Manning, GC. Shoja, (2006) “Solving the Multidimensional Multiple-choice Knapsack Problem by constructing convex hulls”, Computers and Operations Research, Vol. 33(3), pp. 1259-1273.

U. Akinc, (2006) “Approximate and exact algorithms for the fixed-charge knapsack problem”, European Journal of Operational Research, Vol. 170, No 2, pp 363-375.

N. Altay, JR. Robinson, E. Powell, and K. M. Bretthauer, (2008) “Exact and heuristic solution approaches for the mixed integer setup knapsack problem”, European Journal of Operational Research, Vol. 190, No 3, pp 598-609.

A. Amiri, (2019) “A Lagrangean based solution algorithm for the knapsack problem with setups”, Expert Systems with Applications, Vol. 143, pp113077.

S. Boukhari, I. Dahmani and M. Hifi, (2020) “Local branching strategy-based method for the knapsack problem with setup”, David C. Wyld et al. (Eds), Proceedings of the 4th International Conference on Artificial Intelligence, Soft Computing And Applications, pp. 65-75, CS & IT - CSCP 2020 (DOI: 10.5121/csit.2020.101606)

K. Chebil, and M. Khemakhem, (2015) “A dynamic programming algorithm for the knapsack problem with setup”, Computers and Operations Research, Vol. 64, pp 40-50.

K. Chebil and M. Khemakhem, (2016) “A tree search based combination heuristic for the knapsack problem with setup”, Computers and Industrial Engineering, Vol. 99, pp 280-286.

K. Chebil, R. Lahyani, M. Khemakhem, and L. C. Coelho, (2019) “Matheuristics for solving the Multiple Knapsack Problem with Setup”, Computers and Industrial Engineering, Vol. 129, pp 76-89.

C.F. Della, , F. Salassa, and R. Scatamacchia, (2017) “An exact approach for the 0-1 knapsack problem with setups”, Computers and Operations Research, Vol. 80, pp 61-67.

M. Fischetti and A.Lodi , (2003) “Local branching, Mathematical Programming”, Vol. 98, pp. 23{47.

F. Furini, M. Monaci and E. Traversi, (2017) “Exact algorithms for the knapsack problem with setup”, Technical report, Université Paris Dauphine.

A. Grange, I. Kacem and S. Martin, (2019) “Algorithms for the bin packing problem with overlapping items”, Computers and Industrial Engineering, Vol. 115", pp. 331-341.

M. Guignard, (1993) “Solving makespan minimization problems with lagrangean decomposition”, Discrete Applied Mathematics, Vol. 42, no 1, pp. 17-29.

M. Hifi, and L. Yousef, (2019) “A local search-based method for sphere packig problems”, European Journal of Operational Research, Vol. 274(2), pp. 482-500.

M. Merkle and M. Hellma, (1978) “Hiding information and signatures in trapdoor knapsacks”, IEEE Transactions on Information Theory, Vol. 24(5), pp. 525—530.

S. Michel, N. Perrot, and F. Vanderbeck, (2017) “Knapsack problems with setups”, European Journal of Operational Research, Vol. 196, no 3, pp. 909-918.

U. Pferschy,R. Scatamacchia, (2018) “Improved dynamic programming and approximation results for the knapsack problem with setups”, International Transactions in Operational Research, Vol. 25, no 2, pp. 667-682.

L.F. Plata-Gonzalez, I. Amaya, JC. Ortiz-Bayliss, SE. Conant-Pablos, H. Terashima-Marin and CA. Coello-Coello, (2019) “Evolutionary-based tailoring of synthetic instances for the Knapsack problem”, Soft Computin, Vol. 23, pp. 12711-12728.

G. Perboli, L. Gobbato and F. Perfetti, (2014) “Packing problems in transportation and supply chain: new problems and trends”, Procedia - Social and Behavioral Sciences, Vol. 111, pp. 672—681.


Full Text: PDF

Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.

IT in Innovation IT in Business IT in Engineering IT in Health IT in Science IT in Design IT in Fashion

IT in Industry @ http://www.it-in-industry.com . ISSN (Online): 2203-1731; ISSN (Print): 2204-0595