Integer optimization with penalized fractional values: The Knapsack case

Enrico Malaguti

doi:10.1016/j.ejor.2018.09.020

Integer optimization with penalized fractional values: The Knapsack case

2019-03-01

10

OA

AI

DOI：10.1016/j.ejor.2018.09.020

原文链接

查看原文

摘要

En 中文

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. (C) 2018 Elsevier B.V. All rights reserved.

Keyword:

Packing

Knapsack problem

Dynamic programming

Approximation algorithms

Computational experiments

Integer optimization with penalized fractional values: The Knapsack case

摘要

AI总结

期刊

机构