Piecewise convex maximization approach to multiknapsack

Abstract

We refine the reverse convex approach to binary programs into a piecewise convex maximization problem with only two pieces. As a vital lead, we address the multiknapsack problem. The results of computational experiments are presented in contrast with the best known solutions found by heuristics and by the reverse convex approach.

Keywords:

• combinatorial optimization
• knapsack
• local search
• nonconvex and nonsmooth problem
• piecewise convex

AMS Subject Classifications::

• 90C09
• 90C26
• 90C27
• 90C47