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.File in questo prodotto:
File | Dimensione | Formato | |
---|---|---|---|
Handle-mnlk.pdf
Open Access dal 21/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.