  


Integer Optimization with Penalized Fractional Values: The Knapsack Case
Enrico Malaguti(enrico.malagutiunibo.it) 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 (01 Programming ) Category 2: Combinatorial Optimization Citation: Download: [PDF] Entry Submitted: 08/07/2017 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  