A Class of Nonlinear Continuous Knapsack
Problems With
Applications in Supply Chain Optimization
Thomas C. Sharkey, H. Edwin Romeijn,
Joseph Geunes
Dept. of Industrial and Systems Engineering
In recent years several
integrated supply chain optimization models have been studied that require the
solution of certain nonlinear knapsack problems. Examples are market selection
problems where a supplier can choose which markets to serve to maximize a measure
of total profit. Such problems are of independent interest but also appear as
pricing problems in a branch-and-price solution approach to single-sourcing
problems in which a set of retailers (or markets) needs to be assigned to a set
of supply facilities to minimize total system cost.
In this talk we consider the
relaxation of a large class of nonlinear knapsack problems where the objective
function is the sum of one linear function of the variables plus a nonlinear
function of another linear function of the variables, subject to a knapsack
constraint. We start by showing that there always exists an optimal solution to
such problems in which no more than two variables have a fractional value.
Under mild conditions on the objective we use the KKT conditions to
characterize the structure of candidate optimal solutions to such problems.
This characterization is then employed to derive a condition under which we
develop an algorithm that solves the problem in an amount of time that is
polynomial in the number of variables in the problem. In addition, we show that
if the condition is violated the problem is NP-hard. Finally, we show how these
results can be generalized to the case of multiple knapsack constraints.