-1
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – Brian Borchers
    Commented Jul 14, 2013 at 20:26

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I admit that the problem is not well posed; the problem I want to model, is tour expansion for the planar, euclidean TSP. I will edit the problem description and provide details about my approach and the problems I encountered so far. Unfortunately I'm currently short of time. Expect more in about two weeks time. $\endgroup$
    – Manfred Weis
    Commented Jul 19, 2013 at 20:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .