We consider the multiple non-linear knapsack problem with separable non-convex functions. The problem, which can be modeled as a (mixed) integer non-linear program, is extremely difficult to solve in practice. We present a fast heuristic algorithm, based on constructive techniques, surrogate relaxations, and local search improvements. Computational comparisons with exact and heuristic methods for general non-convex mixed integer non-linear programs show that the proposed approach provides good-quality solutions within small computing times.

Relaxations and heuristics for the multiple non-linear separable knapsack problem

Martello, Silvano;
2018

Abstract

We consider the multiple non-linear knapsack problem with separable non-convex functions. The problem, which can be modeled as a (mixed) integer non-linear program, is extremely difficult to solve in practice. We present a fast heuristic algorithm, based on constructive techniques, surrogate relaxations, and local search improvements. Computational comparisons with exact and heuristic methods for general non-convex mixed integer non-linear programs show that the proposed approach provides good-quality solutions within small computing times.
D'Ambrosio, Claudia; Martello, Silvano*; Mencarelli, Luca
File in questo prodotto:
File Dimensione Formato  
Handle-mnlk.pdf

embargo fino al 20/12/2020

Tipo: Postprint
Licenza: Licenza per Accesso Aperto. Creative Commons Attribuzione - Non commerciale - Non opere derivate (CCBYNCND)
Dimensione 738.49 kB
Formato Adobe PDF
738.49 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11585/683155
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 8
social impact