The Linear Sharing Problem

The linear sharing problem is defined as a linear programming problem with a maximin objective function comprised of nondecreasing, continuous tradeoff functions. This paper develops some properties, including optimality conditions, for this problem. It also develops an efficient algorithm that alternately calculates a new global upper bound on the objective function and then determines if a feasible solution exists that meets the new objective function global upper bound. The process continues until the algorithm finds a feasible and, thus, an optimal solution. The algorithm also determines if the problem contains no feasible solution or if the objective function is unbounded. A technique to handle problems with unbounded tradeoff variables is developed and computational experience is given.