Linear problems of resource allocation are traditionally solved by methods of linear programming which do not have a broad applicability.
Article The Technology of Interactive Resource Allocation in Accorda...
Dear Alexander,
It is known that in practice, use of LP methods is quite problematic. One problem is the mathematical incorrectness of the LP problem due to the instability of solution for small changes of the input data. Another problem is the non-applicability of solution found as a Chebyshev point in case of constraints incompatibility. Such solutions can not be applied because they violate constraints that must be met: it is impossible to allocate more resource than available.
One of the main reasons: because a resource allocation problem might not have a clearly defined cost per item values for every variable that we find the solution for. As long as one keeps//approximates goal function and the constraints in linear form, LP is relevant for the solution. But frequently real life cost per item values are not given explicitly, but rather are given implicitly through some historic statistics. Then searching for implicit inference of the goal function might produce non linear goal function.
Hi Renaldas,
I agree with your comments, and I would mention that if we "approximate" a goal function, then the problem of instability of the LP decision becomes the main: small changes of coefficients may cardinally change the goal function value.
Dear Vladimir,
Moreover, expert planner, using a program that can solve only the LP problem and the problem of search for Chebyshev point, is too limited in the choice of means to obtain the desired results. Traditional LP software does not allow an expert intervention in the search for solution. If given system of constraints is incompatible, programs propose to adjust the input data.
The case of linear versus nonlinear depends on the application, most certainly. There are also a very large number of resource allocation applications that are integer-valued, and even some of them are nonlinear.
For more detailed reading, there are at least two books on the subject, treating a variety of settings and applications, as well as algorithms:
K.M. Mjelde, "Methods of the Allocation of Limited Resources", Wiley, 1983
H. Luss: "Equitable Resource Allocation: Models, Algorithms and Applications", Wiley 2012
I have a fairly long survey on the subject in the case of nonlinear and continuous problems when there is one resource, found here in a preprint form: http://publications.lib.chalmers.se/records/fulltext/local_79626.pdf
The actual paper was published in EJOR, linked to here: http://www.sciencedirect.com/science/article/pii/S0377221706012215
Hi Michael,
Thank you for the comments and references.
My question concerns applicability of algorithms for linear problems.
For a linear problem there is the elusive property of Lagrange multipliers (for the resource constraint) not yielding "controllability" - that is, you cannot in general produce an optimal solution even if you know the optimal value of the multiplier of the capacity constraint.
Dear Alexander,
Classical formulation of the linear problem of resource allocation and different algorithms for its solution based on the simplex method - things that have a mathematical sense, but they are not practical.
Algorithms of linear programming may be useful for solving problems in which there are no problems of data accuracy and consistency of the constraints system. In particular, they may be useful in some problems of modeling.
Are there any software for regularized problems of linear programming? (I mean Tikhonov regularization).
See the following papers for further examples of regularization methods for linear programs:
1. http://web.stanford.edu/group/SOL/reports/ldl2.pdf
2. http://www.stat.osu.edu/~yao/software/lpRegPath.pdf