Difference: TransportationProblemInAMPL (1 vs. 9)

Revision 92019-11-11 - MichaelOSullivan

Line: 1 to 1
 
META TOPICPARENT name="AMPLGuide"

The Transportation Problem in AMPL

Line: 103 to 103
  -- MichaelOSullivan - 02 Apr 2008
Deleted:
<
<
META FILEATTACHMENT attachment="latex526e21edb215dffbfdb5ee74dd06358b.png" attr="h" comment="" date="1207132191" name="latex526e21edb215dffbfdb5ee74dd06358b.png" stream="GLOB(0xa44d1b8)" tmpFilename="latex526e21edb215dffbfdb5ee74dd06358b.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latex3c99455acbafe055e535fc129b4dd12e.png" attr="h" comment="" date="1207132191" name="latex3c99455acbafe055e535fc129b4dd12e.png" stream="GLOB(0xa456928)" tmpFilename="latex3c99455acbafe055e535fc129b4dd12e.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latexa518db3a714367f452620a2d18e0d61e.png" attr="h" comment="" date="1207132191" name="latexa518db3a714367f452620a2d18e0d61e.png" stream="GLOB(0xa4568f8)" tmpFilename="latexa518db3a714367f452620a2d18e0d61e.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latex57f16e685545faa46af73ecce6b4eb7c.png" attr="h" comment="" date="1207132191" name="latex57f16e685545faa46af73ecce6b4eb7c.png" stream="GLOB(0xa44d5e4)" tmpFilename="latex57f16e685545faa46af73ecce6b4eb7c.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latex15b62f2a4b15b2f0ea551529e221b54f.png" attr="h" comment="" date="1207132191" name="latex15b62f2a4b15b2f0ea551529e221b54f.png" stream="GLOB(0xa44d950)" tmpFilename="latex15b62f2a4b15b2f0ea551529e221b54f.png" user="MichaelOSullivan" version="1"
 
META FILEATTACHMENT attachment="transportation.mod" attr="" comment="" date="1207141133" name="transportation.mod" path="transportation.mod" size="1238" stream="transportation.mod" tmpFilename="" user="MichaelOSullivan" version="2"
META FILEATTACHMENT attachment="transportation.run" attr="" comment="" date="1207188773" name="transportation.run" path="transportation.run" size="929" stream="transportation.run" tmpFilename="" user="BaseUserMapping_333" version="2"
Added:
>
>
META FILEATTACHMENT attachment="latexddfefd6f6e1b023dbc77750dde745f13.png" attr="h" comment="" date="1573440880" name="latexddfefd6f6e1b023dbc77750dde745f13.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latexd58eb835f5dc3ce48118d235a7ed6afa.png" attr="h" comment="" date="1573440880" name="latexd58eb835f5dc3ce48118d235a7ed6afa.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latex5aff540fda60ff1cc43cde3401da45e7.png" attr="h" comment="" date="1573440880" name="latex5aff540fda60ff1cc43cde3401da45e7.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latex5b7238471e85c930c82a09db6ad982d9.png" attr="h" comment="" date="1573440880" name="latex5b7238471e85c930c82a09db6ad982d9.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latexc3a253a845b49f03af40d72efe1dabb9.png" attr="h" comment="" date="1573440881" name="latexc3a253a845b49f03af40d72efe1dabb9.png" user="MichaelOSullivan" version="1"

Revision 82008-04-10 - MichaelOSullivan

Line: 1 to 1
 
META TOPICPARENT name="AMPLGuide"

The Transportation Problem in AMPL

Line: 109 to 109
 
META FILEATTACHMENT attachment="latex57f16e685545faa46af73ecce6b4eb7c.png" attr="h" comment="" date="1207132191" name="latex57f16e685545faa46af73ecce6b4eb7c.png" stream="GLOB(0xa44d5e4)" tmpFilename="latex57f16e685545faa46af73ecce6b4eb7c.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latex15b62f2a4b15b2f0ea551529e221b54f.png" attr="h" comment="" date="1207132191" name="latex15b62f2a4b15b2f0ea551529e221b54f.png" stream="GLOB(0xa44d950)" tmpFilename="latex15b62f2a4b15b2f0ea551529e221b54f.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="transportation.mod" attr="" comment="" date="1207141133" name="transportation.mod" path="transportation.mod" size="1238" stream="transportation.mod" tmpFilename="" user="MichaelOSullivan" version="2"
Changed:
<
<
META FILEATTACHMENT attachment="transportation.run" attr="h" comment="" date="1207188773" name="transportation.run" path="transportation.run" size="929" stream="transportation.run" tmpFilename="" user="BaseUserMapping_333" version="2"
>
>
META FILEATTACHMENT attachment="transportation.run" attr="" comment="" date="1207188773" name="transportation.run" path="transportation.run" size="929" stream="transportation.run" tmpFilename="" user="BaseUserMapping_333" version="2"

Revision 72008-04-03 - TWikiAdminUser

Line: 1 to 1
 
META TOPICPARENT name="AMPLGuide"

The Transportation Problem in AMPL

Line: 109 to 109
 
META FILEATTACHMENT attachment="latex57f16e685545faa46af73ecce6b4eb7c.png" attr="h" comment="" date="1207132191" name="latex57f16e685545faa46af73ecce6b4eb7c.png" stream="GLOB(0xa44d5e4)" tmpFilename="latex57f16e685545faa46af73ecce6b4eb7c.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latex15b62f2a4b15b2f0ea551529e221b54f.png" attr="h" comment="" date="1207132191" name="latex15b62f2a4b15b2f0ea551529e221b54f.png" stream="GLOB(0xa44d950)" tmpFilename="latex15b62f2a4b15b2f0ea551529e221b54f.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="transportation.mod" attr="" comment="" date="1207141133" name="transportation.mod" path="transportation.mod" size="1238" stream="transportation.mod" tmpFilename="" user="MichaelOSullivan" version="2"
Changed:
<
<
META FILEATTACHMENT attachment="transportation.run" attr="" comment="" date="1207132942" name="transportation.run" path="transportation.run" size="887" stream="transportation.run" tmpFilename="" user="MichaelOSullivan" version="1"
>
>
META FILEATTACHMENT attachment="transportation.run" attr="h" comment="" date="1207188773" name="transportation.run" path="transportation.run" size="929" stream="transportation.run" tmpFilename="" user="BaseUserMapping_333" version="2"

Revision 62008-04-02 - MichaelOSullivan

Line: 1 to 1
 
META TOPICPARENT name="AMPLGuide"

The Transportation Problem in AMPL

Line: 53 to 53
  >= Lower[i, j], <= Upper[i, j], integer;
Added:
>
>
Also, since some arcs no longer exist you should set a default of 0 for Cost (thus you don't have to define costs for non-existent arcs).
param Cost {SUPPLY_NODES, DEMAND_NODES} default 0;
 

Balancing Transportation Problems

Balanced transportation models are preferred as there is no confusion about the relational operators for the supply and demand constraints. We can use a script file (transportation.run) to balance any transportation problem automatically:

Line: 103 to 108
 
META FILEATTACHMENT attachment="latexa518db3a714367f452620a2d18e0d61e.png" attr="h" comment="" date="1207132191" name="latexa518db3a714367f452620a2d18e0d61e.png" stream="GLOB(0xa4568f8)" tmpFilename="latexa518db3a714367f452620a2d18e0d61e.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latex57f16e685545faa46af73ecce6b4eb7c.png" attr="h" comment="" date="1207132191" name="latex57f16e685545faa46af73ecce6b4eb7c.png" stream="GLOB(0xa44d5e4)" tmpFilename="latex57f16e685545faa46af73ecce6b4eb7c.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latex15b62f2a4b15b2f0ea551529e221b54f.png" attr="h" comment="" date="1207132191" name="latex15b62f2a4b15b2f0ea551529e221b54f.png" stream="GLOB(0xa44d950)" tmpFilename="latex15b62f2a4b15b2f0ea551529e221b54f.png" user="MichaelOSullivan" version="1"
Changed:
<
<
META FILEATTACHMENT attachment="transportation.mod" attr="" comment="" date="1207132918" name="transportation.mod" path="transportation.mod" size="1228" stream="transportation.mod" tmpFilename="" user="MichaelOSullivan" version="1"
>
>
META FILEATTACHMENT attachment="transportation.mod" attr="" comment="" date="1207141133" name="transportation.mod" path="transportation.mod" size="1238" stream="transportation.mod" tmpFilename="" user="MichaelOSullivan" version="2"
 
META FILEATTACHMENT attachment="transportation.run" attr="" comment="" date="1207132942" name="transportation.run" path="transportation.run" size="887" stream="transportation.run" tmpFilename="" user="MichaelOSullivan" version="1"

Revision 52008-04-02 - MichaelOSullivan

Line: 1 to 1
 
META TOPICPARENT name="AMPLGuide"

The Transportation Problem in AMPL

AMPL Formulation

Changed:
<
<
The formulation of the transportation problem is AMPL is a straightforward translation of the mathematical programme for the transportation problem.
>
>
The formulation of the transportation problem is AMPL is a straightforward translation of the mathematical programme for the transportation problem. We will build the file transportation.mod.
  The sets ${\cal S}$ and ${\cal D}$ are declared as SUPPLY_NODES and DEMAND_NODES respectively:

Line: 55 to 55
 

Balancing Transportation Problems

Changed:
<
<
Balanced transportation models are preferred as there is no confusion about the relational operators for the supply and demand constraints. We can use script file to balance any transportation problem automatically:
>
>
Balanced transportation models are preferred as there is no confusion about the relational operators for the supply and demand constraints. We can use a script file (transportation.run) to balance any transportation problem automatically:
 
reset;

Line: 96 to 96
  Note the check statement to ensure that the balancing has been done properly before solving. Also, note that costToDummy and costFromDummy allow for the definition of costs on any flow from/to a dummy node in the data file.
Deleted:
<
<
Both the AMPL model file transportation.mod and script file transportation.run are attached.
 -- MichaelOSullivan - 02 Apr 2008

META FILEATTACHMENT attachment="latex526e21edb215dffbfdb5ee74dd06358b.png" attr="h" comment="" date="1207132191" name="latex526e21edb215dffbfdb5ee74dd06358b.png" stream="GLOB(0xa44d1b8)" tmpFilename="latex526e21edb215dffbfdb5ee74dd06358b.png" user="MichaelOSullivan" version="1"

Revision 42008-04-02 - MichaelOSullivan

Line: 1 to 1
 
META TOPICPARENT name="AMPLGuide"

The Transportation Problem in AMPL

AMPL Formulation

Changed:
<
<
The formulation of the transportation problem is AMPL is a straighforward translation of the matehmatical programme for the transportation problem.
>
>
The formulation of the transportation problem is AMPL is a straightforward translation of the mathematical programme for the transportation problem.
  The sets ${\cal S}$ and ${\cal D}$ are declared as SUPPLY_NODES and DEMAND_NODES respectively:

Line: 55 to 55
 

Balancing Transportation Problems

Added:
>
>
Balanced transportation models are preferred as there is no confusion about the relational operators for the supply and demand constraints. We can use script file to balance any transportation problem automatically:
reset;

model transportation.mod;

param costFromDummy {DEMAND_NODES} default 0;
param costToDummy   {SUPPLY_NODES} default 0;

param difference;

# Add the problem date file here
# e.g., data brewery.dat;

let difference := (sum {s in SUPPLY_NODES} Supply[s])
                - (sum {d in DEMAND_NODES} Demand[d]);
                  
if difference > 0 then
{
  let DEMAND_NODES := DEMAND_NODES union {'Dummy'};
  let Demand['Dummy'] := difference;
  let {s in SUPPLY_NODES} Cost[s, 'Dummy'] := costToDummy[s];
}
else if difference < 0 then
{
  let SUPPLY_NODES := SUPPLY_NODES union {'Dummy'};
  let Supply['Dummy'] := - difference;
  let {d in DEMAND_NODES} Cost['Dummy', d] := costFromDummy[d];
}; # else the problem is balanced

# Make sure the problem is balanced
check : sum {s in SUPPLY_NODES} Supply[s] = sum {d in DEMAND_NODES} Demand[d];

option solver cplex;

solve;

display Flow;
Note the check statement to ensure that the balancing has been done properly before solving. Also, note that costToDummy and costFromDummy allow for the definition of costs on any flow from/to a dummy node in the data file.

Both the AMPL model file transportation.mod and script file transportation.run are attached.

 -- MichaelOSullivan - 02 Apr 2008

META FILEATTACHMENT attachment="latex526e21edb215dffbfdb5ee74dd06358b.png" attr="h" comment="" date="1207132191" name="latex526e21edb215dffbfdb5ee74dd06358b.png" stream="GLOB(0xa44d1b8)" tmpFilename="latex526e21edb215dffbfdb5ee74dd06358b.png" user="MichaelOSullivan" version="1"
Line: 62 to 106
 
META FILEATTACHMENT attachment="latexa518db3a714367f452620a2d18e0d61e.png" attr="h" comment="" date="1207132191" name="latexa518db3a714367f452620a2d18e0d61e.png" stream="GLOB(0xa4568f8)" tmpFilename="latexa518db3a714367f452620a2d18e0d61e.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latex57f16e685545faa46af73ecce6b4eb7c.png" attr="h" comment="" date="1207132191" name="latex57f16e685545faa46af73ecce6b4eb7c.png" stream="GLOB(0xa44d5e4)" tmpFilename="latex57f16e685545faa46af73ecce6b4eb7c.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latex15b62f2a4b15b2f0ea551529e221b54f.png" attr="h" comment="" date="1207132191" name="latex15b62f2a4b15b2f0ea551529e221b54f.png" stream="GLOB(0xa44d950)" tmpFilename="latex15b62f2a4b15b2f0ea551529e221b54f.png" user="MichaelOSullivan" version="1"
Added:
>
>
META FILEATTACHMENT attachment="transportation.mod" attr="" comment="" date="1207132918" name="transportation.mod" path="transportation.mod" size="1228" stream="transportation.mod" tmpFilename="" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="transportation.run" attr="" comment="" date="1207132942" name="transportation.run" path="transportation.run" size="887" stream="transportation.run" tmpFilename="" user="MichaelOSullivan" version="1"

Revision 32008-04-02 - MichaelOSullivan

Line: 1 to 1
 
META TOPICPARENT name="AMPLGuide"

The Transportation Problem in AMPL

Line: 23 to 23
 param Cost {SUPPLY_NODES, DEMAND_NODES};
Changed:
<
<
Now, the mathematical proramme follows directly:
>
>
Now, the mathematical programme follows directly:
 

Changed:
<
<
var Flow {i in SUPPLY_NODES, j in DEMAND_NODES} >= 0, integer;
>
>
var Flow {SUPPLY_NODES, DEMAND_NODES} >= 0, integer;
  minimize TotalCost: sum {i in SUPPLY_NODES, j in DEMAND_NODES} Cost[i, j] * Flow[i, j];
Line: 38 to 38
  Note that we assume the transportation is balanced.
Added:
>
>

Adding Bounds

In the main discussion of transportation problems, we saw that adding bounds to the flow variables allowed us to easily either bound the transportation of good from a supply node to a demand node or remove an arc from the problem altogether.

We can add bounds to our AMPL formulation by declaring 2 new parameters with defaults:

param Lower {SUPPLY_NODES, DEMAND_NODES} integer default 0;
param Upper {SUPPLY_NODES, DEMAND_NODES} integer default Infinity;
and adding them to the Flow variable declaration:
var Flow {i in SUPPLY_NODES, j in DEMAND_NODES}
  >= Lower[i, j], <= Upper[i, j], integer;

Balancing Transportation Problems

  -- MichaelOSullivan - 02 Apr 2008

Revision 22008-04-02 - MichaelOSullivan

Line: 1 to 1
 
META TOPICPARENT name="AMPLGuide"

The Transportation Problem in AMPL

Added:
>
>

AMPL Formulation

The formulation of the transportation problem is AMPL is a straighforward translation of the matehmatical programme for the transportation problem.

The sets ${\cal S}$ and ${\cal D}$ are declared as SUPPLY_NODES and DEMAND_NODES respectively:

set SUPPLY_NODES;
set DEMAND_NODES;

The supply $s_i, i \in {\cal S}$ and demand $d_j, j \in {\cal D}$ are declared as integer parameters:

param Supply {SUPPLY_NODES} >= 0, integer;
param Demand {DEMAND_NODES} >= 0, integer;

The cost $c_{ij}$ is declared over the SUPPLY_NODES and DEMAND_NODES:

param Cost {SUPPLY_NODES, DEMAND_NODES};

Now, the mathematical proramme follows directly:

var Flow {i in SUPPLY_NODES, j in DEMAND_NODES} >= 0, integer;

minimize TotalCost:
  sum {i in SUPPLY_NODES, j in DEMAND_NODES} Cost[i, j] * Flow[i, j];

subject to UseSupply {i in SUPPLY_NODES}:
  sum {j in DEMAND_NODES} Flow[i, j] = Supply[i];

subject to MeetDemand {j in DEMAND_NODES}:
  sum {i in SUPPLY_NODES} Flow[i, j] = Demand[j];
Note that we assume the transportation is balanced.
 -- MichaelOSullivan - 02 Apr 2008
Added:
>
>
META FILEATTACHMENT attachment="latex526e21edb215dffbfdb5ee74dd06358b.png" attr="h" comment="" date="1207132191" name="latex526e21edb215dffbfdb5ee74dd06358b.png" stream="GLOB(0xa44d1b8)" tmpFilename="latex526e21edb215dffbfdb5ee74dd06358b.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latex3c99455acbafe055e535fc129b4dd12e.png" attr="h" comment="" date="1207132191" name="latex3c99455acbafe055e535fc129b4dd12e.png" stream="GLOB(0xa456928)" tmpFilename="latex3c99455acbafe055e535fc129b4dd12e.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latexa518db3a714367f452620a2d18e0d61e.png" attr="h" comment="" date="1207132191" name="latexa518db3a714367f452620a2d18e0d61e.png" stream="GLOB(0xa4568f8)" tmpFilename="latexa518db3a714367f452620a2d18e0d61e.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latex57f16e685545faa46af73ecce6b4eb7c.png" attr="h" comment="" date="1207132191" name="latex57f16e685545faa46af73ecce6b4eb7c.png" stream="GLOB(0xa44d5e4)" tmpFilename="latex57f16e685545faa46af73ecce6b4eb7c.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latex15b62f2a4b15b2f0ea551529e221b54f.png" attr="h" comment="" date="1207132191" name="latex15b62f2a4b15b2f0ea551529e221b54f.png" stream="GLOB(0xa44d950)" tmpFilename="latex15b62f2a4b15b2f0ea551529e221b54f.png" user="MichaelOSullivan" version="1"

Revision 12008-04-02 - MichaelOSullivan

Line: 1 to 1
Added:
>
>
META TOPICPARENT name="AMPLGuide"

The Transportation Problem in AMPL

-- MichaelOSullivan - 02 Apr 2008

 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2020 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback