by Girlich, E., Kovalev, M., Zaporozhets, A..

**Series:** 1997-36, Preprints

- MSC:
- 90C10 Integer programming

**Abstract:**

We consider the standardization problem (SP) which can be formulated as

follows. There are m types of items. There exist a demand in items of n types represented

by a vector b 2 Z n

+ . There are known possibilities of replacement of some items type by

others. Producing y i items of the ith type, one becomes a profit f i (y i ), where f i : R! R

is a nondecreasing concave function for each i_2 f1,2,...,ng. It is necessary to satisfy the

demand and to maximize the total profit under the replacements condition. We show that

SP and its generalization are special cases of resource allocation problem over a network

polymatroid. An adaptation of Scaling Algorithm for SP is proposed.

**Keywords:**

Standardization problem, Resource allocation, Network polymatroid, Bipartite graph.