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
Mencarelli L.
2018-01-01
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:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.