Skip to main content
Post Undeleted by Robert Israel
added 59 characters in body
Source Link
Robert Israel
  • 54.2k
  • 1
  • 76
  • 152

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

I don't see how your restriction captures the requirement you stated. In any case, it does not preserve integrality. Consider a case where customer A can be served by depots 1 and 2, customer B by depots 2 and 3, but cost of using depot 3 is high. All demands are 1 unit. If you require the flow from depot 2 to A be the maximum of the flows from depot 2, the optimal solution will have 2 send 1/2 unit to both A and B.

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.

Post Deleted by Robert Israel
Source Link
Robert Israel
  • 54.2k
  • 1
  • 76
  • 152

I don't see how your restriction captures the requirement you stated. In any case, it does not preserve integrality. Consider a case where customer A can be served by depots 1 and 2, customer B by depots 2 and 3, but cost of using depot 3 is high. All demands are 1 unit. If you require the flow from depot 2 to A be the maximum of the flows from depot 2, the optimal solution will have 2 send 1/2 unit to both A and B.