We consider the nonlinear knapsack problem with separable nonconvex functions. Depending on the assumption on the integrality of the variables, this problem can be modeled as a nonlinear programming or as a (mixed) integer nonlinear programming problem. In both cases, this class of problems is very difficult to solve, both from a theoretical and a practical viewpoint. We propose a fast heuristic algorithm, and a local search post-optimization procedure. A series of computational comparisons with a heuristic method for general nonconvex mixed integer nonlinear programming and with global optimization methods shows that the proposed algorithms provide high-quality solutions within very short computing times.

C. D'Ambrosio, S. Martello (2011). Heuristic algorithms for the general nonlinear separable knapsack problems,. COMPUTERS & OPERATIONS RESEARCH, 38, 505-513 [10.1016/j.cor.2010.07.010].

Heuristic algorithms for the general nonlinear separable knapsack problems,

D'AMBROSIO, CLAUDIA;MARTELLO, SILVANO
2011

Abstract

We consider the nonlinear knapsack problem with separable nonconvex functions. Depending on the assumption on the integrality of the variables, this problem can be modeled as a nonlinear programming or as a (mixed) integer nonlinear programming problem. In both cases, this class of problems is very difficult to solve, both from a theoretical and a practical viewpoint. We propose a fast heuristic algorithm, and a local search post-optimization procedure. A series of computational comparisons with a heuristic method for general nonconvex mixed integer nonlinear programming and with global optimization methods shows that the proposed algorithms provide high-quality solutions within very short computing times.
2011
C. D'Ambrosio, S. Martello (2011). Heuristic algorithms for the general nonlinear separable knapsack problems,. COMPUTERS & OPERATIONS RESEARCH, 38, 505-513 [10.1016/j.cor.2010.07.010].
C. D'Ambrosio; S. Martello
File in questo prodotto:
Eventuali allegati, non sono esposti

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: https://hdl.handle.net/11585/103861
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 14
  • ???jsp.display-item.citation.isi??? 13
social impact