Optimization Online


Integer Optimization with Penalized Fractional Values: The Knapsack Case

Enrico Malaguti(enrico.malaguti***at***unibo.it)
Michele Monaci(michele.monaci***at***unibo.it)
Paolo Paronuzzi(paolo.paronuzzi***at***unibo.it)
Ulrich Pferschy(pferschy***at***uni-graz.at)

Abstract: We consider integer optimization problems where variables can potentially take fractional values, but this occurrence is penalized in the objective function. This general situation has relevant examples in scheduling (preemption), routing (split delivery), cutting and telecommunications, just to mention a few. However, the general case in which variables integrality can be relaxed at cost of introducing a general penalty was not discussed before. As a case study, we consider the possibly simplest combinatorial optimization problem, namely the classical Knapsack Problem. We introduce the Fractional Knapsack Problem with Penalties (FKPP), a variant of the knapsack problem in which items can be split at the expense of a penalty depending on the fractional quantity. We analyze relevant properties of the problem, present alternative mathematical models, and analyze their performance from a theoretical viewpoint. In addition, we introduce a Fully Polynomial Time Approximation Scheme for the approximate solution of the general problem, and an improved dynamic programming approach that computes the optimal solution in one relevant case. We computationally test the proposed models and algorithms on a large set of instances derived from benchmarks from the literature.

Keywords: knapsack problem, mathematical models, dynamic programming, computational experiments

Category 1: Integer Programming (0-1 Programming )

Category 2: Combinatorial Optimization


Download: [PDF]

Entry Submitted: 08/07/2017
Entry Accepted: 08/07/2017
Entry Last Modified: 08/07/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society