# Effect of a Specific Restriction on the Integrality of Min-cost Flow Solutions

I want to model the following situation: there is one production site (modelled by the source), a collection of depots (modelled by nodes without demand) and, of course many more customers (modelled by sinks). The production equals the demand and the transport of goods costs money; the costs are proportional to the amount of goods transported, but the factor may be different for different roads.

Now comes the twist: a depot may only be visited if also a specific customer nearby will be served from that depot.

The way I intend to model that requirement is by demanding that the flow from the depot to that customer shall be the maximum of all outflows from that depot.

The question is now, as to whether such a maximum restriction upon the outflows of a node will preserve integrality of the solution.

• Do the demands of the different customers vary, or are they all the same? Are there upper bounds on the capacity of any of the arcs? Are there some arcs that simply don't exist (or have a 0 upper bound on the flow)? Is it possible for two depots to both be associated with the same customer? – Brian Borchers Jul 14 '13 at 20:26

I don't see how your restriction captures the requirement you stated. In any case, it does not preserve integrality. Consider a case where customers A and B (each with 1 unit demand) can both be served by depots 1 and 2, but you require the flow from 1 to A be the maximum of the flows out of 1. There are two extreme points of the set of feasible solutions, of which one is non-integral (each depot sends $1/2$ unit to each customer), and this may well be the optimal solution.