ISSN:
1436-4646
Keywords:
Maximin programming
;
knapsack sharing problems
;
multiple-valued objective functions
;
staircase objective functions
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract A knapsack sharing problem is a maximin or minimax mathematical programming problem with one or more “knapsack” constraints (an inequality constraint with all non-negative coefficients). All knapsack sharing algorithms to date have assumed that the objective function is composed of single variable functions called tradeoff functions which are strictly increasing continuous functions. This paper develops optimality conditions and algorithms for knapsack sharing problems with any type of continuous tradeoff function including multiple-valued and staircase functions which can be increasing, decreasing, unimodal, bimodal, or even multi-modal. To do this, optimality conditions are developed for a special type of multiple-valued, nondecreasing tradeoff function called an ascending function. The optimal solution to any knapsack sharing problem can then be found by solving an equivalent problem where all the tradeoff functions have been transformed to ascending functions. Polynomial algorithms are developed for piecewise linear tradeoff functions with a fixed number of breakpoints. The techniques needed to construct efficient algorithms for any type of tradeoff function are discussed.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01586926
Permalink
