A Submodular Optimization Problem with Side Constraints

In this paper we consider the general problem of optimizing over the intersection of a submodular base polyhedron and an affine space. An example is the following flow problem defined on a capacitated network: We wish to send a commodity from locations in a producing country to locations in a number of client countries so as to simultaneously maximize profits and send to each client country a prescribed proportion of the total sent. We present an algorithm for the general problem and analyze its complexity.