Fixed-charge continuous knapsack problems and pseudogreedy solutions
We investigate nonlinear continuous knapsack problems, which can be classified as fixed-charge problems with one equality constraint and explicit bounds on the variables. The objective function of the general problem considered here, has the form Psi(x) - Gamma(x). Psi(x) constitutes a specific generalization of a linear function, still allowing a greedy sorting of the variables. Gamma(x) includes the fixed-cost functions of many types of fixed-charge problems as special cases (e.g. sequence-dependent fixed costs and the fixed-cost function of the interactive fixed-charge problem of Benson and Erenguc). Gamma is an isotonic function, but not sub-modular in general. We prove the existence of simple-structured optimal solutions (they show a partial greedy structure and at most one variable does not attain its upper or lower bound) called "pseudogreedy solutions". Moreover we state an algorithm for solving the problem and we give results concerning the sensitivity of the greedy solution and the pseudogreedy structure of optimal solutions.
fixed-charge continuous knapsack problem pseudogreedy solution greedy solution convex maximization generalized fixed-cost function sensitivity analysis