Heuristics for the General Multiple Non-linear Knapsack Problem

Luca Mencarelli; Claudia D'Ambrosio; Angelo Di Zio; Silvano Martello

doi:10.1016/j.endm.2016.10.018

Heuristics for the General Multiple Non-linear Knapsack Problem

Luca Mencarelli
, Claudia D'Ambrosio
, Angelo Di Zio
, Silvano Martello

Laboratoire d'Informatique (LIX)
Chemin de la Malmaison
DEI “Guglielmo Marconi”

Research output: Contribution to journal › Article › peer-review

3 Citations (Scopus)

Abstract

We propose heuristic algorithms for the multiple non-linear knapsack problem with separable non-convex profit and weight functions. First, we design a fast constructive algorithm that provides good initial solutions. Secondly, we improve the quality of these solutions through local search procedures. We compare the proposed methods with exact and heuristic algorithms for mixed integer non-linear programming problems, proving that our approach provides good-quality solutions in smaller CPU time.

Original language	English
Pages (from-to)	69-72
Number of pages	4
Journal	Electronic Notes in Discrete Mathematics
Volume	55
DOIs	https://doi.org/10.1016/j.endm.2016.10.018
Publication status	Published - 1 Nov 2016

Keywords

Heuristic algorithm
Local search
Mixed-integer non-linear programming
Multiple non-linear knapsack problem

Access to Document

10.1016/j.endm.2016.10.018

Cite this

@article{718b51d786954e169a0d810ee4e69a9b,

title = "Heuristics for the General Multiple Non-linear Knapsack Problem",

abstract = "We propose heuristic algorithms for the multiple non-linear knapsack problem with separable non-convex profit and weight functions. First, we design a fast constructive algorithm that provides good initial solutions. Secondly, we improve the quality of these solutions through local search procedures. We compare the proposed methods with exact and heuristic algorithms for mixed integer non-linear programming problems, proving that our approach provides good-quality solutions in smaller CPU time.",

keywords = "Heuristic algorithm, Local search, Mixed-integer non-linear programming, Multiple non-linear knapsack problem",

author = "Luca Mencarelli and Claudia D'Ambrosio and \{Di Zio\}, Angelo and Silvano Martello",

note = "Publisher Copyright: {\textcopyright} 2016 Elsevier B.V.",

year = "2016",

month = nov,

day = "1",

doi = "10.1016/j.endm.2016.10.018",

language = "English",

volume = "55",

pages = "69--72",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Heuristics for the General Multiple Non-linear Knapsack Problem

AU - Mencarelli, Luca

AU - D'Ambrosio, Claudia

AU - Di Zio, Angelo

AU - Martello, Silvano

PY - 2016/11/1

Y1 - 2016/11/1

N2 - We propose heuristic algorithms for the multiple non-linear knapsack problem with separable non-convex profit and weight functions. First, we design a fast constructive algorithm that provides good initial solutions. Secondly, we improve the quality of these solutions through local search procedures. We compare the proposed methods with exact and heuristic algorithms for mixed integer non-linear programming problems, proving that our approach provides good-quality solutions in smaller CPU time.

AB - We propose heuristic algorithms for the multiple non-linear knapsack problem with separable non-convex profit and weight functions. First, we design a fast constructive algorithm that provides good initial solutions. Secondly, we improve the quality of these solutions through local search procedures. We compare the proposed methods with exact and heuristic algorithms for mixed integer non-linear programming problems, proving that our approach provides good-quality solutions in smaller CPU time.

KW - Heuristic algorithm

KW - Local search

KW - Mixed-integer non-linear programming

KW - Multiple non-linear knapsack problem

U2 - 10.1016/j.endm.2016.10.018

DO - 10.1016/j.endm.2016.10.018

M3 - Article

AN - SCOPUS:84995642312

SN - 1571-0653

VL - 55

SP - 69

EP - 72

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

ER -

Heuristics for the General Multiple Non-linear Knapsack Problem

Abstract

Keywords

Access to Document

Fingerprint

Cite this