Nonconvex piecewise linear knapsack problems

DOI10.1016/j.ejor.2007.08.044zbMath1180.90271OpenAlexW2039730573MaRDI QIDQ948649

S. Kameshwaran, Yadati Narahari

Publication date: 17 October 2008

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2007.08.044

zbMATH Keywords

dynamic programmingapproximation algorithmconvex envelopelinear relaxationfully polynomial time approximation scheme

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (11)

Capacitated refueling station location problem with traffic deviations over multiple time periods ⋮ A parametric simplex algorithm for biobjective piecewise linear programming problems ⋮ Linearization technique with superior expressions for centralized planning problem with discount policy ⋮ A branch-cut-and-price algorithm for the piecewise linear transportation problem ⋮ Approximating single- and multi-objective nonlinear sum and product knapsack problems ⋮ A graphical approach to solve an investment optimization problem ⋮ Optimal pricing in iterative flexible combinatorial procurement auctions ⋮ A new effective dynamic program for an investment optimization problem ⋮ A heuristic approach for allocation of data to RFID tags: a data allocation knapsack problem (DAKP) ⋮ Heuristic algorithms for the general nonlinear separable knapsack problem ⋮ Knapsack problems with sigmoid utilities: approximation algorithms via hybrid optimization

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Multiattribute electronic procurement using goal programming
• A note on a general nonlinear knapsack problem
• Exact methods for the knapsack problem and its generalizations
• Approximation algorithms for the capacitated plant allocation problem
• Heuristic and exact algorithms for the precedence-constrained knapsack problem
• The nonlinear knapsack problem - algorithms and applications
• A nonlinear knapsack problem
• Approximate minimization algorithms for the 0/1 knapsack and subset-sum problem
• On the solution of concave knapsack problems
• Bid evaluation in procurement auctions with piecewise linear supply curves
• Algorithms for Separable Nonlinear Resource Allocation Problems
• A Comparison of Mixed-Integer Programming Models for Nonconvex Piecewise Linear Cost Minimization Problems
• Fast Approximation Algorithms for Knapsack Problems
• Simple Ranking Methods for Allocation of One Resource
• Disaggregation and Resource Allocation Using Convex Knapsack Problems with Bounded Variables
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Approximate Algorithms for the 0/1 Knapsack Problem
• On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees
• The Nonlinear Resource Allocation Problem
• A pegging algorithm for the nonlinear resource allocation problem

This page was built for publication: Nonconvex piecewise linear knapsack problems