Difference: CokeSupplyChain (1 vs. 20)

Revision 202018-11-23 - TWikiAdminUser

Line: 1 to 1
 
META TOPICPARENT name="SubmitCaseStudy" 
<-- Ready to Review -->
Line: 95 to 95
 |*FORM FIELD StudentTasks*|StudentTasks|
  1. Write AMPL model, data and script files (coke.mod, coke.dat and coke.run respectively) to solve the Coke Production Problem. Write a management summary for your solution.

    What to hand in Your 3 AMPL files. Your management summary.

  2. Experts Only Solve the LP relaxation of the Coke Supply Chain Problem integer programme. Using the branches described in Extra for Experts, use AMPL to perform branching on at least 4 nodes and draw the resulting branch-and-bound tree.

    Hint See Extra for Experts in the Cosmic ComputersProblem for an example of constraint branching in AMPL.

    What to hand in Your AMPL code for implementing the branches. Your drawing of your branch-and-bound tree.

|
META FILEATTACHMENT attachment="800px-Koks_Brennstoff.jpg" attr="h" comment="" date="1203500128" name="800px-Koks_Brennstoff.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\CokeProduction\800px-Koks_Brennstoff.jpg" size="77315" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\CokeProduction\800px-Koks_Brennstoff.jpg" tmpFilename="" user="LaurenJackson" version="1"
META FILEATTACHMENT attachment="coke_map.jpg" attr="h" comment="" date="1203500160" name="coke_map.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\CokeProduction\coke_map.jpg" size="43023" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\CokeProduction\coke_map.jpg" tmpFilename="" user="LaurenJackson" version="1"
Changed:
<
<
META FILEATTACHMENT attachment="latex6f834a945dc2e3c23f04a7ab04dfd506.png" attr="h" comment="" date="1208933146" name="latex6f834a945dc2e3c23f04a7ab04dfd506.png" stream="GLOB(0xa3aeab4)" tmpFilename="latex6f834a945dc2e3c23f04a7ab04dfd506.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latexf59c8c028fb191d065d6a20fa8b58ad4.png" attr="h" comment="" date="1208933147" name="latexf59c8c028fb191d065d6a20fa8b58ad4.png" stream="GLOB(0xa2dfe64)" tmpFilename="latexf59c8c028fb191d065d6a20fa8b58ad4.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latexc1aa8902c98c0ae0732323a987ba2bd9.png" attr="h" comment="" date="1208933147" name="latexc1aa8902c98c0ae0732323a987ba2bd9.png" stream="GLOB(0xa2e0188)" tmpFilename="latexc1aa8902c98c0ae0732323a987ba2bd9.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latexdcf1fc59557e250eed061a8c02867d44.png" attr="h" comment="" date="1208934097" name="latexdcf1fc59557e250eed061a8c02867d44.png" stream="GLOB(0xacc2594)" tmpFilename="latexdcf1fc59557e250eed061a8c02867d44.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latexfb492a77be777564ce3f1e7425e408e4.png" attr="h" comment="" date="1208934097" name="latexfb492a77be777564ce3f1e7425e408e4.png" stream="GLOB(0xabb95e8)" tmpFilename="latexfb492a77be777564ce3f1e7425e408e4.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latex813faf7551d19e746040859b8af4d580.png" attr="h" comment="" date="1208934098" name="latex813faf7551d19e746040859b8af4d580.png" stream="GLOB(0xabb152c)" tmpFilename="latex813faf7551d19e746040859b8af4d580.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latex249fcba5b94268daac8961654756a25c.png" attr="h" comment="" date="1208934098" name="latex249fcba5b94268daac8961654756a25c.png" stream="GLOB(0xabb18c8)" tmpFilename="latex249fcba5b94268daac8961654756a25c.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latex75ebf9389b5be72af0360b24bca5adee.png" attr="h" comment="" date="1208934098" name="latex75ebf9389b5be72af0360b24bca5adee.png" stream="GLOB(0xabb1850)" tmpFilename="latex75ebf9389b5be72af0360b24bca5adee.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latex3aea7233589aa721f711db94f601349b.png" attr="h" comment="" date="1208934098" name="latex3aea7233589aa721f711db94f601349b.png" stream="GLOB(0xabb17d8)" tmpFilename="latex3aea7233589aa721f711db94f601349b.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latex7af89fb055fd3b92240c2285dbbe8111.png" attr="h" comment="" date="1208934098" name="latex7af89fb055fd3b92240c2285dbbe8111.png" stream="GLOB(0xabb1afc)" tmpFilename="latex7af89fb055fd3b92240c2285dbbe8111.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latex65cd373241df8f5af7efc94023eda61a.png" attr="h" comment="" date="1208934098" name="latex65cd373241df8f5af7efc94023eda61a.png" stream="GLOB(0xabb1c88)" tmpFilename="latex65cd373241df8f5af7efc94023eda61a.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latex32fc80ae026cf4d1f4099205fde096f0.png" attr="h" comment="" date="1208934098" name="latex32fc80ae026cf4d1f4099205fde096f0.png" stream="GLOB(0xacc236c)" tmpFilename="latex32fc80ae026cf4d1f4099205fde096f0.png" user="MichaelOSullivan" version="1"
>
>
META FILEATTACHMENT attachment="latex430c43d5656b1cf7a0141b5ffe7f4ce9.png" attr="h" comment="" date="1542936750" name="latex430c43d5656b1cf7a0141b5ffe7f4ce9.png" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="latex49e5470703bcb88ad55bba9d5285d255.png" attr="h" comment="" date="1542936750" name="latex49e5470703bcb88ad55bba9d5285d255.png" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="latexb7d92a08e1d10303f6e1d9bcc17f3764.png" attr="h" comment="" date="1542936750" name="latexb7d92a08e1d10303f6e1d9bcc17f3764.png" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="latex82630b16f6a889391ab4087ec9289539.png" attr="h" comment="" date="1542936750" name="latex82630b16f6a889391ab4087ec9289539.png" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="latexc6225364c4b2df199eec362b876b546b.png" attr="h" comment="" date="1542936750" name="latexc6225364c4b2df199eec362b876b546b.png" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="latex17aa2e4ba5661923f2a0a3d51bf35a1a.png" attr="h" comment="" date="1542936750" name="latex17aa2e4ba5661923f2a0a3d51bf35a1a.png" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="latexf92fd67ba11cce348cdde7ff11c78989.png" attr="h" comment="" date="1542936750" name="latexf92fd67ba11cce348cdde7ff11c78989.png" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="latex750ab94d45649681fc8be4ab64c6315f.png" attr="h" comment="" date="1542936750" name="latex750ab94d45649681fc8be4ab64c6315f.png" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="latex2b8909668b8155ce5843ac747958be68.png" attr="h" comment="" date="1542936750" name="latex2b8909668b8155ce5843ac747958be68.png" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="latexcc750865e2bfc1f08c5f63b8d28427b9.png" attr="h" comment="" date="1542936750" name="latexcc750865e2bfc1f08c5f63b8d28427b9.png" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="latex59dd634520662634567175a69d647201.png" attr="h" comment="" date="1542936751" name="latex59dd634520662634567175a69d647201.png" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="latexcd79dbd5ab7a74950eb23c49b57e82a7.png" attr="h" comment="" date="1542936751" name="latexcd79dbd5ab7a74950eb23c49b57e82a7.png" user="BaseUserMapping_333" version="1"
 
META TOPICMOVED by="MichaelOSullivan" date="1204454747" from="OpsRes.CokeProduction" to="OpsRes.CokeSupplyChain"

Revision 192009-10-06 - MichaelOSullivan

Line: 1 to 1
 
META TOPICPARENT name="SubmitCaseStudy" 
<-- Ready to Review -->
Line: 18 to 18
  -->
Changed:
<
<		%BEGINLATEXPREAMBLE% \usepackage{amsmath}
>
>		%BEGINLATEXPREAMBLE% \usepackage{amsmath}
 %ENDLATEXPREAMBLE%

Case Study: The Coke Supply Chain Problem

Line: 92 to 91
 
FORM FIELD ComputationalModel ComputationalModel The computational model...
FORM FIELD Results Results The results...
FORM FIELD Conclusions Conclusions In conclusion...
Changed:
<
<		|*FORM FIELD ExtraForExperts*|ExtraForExperts|This problem is similar to the Cosmic Computers Problem, but the facility location is a little different. Rather than face a decision about whether to build a plant or not, we need to determine what type of plant to build. This gives rise to the following variable:
\[ y_{ps} = 1 \text{ if plant $p$ is built with size $s$, 0 otherwise} \]

While solving the Coke Supply Chain Problem, the expression

\[ \sum_{s \in \text{sizes}} y_{ps} \]
will often be fractional. This means that the capacity of the plant
\[ \sum_{s \in \text{sizes}} C_s y_{ps} \]
where $C_s$ is the capacity of a plant of size $s$ will be between the capacities of two different size plants, e.g., 280 kT/yr is between 225 kT/yr plant and a 300 kT/yr plant. We could use constraints to remove the fractionality, e.g.,
\[ \begin{array}{r@{\,}l@{\quad\quad}l} \displaystyle \sum_{s \in \text{sizes}} C_s y_{ps} &amp;\leq 225 &amp; \text{(branching down)} \\ \displaystyle \sum_{s \in \text{sizes}} C_s y_{ps} &amp;\geq 300 &amp; \text{(branching up)} \end{array} \]

These branches will ensure plants have the right capacities, but will still not resolve fractionalities in the $y_{ps}$. However, if we want the capacity of plant $p$ to be $\leq$ 225, then we can remove all the $y_{ps}$ that allow for the capacity to be larger than 225:

\[ \sum_{s \in \text{sizes} | C_s > 225} y_{ps} = 0 \]

Conversely, if we want to branch up, i.e., the capacity is $\geq$ 300, then we can remove all the $y_{ps}$ that allow the capacity to be smaller than 300:

\[ \sum_{s \in \text{sizes} | C_s < 300} y_{ps} = 0 \]

Note For these branches to work properly, the possibility of building no plant must be modeled as building a plant with no capacity (i.e., $C_s$ = 0) for no cost. |

>
>		|*FORM FIELD ExtraForExperts*|ExtraForExperts|This problem is similar to the Cosmic Computers Problem, but the facility location is a little different. Rather than face a decision about whether to build a plant or not, we need to determine what type of plant to build. This gives rise to the following variable:
\[ y_{ps} = 1 \text{ if plant $p$ is built with size $s$, 0 otherwise} \]

While solving the Coke Supply Chain Problem, the expression

\[ \sum_{s \in \text{sizes}} y_{ps} \]
will often be fractional. This means that the capacity of the plant
\[ \sum_{s \in \text{sizes}} C_s y_{ps} \]
where $C_s$ is the capacity of a plant of size $s$ will be between the capacities of two different size plants, e.g., 280 kT/yr is between 225 kT/yr plant and a 300 kT/yr plant. We could use constraints to remove the fractionality, e.g.,
\[ \begin{array}{r@{\,}l@{\quad\quad}l} \displaystyle \sum_{s \in \text{sizes}} C_s y_{ps} &amp;\leq 225 &amp; \text{(branching down)} \\ \displaystyle \sum_{s \in \text{sizes}} C_s y_{ps} &amp;\geq 300 &amp; \text{(branching up)} \end{array} \]

These branches will ensure plants have the right capacities, but will still not resolve fractionalities in the $y_{ps}$. However, if we want the capacity of plant $p$ to be $\leq$ 225, then we can remove all the $y_{ps}$ that allow for the capacity to be larger than 225:

\[ \sum_{s \in \text{sizes} | C_s > 225} y_{ps} = 0 \]

Conversely, if we want to branch up, i.e., the capacity is $\geq$ 300, then we can remove all the $y_{ps}$ that allow the capacity to be smaller than 300:

\[ \sum_{s \in \text{sizes} | C_s < 300} y_{ps} = 0 \]

Note For these branches to work properly, the possibility of building no plant must be modelled as building a plant with no capacity (i.e., $C_s$ = 0) for no cost. |

 |*FORM FIELD StudentTasks*|StudentTasks|
  1. Write AMPL model, data and script files (coke.mod, coke.dat and coke.run respectively) to solve the Coke Production Problem. Write a management summary for your solution.

    What to hand in Your 3 AMPL files. Your management summary.

  2. Experts Only Solve the LP relaxation of the Coke Supply Chain Problem integer programme. Using the branches described in Extra for Experts, use AMPL to perform branching on at least 4 nodes and draw the resulting branch-and-bound tree.

    Hint See Extra for Experts in the Cosmic ComputersProblem for an example of constraint branching in AMPL.

    What to hand in Your AMPL code for implementing the branches. Your drawing of your branch-and-bound tree.

|
META FILEATTACHMENT attachment="800px-Koks_Brennstoff.jpg" attr="h" comment="" date="1203500128" name="800px-Koks_Brennstoff.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\CokeProduction\800px-Koks_Brennstoff.jpg" size="77315" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\CokeProduction\800px-Koks_Brennstoff.jpg" tmpFilename="" user="LaurenJackson" version="1"
META FILEATTACHMENT attachment="coke_map.jpg" attr="h" comment="" date="1203500160" name="coke_map.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\CokeProduction\coke_map.jpg" size="43023" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\CokeProduction\coke_map.jpg" tmpFilename="" user="LaurenJackson" version="1"

Revision 182008-04-28 - MichaelOSullivan

Line: 1 to 1
 
META TOPICPARENT name="SubmitCaseStudy" 
<-- Ready to Review -->
Line: 87 to 87
 
FORM FIELD CaseStudyType CaseStudyType DIYCaseStudy
FORM FIELD OperationsResearchTopics OperationsResearchTopics LinearProgramming, IntegerProgramming, MasterSlaveConstraints, FacilityLocationProblem
FORM FIELD ApplicationAreas ApplicationAreas Logistics, Industrial Planning, Fuel Manufacturing
Changed:
<
<		|*FORM FIELD ProblemDescription*|ProblemDescription|*THE COKE PRODUCTION PROBLEM*

Adapted from a real-world problem

Over 29% of world's coke is made in China. Recently market liberalization has lead to town and village enterprises, with uncertainty in future markets resulting in short-sighted resource use. There are currently many small cokemaking plants with relatively primitive technology. This has resulted in an industry with low transportation costs (as coke is supplied by many small local producers) but high pollution and energy use.

Figure 1 Coke from en.wikipedia.org/wiki/Image:Koks_Brennstoff.jpg

800px-Koks_Brennstoff.jpg

The government wants to move cokemaking to Shanxi, where they can establish bigger facilities. This plan will be more efficient, with less pollution, but will also result in higher transport costs (calculated from a GIS database). The plants in Shanxi will be built with one or more oven batteries, each making 75,000 tonnes of coke a year. The process these plants will use to convert coal to coke is "thermal decomposition". This process results in 1 tonne of coke produced for every 1.3 tonnes of coal processed.

The (simplified) problem we will model has the following details:

  1. There are six coal mines, each able to supply up to a certain amount of coal each year to the plants for processing
  2. There are six customers, each with a certain demand for coke each year
  3. There are six possible plant locations, each able to process a certain amount of coke each year

coke_map.jpg

Each plant has 6 possible sizes, with coke processing levels and associated construction costs shown below:

Size Cost
(kT/yr) (MRMB)
75 4.4
150 7.4
225 10.5
300 13.5
375 16.5
450 19.6

Each Mine has the following coal supply per year:

Mine 1 2 3 4 5 6
Coal Supply (kT/yr) 25.8 728 1456 40 36.9 1100

Each Customer has the following coke demand per year:

Customer 1 2 3 4 5 6
Coke Demand (kT/yr) 83 5.5 6.975 5.5 720.75 5.5

The transportation costs (RMB/kT) between the mines and the plants are as follows:

RMB/kT Plant 1 Plant 2 Plant 3 Plant 4 Plant 5 Plant 6
Mine 1 231737 46813 79337 195845 103445 45186
Mine 2 179622 267996 117602 200298 128184 49046
Mine 3 45170 93159 156241 218655 103802 119616
Mine 4 149925 254305 76423 123534 151784 104081
Mine 5 152301 205126 24321 66187 195559 88979
Mine 6 223934 132391 51004 122329 222927 54357

The transportation costs (RMB/kT) between the plants and the customers are as follows:

RMB/kT Plant 1 Plant 2 Plant 3 Plant 4 Plant 5 Plant 6
Customer 1 6736 42658 70414 45170 184679 111569
Customer 2 217266 227190 249640 203029 153531 117487
Customer 3 35936 28768 126316 2498 130317 74034
Customer 4 73446 52077 108368 75011 49827 62850
Customer 5 174664 177461 151589 153300 59916 135162
Customer 6 186302 189099 147026 164938 149836 286307  
>
>		|*FORM FIELD ProblemDescription*|ProblemDescription|*Adapted from a real-world problem*

Over 29% of world's coke is made in China. Recently market liberalization has lead to town and village enterprises, with uncertainty in future markets resulting in short-sighted resource use. There are currently many small cokemaking plants with relatively primitive technology. This has resulted in an industry with low transportation costs (as coke is supplied by many small local producers) but high pollution and energy use.

Figure 1 Coke from en.wikipedia.org/wiki/Image:Koks_Brennstoff.jpg

800px-Koks_Brennstoff.jpg

The government wants to move cokemaking to Shanxi, where they can establish bigger facilities. This plan will be more efficient, with less pollution, but will also result in higher transport costs (calculated from a GIS database). The plants in Shanxi will be built with one or more oven batteries, each making 75,000 tonnes of coke a year. The process these plants will use to convert coal to coke is "thermal decomposition". This process results in 1 tonne of coke produced for every 1.3 tonnes of coal processed.

The (simplified) problem we will model has the following details:

  1. There are six coal mines, each able to supply up to a certain amount of coal each year to the plants for processing
  2. There are six customers, each with a certain demand for coke each year
  3. There are six possible plant locations, each able to process a certain amount of coke each year

coke_map.jpg

Each plant has 6 possible sizes, with coke processing levels and associated construction costs shown below:

Size Cost
(kT/yr) (MRMB)
75 4.4
150 7.4
225 10.5
300 13.5
375 16.5
450 19.6

Each Mine has the following coal supply per year:

Mine 1 2 3 4 5 6
Coal Supply (kT/yr) 25.8 728 1456 40 36.9 1100

Each Customer has the following coke demand per year:

Customer 1 2 3 4 5 6
Coke Demand (kT/yr) 83 5.5 6.975 5.5 720.75 5.5

The transportation costs (RMB/kT) between the mines and the plants are as follows:

RMB/kT Plant 1 Plant 2 Plant 3 Plant 4 Plant 5 Plant 6
Mine 1 231737 46813 79337 195845 103445 45186
Mine 2 179622 267996 117602 200298 128184 49046
Mine 3 45170 93159 156241 218655 103802 119616
Mine 4 149925 254305 76423 123534 151784 104081
Mine 5 152301 205126 24321 66187 195559 88979
Mine 6 223934 132391 51004 122329 222927 54357

The transportation costs (RMB/kT) between the plants and the customers are as follows:

RMB/kT Plant 1 Plant 2 Plant 3 Plant 4 Plant 5 Plant 6
Customer 1 6736 42658 70414 45170 184679 111569
Customer 2 217266 227190 249640 203029 153531 117487
Customer 3 35936 28768 126316 2498 130317 74034
Customer 4 73446 52077 108368 75011 49827 62850
Customer 5 174664 177461 151589 153300 59916 135162
Customer 6 186302 189099 147026 164938 149836 286307  
 
FORM FIELD ProblemFormulation ProblemFormulation The formulation...
FORM FIELD ComputationalModel ComputationalModel The computational model...
FORM FIELD Results Results The results...

Revision 172008-04-23 - MichaelOSullivan

Line: 1 to 1
 
META TOPICPARENT name="SubmitCaseStudy"
Changed:
<
<
<-- Under Construction -->
>
>
<-- Ready to Review -->
 

Revision 162008-04-23 - MichaelOSullivan

Line: 1 to 1
 
META TOPICPARENT name="SubmitCaseStudy" 
<-- Under Construction -->
Line: 93 to 93
 
FORM FIELD Results Results The results...
FORM FIELD Conclusions Conclusions In conclusion...
|*FORM FIELD ExtraForExperts*|ExtraForExperts|This problem is similar to the Cosmic Computers Problem, but the facility location is a little different. Rather than face a decision about whether to build a plant or not, we need to determine what type of plant to build. This gives rise to the following variable:
\[ y_{ps} = 1 \text{ if plant $p$ is built with size $s$, 0 otherwise} \]

While solving the Coke Supply Chain Problem, the expression

\[ \sum_{s \in \text{sizes}} y_{ps} \]
will often be fractional. This means that the capacity of the plant
\[ \sum_{s \in \text{sizes}} C_s y_{ps} \]
where $C_s$ is the capacity of a plant of size $s$ will be between the capacities of two different size plants, e.g., 280 kT/yr is between 225 kT/yr plant and a 300 kT/yr plant. We could use constraints to remove the fractionality, e.g.,
\[ \begin{array}{r@{\,}l@{\quad\quad}l} \displaystyle \sum_{s \in \text{sizes}} C_s y_{ps} &amp;\leq 225 &amp; \text{(branching down)} \\ \displaystyle \sum_{s \in \text{sizes}} C_s y_{ps} &amp;\geq 300 &amp; \text{(branching up)} \end{array} \]

These branches will ensure plants have the right capacities, but will still not resolve fractionalities in the $y_{ps}$. However, if we want the capacity of plant $p$ to be $\leq$ 225, then we can remove all the $y_{ps}$ that allow for the capacity to be larger than 225:

\[ \sum_{s \in \text{sizes} | C_s > 225} y_{ps} = 0 \]

Conversely, if we want to branch up, i.e., the capacity is $\geq$ 300, then we can remove all the $y_{ps}$ that allow the capacity to be smaller than 300:

\[ \sum_{s \in \text{sizes} | C_s < 300} y_{ps} = 0 \]

Note For these branches to work properly, the possibility of building no plant must be modeled as building a plant with no capacity (i.e., $C_s$ = 0) for no cost. |

Changed:
<
<		|*FORM FIELD StudentTasks*|StudentTasks|
  1. Write AMPL model, data and script files (coke.mod, coke.dat and coke.run respectively) to solve the Coke Production Problem. Write a management summary for your solution.

    What to hand in Your 3 AMPL files. Your management summary.

  2. Experts Only Solve the LP relaxation of the Coke Supply Chain Problem integer programme. Using the branches described in Extra for Experts, use AMPL to perform branching on at least 4 nodes and draw the resulting branch-and-bound tree.

    Hint See Extra for Experts in the Cosmic ComputersProblem for an example of constraint branching.

    What to hand in Your AMPL code for implementing the branches. Your drawing of your branch-and-bound tree.

|
>
>		|*FORM FIELD StudentTasks*|StudentTasks|
  1. Write AMPL model, data and script files (coke.mod, coke.dat and coke.run respectively) to solve the Coke Production Problem. Write a management summary for your solution.

    What to hand in Your 3 AMPL files. Your management summary.

  2. Experts Only Solve the LP relaxation of the Coke Supply Chain Problem integer programme. Using the branches described in Extra for Experts, use AMPL to perform branching on at least 4 nodes and draw the resulting branch-and-bound tree.

    Hint See Extra for Experts in the Cosmic ComputersProblem for an example of constraint branching in AMPL.

    What to hand in Your AMPL code for implementing the branches. Your drawing of your branch-and-bound tree.

|
 
META FILEATTACHMENT attachment="800px-Koks_Brennstoff.jpg" attr="h" comment="" date="1203500128" name="800px-Koks_Brennstoff.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\CokeProduction\800px-Koks_Brennstoff.jpg" size="77315" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\CokeProduction\800px-Koks_Brennstoff.jpg" tmpFilename="" user="LaurenJackson" version="1"
META FILEATTACHMENT attachment="coke_map.jpg" attr="h" comment="" date="1203500160" name="coke_map.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\CokeProduction\coke_map.jpg" size="43023" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\CokeProduction\coke_map.jpg" tmpFilename="" user="LaurenJackson" version="1"
META FILEATTACHMENT attachment="latex6f834a945dc2e3c23f04a7ab04dfd506.png" attr="h" comment="" date="1208933146" name="latex6f834a945dc2e3c23f04a7ab04dfd506.png" stream="GLOB(0xa3aeab4)" tmpFilename="latex6f834a945dc2e3c23f04a7ab04dfd506.png" user="MichaelOSullivan" version="1"

Revision 152008-04-23 - MichaelOSullivan

Line: 1 to 1
 
META TOPICPARENT name="SubmitCaseStudy" 
<-- Under Construction -->
Line: 82 to 82
 

META FORM name="OpsRes.CaseStudyForm"
Changed:
<
<
FORM FIELD Title Title The Coke Supply Chain
>
>
FORM FIELD Title Title The Coke Supply Chain Problem
 
FORM FIELD DateSubmitted DateSubmitted 20 Feb 2008
FORM FIELD CaseStudyType CaseStudyType DIYCaseStudy
Changed:
<
<
FORM FIELD OperationsResearchTopics OperationsResearchTopics LinearProgramming, IntegerProgramming
>
>
FORM FIELD OperationsResearchTopics OperationsResearchTopics LinearProgramming, IntegerProgramming, MasterSlaveConstraints, FacilityLocationProblem
 
FORM FIELD ApplicationAreas ApplicationAreas Logistics, Industrial Planning, Fuel Manufacturing
Changed:
<
<		|*FORM FIELD ProblemDescription*|ProblemDescription|*THE COKE PRODUCTION PROBLEM*

Adapted from a real-world problem

Over 29% of world's coke is made in China. Recently market liberalization has lead to town and village enterprises, with uncertainty in future markets resulting in short-sighted resource use. There are currently many small cokemaking plants with relatively primitive technology. This has resulted in an industry with low transportation costs (as coke is supplied by many small local producers) but high pollution and energy use.

Figure 1 Coke en.wikipedia.org/wiki/Image:Koks_Brennstoff.jpg

800px-Koks_Brennstoff.jpg

The government wants to move cokemaking to Shanxi, where they can establish bigger facilities. This plan will be more efficient, with less pollution, but will also result in higher transport costs (calculated from a GIS database). The plants in Shanxi will be built with one or more oven batteries, each making 75,000 tonnes of coke a year. The process these plants will use to convert coal to coke is "thermal decomposition". This process results in 1 tonne of coke produced for every 1.3 tonnes of coal processed.

The (simplified) problem we will model has the following details:

  1. There are six coal mines, each able to supply up to a certain amount of coal each year to the plants for processing
  2. There are six customers, each with a certain demand for coke each year
  3. There are six possible plant locations, each able to process a certain amount of coke each year

coke_map.jpg

Each plant has 6 possible sizes, with coke processing levels and associated construction costs shown below:

Size Cost
(kT/yr) (MRMB)
75 4.4
150 7.4
225 10.5
300 13.5
375 16.5
450 19.6

Each Mine has the following coal supply per year:

Mine 1 2 3 4 5 6
Coal Supply (kT/yr) 25.8 728 1456 40 36.9 1100

Each Customer has the following coke demand per year:

Customer 1 2 3 4 5 6
Coke Demand (kT/yr) 83 5.5 6.975 5.5 720.75 5.5

The transportation costs (RMB/kT) between the mines and the plants are as follows:

RMB/kT Plant 1 Plant 2 Plant 3 Plant 4 Plant 5 Plant 6
Mine 1 231737 46813 79337 195845 103445 45186
Mine 2 179622 267996 117602 200298 128184 49046
Mine 3 45170 93159 156241 218655 103802 119616
Mine 4 149925 254305 76423 123534 151784 104081
Mine 5 152301 205126 24321 66187 195559 88979
Mine 6 223934 132391 51004 122329 222927 54357

The transportation costs (RMB/kT) between the plants and the customers are as follows:

RMB/kT Plant 1 Plant 2 Plant 3 Plant 4 Plant 5 Plant 6
Customer 1 6736 42658 70414 45170 184679 111569
Customer 2 217266 227190 249640 203029 153531 117487
Customer 3 35936 28768 126316 2498 130317 74034
Customer 4 73446 52077 108368 75011 49827 62850
Customer 5 174664 177461 151589 153300 59916 135162
Customer 6 186302 189099 147026 164938 149836 286307  
>
>		|*FORM FIELD ProblemDescription*|ProblemDescription|*THE COKE PRODUCTION PROBLEM*

Adapted from a real-world problem

Over 29% of world's coke is made in China. Recently market liberalization has lead to town and village enterprises, with uncertainty in future markets resulting in short-sighted resource use. There are currently many small cokemaking plants with relatively primitive technology. This has resulted in an industry with low transportation costs (as coke is supplied by many small local producers) but high pollution and energy use.

Figure 1 Coke from en.wikipedia.org/wiki/Image:Koks_Brennstoff.jpg

800px-Koks_Brennstoff.jpg

The government wants to move cokemaking to Shanxi, where they can establish bigger facilities. This plan will be more efficient, with less pollution, but will also result in higher transport costs (calculated from a GIS database). The plants in Shanxi will be built with one or more oven batteries, each making 75,000 tonnes of coke a year. The process these plants will use to convert coal to coke is "thermal decomposition". This process results in 1 tonne of coke produced for every 1.3 tonnes of coal processed.

The (simplified) problem we will model has the following details:

  1. There are six coal mines, each able to supply up to a certain amount of coal each year to the plants for processing
  2. There are six customers, each with a certain demand for coke each year
  3. There are six possible plant locations, each able to process a certain amount of coke each year

coke_map.jpg

Each plant has 6 possible sizes, with coke processing levels and associated construction costs shown below:

Size Cost
(kT/yr) (MRMB)
75 4.4
150 7.4
225 10.5
300 13.5
375 16.5
450 19.6

Each Mine has the following coal supply per year:

Mine 1 2 3 4 5 6
Coal Supply (kT/yr) 25.8 728 1456 40 36.9 1100

Each Customer has the following coke demand per year:

Customer 1 2 3 4 5 6
Coke Demand (kT/yr) 83 5.5 6.975 5.5 720.75 5.5

The transportation costs (RMB/kT) between the mines and the plants are as follows:

RMB/kT Plant 1 Plant 2 Plant 3 Plant 4 Plant 5 Plant 6
Mine 1 231737 46813 79337 195845 103445 45186
Mine 2 179622 267996 117602 200298 128184 49046
Mine 3 45170 93159 156241 218655 103802 119616
Mine 4 149925 254305 76423 123534 151784 104081
Mine 5 152301 205126 24321 66187 195559 88979
Mine 6 223934 132391 51004 122329 222927 54357

The transportation costs (RMB/kT) between the plants and the customers are as follows:

RMB/kT Plant 1 Plant 2 Plant 3 Plant 4 Plant 5 Plant 6
Customer 1 6736 42658 70414 45170 184679 111569
Customer 2 217266 227190 249640 203029 153531 117487
Customer 3 35936 28768 126316 2498 130317 74034
Customer 4 73446 52077 108368 75011 49827 62850
Customer 5 174664 177461 151589 153300 59916 135162
Customer 6 186302 189099 147026 164938 149836 286307  
 
FORM FIELD ProblemFormulation ProblemFormulation The formulation...
FORM FIELD ComputationalModel ComputationalModel The computational model...
FORM FIELD Results Results The results...
FORM FIELD Conclusions Conclusions In conclusion...
Changed:
<
<
FORM FIELD ExtraForExperts ExtraForExperts
|*FORM FIELD StudentTasks*|StudentTasks|*STUDENT TASKS*

1. Write AMPL model, data and script files (coke.mod, coke.dat and coke.run respectively) to solve The Coke Production Problem. Write a management summary for your solution.

What to hand in Your 3 AMPL files. Your management summary.

Extra for Experts' Tasks

1. In The Coke Production Problem the capacity of a plant is given by the sum (over all the different plant sizes) of the plant processing capacity multiplied by the binary variable indicating if that size plant will be constructed, e.g., sum {s in SIZES} Capacity[s] * Build[p, s] gives the capacity of plant p. Since the plants can only have certain capacity levels (corresponding to the plants) we can branch on the plant capacity expression, e.g., 

# This constraint ensures the capacity of Plant 1 is at least 225 kT/yr,
# i.e., a plant of size 3, 4, 5, or 6
subject to Up :
  sum {s in SIZES} Capacity[s] * Build['Plant 1', s] >= 225000;

These branches are another type of constraint branch. Implement 3 of these constraint branches starting at the root node, i.e., the LP relaxation solution. Make sure you check both sides of the branch, e.g., 

# This constraint ensures the capacity of Plant 1 is at least 225 kT/yr,
# i.e., a plant of size 3, 4, 5, or 6
subject to Up :
  sum {s in SIZES} Capacity[s] * Build['Plant 1', s] >= 225000;

and 

# This constraint ensures the capacity of Plant 1 is at most 150 kT/yr,
# i.e., a plant of size 1 or 2
subject to Down :
  sum {s in SIZES} Capacity[s] * Build['Plant 1', s] <= 150000;

Draw the branch-and-bound tree created by your branches.

What to hand in Your AMPL code for implementing the branches. Your drawing of your branch-and-bound tree.

|
>
>		|*FORM FIELD ExtraForExperts*|ExtraForExperts|This problem is similar to the Cosmic Computers Problem, but the facility location is a little different. Rather than face a decision about whether to build a plant or not, we need to determine what type of plant to build. This gives rise to the following variable:
\[ y_{ps} = 1 \text{ if plant $p$ is built with size $s$, 0 otherwise} \]

While solving the Coke Supply Chain Problem, the expression

\[ \sum_{s \in \text{sizes}} y_{ps} \]
will often be fractional. This means that the capacity of the plant
\[ \sum_{s \in \text{sizes}} C_s y_{ps} \]
where $C_s$ is the capacity of a plant of size $s$ will be between the capacities of two different size plants, e.g., 280 kT/yr is between 225 kT/yr plant and a 300 kT/yr plant. We could use constraints to remove the fractionality, e.g.,
\[ \begin{array}{r@{\,}l@{\quad\quad}l} \displaystyle \sum_{s \in \text{sizes}} C_s y_{ps} &amp;\leq 225 &amp; \text{(branching down)} \\ \displaystyle \sum_{s \in \text{sizes}} C_s y_{ps} &amp;\geq 300 &amp; \text{(branching up)} \end{array} \]

These branches will ensure plants have the right capacities, but will still not resolve fractionalities in the $y_{ps}$. However, if we want the capacity of plant $p$ to be $\leq$ 225, then we can remove all the $y_{ps}$ that allow for the capacity to be larger than 225:

\[ \sum_{s \in \text{sizes} | C_s > 225} y_{ps} = 0 \]

Conversely, if we want to branch up, i.e., the capacity is $\geq$ 300, then we can remove all the $y_{ps}$ that allow the capacity to be smaller than 300:

\[ \sum_{s \in \text{sizes} | C_s < 300} y_{ps} = 0 \]

Note For these branches to work properly, the possibility of building no plant must be modeled as building a plant with no capacity (i.e., $C_s$ = 0) for no cost. | |*FORM FIELD StudentTasks*|StudentTasks|

  1. Write AMPL model, data and script files (coke.mod, coke.dat and coke.run respectively) to solve the Coke Production Problem. Write a management summary for your solution.

    What to hand in Your 3 AMPL files. Your management summary.

  2. Experts Only Solve the LP relaxation of the Coke Supply Chain Problem integer programme. Using the branches described in Extra for Experts, use AMPL to perform branching on at least 4 nodes and draw the resulting branch-and-bound tree.

    Hint See Extra for Experts in the Cosmic ComputersProblem for an example of constraint branching.

    What to hand in Your AMPL code for implementing the branches. Your drawing of your branch-and-bound tree.

|
 
META FILEATTACHMENT attachment="800px-Koks_Brennstoff.jpg" attr="h" comment="" date="1203500128" name="800px-Koks_Brennstoff.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\CokeProduction\800px-Koks_Brennstoff.jpg" size="77315" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\CokeProduction\800px-Koks_Brennstoff.jpg" tmpFilename="" user="LaurenJackson" version="1"
META FILEATTACHMENT attachment="coke_map.jpg" attr="h" comment="" date="1203500160" name="coke_map.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\CokeProduction\coke_map.jpg" size="43023" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\CokeProduction\coke_map.jpg" tmpFilename="" user="LaurenJackson" version="1"
Added:
>
>
META FILEATTACHMENT attachment="latex6f834a945dc2e3c23f04a7ab04dfd506.png" attr="h" comment="" date="1208933146" name="latex6f834a945dc2e3c23f04a7ab04dfd506.png" stream="GLOB(0xa3aeab4)" tmpFilename="latex6f834a945dc2e3c23f04a7ab04dfd506.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latexf59c8c028fb191d065d6a20fa8b58ad4.png" attr="h" comment="" date="1208933147" name="latexf59c8c028fb191d065d6a20fa8b58ad4.png" stream="GLOB(0xa2dfe64)" tmpFilename="latexf59c8c028fb191d065d6a20fa8b58ad4.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latexc1aa8902c98c0ae0732323a987ba2bd9.png" attr="h" comment="" date="1208933147" name="latexc1aa8902c98c0ae0732323a987ba2bd9.png" stream="GLOB(0xa2e0188)" tmpFilename="latexc1aa8902c98c0ae0732323a987ba2bd9.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latexdcf1fc59557e250eed061a8c02867d44.png" attr="h" comment="" date="1208934097" name="latexdcf1fc59557e250eed061a8c02867d44.png" stream="GLOB(0xacc2594)" tmpFilename="latexdcf1fc59557e250eed061a8c02867d44.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latexfb492a77be777564ce3f1e7425e408e4.png" attr="h" comment="" date="1208934097" name="latexfb492a77be777564ce3f1e7425e408e4.png" stream="GLOB(0xabb95e8)" tmpFilename="latexfb492a77be777564ce3f1e7425e408e4.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latex813faf7551d19e746040859b8af4d580.png" attr="h" comment="" date="1208934098" name="latex813faf7551d19e746040859b8af4d580.png" stream="GLOB(0xabb152c)" tmpFilename="latex813faf7551d19e746040859b8af4d580.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latex249fcba5b94268daac8961654756a25c.png" attr="h" comment="" date="1208934098" name="latex249fcba5b94268daac8961654756a25c.png" stream="GLOB(0xabb18c8)" tmpFilename="latex249fcba5b94268daac8961654756a25c.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latex75ebf9389b5be72af0360b24bca5adee.png" attr="h" comment="" date="1208934098" name="latex75ebf9389b5be72af0360b24bca5adee.png" stream="GLOB(0xabb1850)" tmpFilename="latex75ebf9389b5be72af0360b24bca5adee.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latex3aea7233589aa721f711db94f601349b.png" attr="h" comment="" date="1208934098" name="latex3aea7233589aa721f711db94f601349b.png" stream="GLOB(0xabb17d8)" tmpFilename="latex3aea7233589aa721f711db94f601349b.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latex7af89fb055fd3b92240c2285dbbe8111.png" attr="h" comment="" date="1208934098" name="latex7af89fb055fd3b92240c2285dbbe8111.png" stream="GLOB(0xabb1afc)" tmpFilename="latex7af89fb055fd3b92240c2285dbbe8111.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latex65cd373241df8f5af7efc94023eda61a.png" attr="h" comment="" date="1208934098" name="latex65cd373241df8f5af7efc94023eda61a.png" stream="GLOB(0xabb1c88)" tmpFilename="latex65cd373241df8f5af7efc94023eda61a.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latex32fc80ae026cf4d1f4099205fde096f0.png" attr="h" comment="" date="1208934098" name="latex32fc80ae026cf4d1f4099205fde096f0.png" stream="GLOB(0xacc236c)" tmpFilename="latex32fc80ae026cf4d1f4099205fde096f0.png" user="MichaelOSullivan" version="1"
 
META TOPICMOVED by="MichaelOSullivan" date="1204454747" from="OpsRes.CokeProduction" to="OpsRes.CokeSupplyChain"

Revision 142008-04-23 - MichaelOSullivan

Line: 1 to 1
 
META TOPICPARENT name="SubmitCaseStudy" 
<-- Under Construction -->
Line: 87 to 87
 
FORM FIELD CaseStudyType CaseStudyType DIYCaseStudy
FORM FIELD OperationsResearchTopics OperationsResearchTopics LinearProgramming, IntegerProgramming
FORM FIELD ApplicationAreas ApplicationAreas Logistics, Industrial Planning, Fuel Manufacturing
Changed:
<
<		|*FORM FIELD ProblemDescription*|ProblemDescription|*THE COKE PRODUCTION PROBLEM*

Adapted from a real-world problem

Over 29% of world's coke is made in China. Recently market liberalization has lead to town and village enterprises, with uncertainty in future markets resulting in short-sighted resource use. There are currently many small cokemaking plants with relatively primitive technology. This has resulted in an industry with low transportation costs (as coke is supplied by many small local producers) but high pollution and energy use.

Figure 1 Coke: [https://en.wikipedia.org/wiki/Image:Koks_Brennstoff.jpg][https://en.wikipedia.org/wiki/Image:Koks_Brennstoff.jpg]]

800px-Koks_Brennstoff.jpg

The government wants to move cokemaking to Shanxi, where they can establish bigger facilities. This plan will be more efficient, with less pollution, but will also result in higher transport costs (calculated from a GIS database). The plants in Shanxi will be built with one or more oven batteries, each making 75,000 tonnes of coke a year. The process these plants will use to convert coal to coke is "thermal decomposition". This process results in 1 tonne of coke produced for every 1.3 tonnes of coal processed.

The (simplified) problem we will model has the following details:

  1. There are six coal mines, each able to supply up to a certain amount of coal each year to the plants for processing
  2. There are six customers, each with a certain demand for coke each year
  3. There are six possible plant locations, each able to process a certain amount of coke each year

coke_map.jpg

Each plant has 6 possible sizes, with coke processing levels and associated construction costs shown below:

Size Cost
(kT/yr) (MRMB)
75 4.4
150 7.4
225 10.5
300 13.5
375 16.5
450 19.6

Each Mine has the following coal supply per year:

Mine 1 2 3 4 5 6
Coal Supply (kT/yr) 25.8 728 1456 40 36.9 1100

Each Customer has the following coke demand per year:

Customer 1 2 3 4 5 6
Coke Demand (kT/yr) 83 5.5 6.975 5.5 720.75 5.5

The transportation costs (RMB/kT) between the mines and the plants are as follows:

RMB/kT Plant 1 Plant 2 Plant 3 Plant 4 Plant 5 Plant 6
Mine 1 231737 46813 79337 195845 103445 45186
Mine 2 179622 267996 117602 200298 128184 49046
Mine 3 45170 93159 156241 218655 103802 119616
Mine 4 149925 254305 76423 123534 151784 104081
Mine 5 152301 205126 24321 66187 195559 88979
Mine 6 223934 132391 51004 122329 222927 54357

The transportation costs (RMB/kT) between the plants and the customers are as follows:

RMB/kT Plant 1 Plant 2 Plant 3 Plant 4 Plant 5 Plant 6
Customer 1 6736 42658 70414 45170 184679 111569
Customer 2 217266 227190 249640 203029 153531 117487
Customer 3 35936 28768 126316 2498 130317 74034
Customer 4 73446 52077 108368 75011 49827 62850
Customer 5 174664 177461 151589 153300 59916 135162
Customer 6 186302 189099 147026 164938 149836 286307  
>
>		|*FORM FIELD ProblemDescription*|ProblemDescription|*THE COKE PRODUCTION PROBLEM*

Adapted from a real-world problem

Over 29% of world's coke is made in China. Recently market liberalization has lead to town and village enterprises, with uncertainty in future markets resulting in short-sighted resource use. There are currently many small cokemaking plants with relatively primitive technology. This has resulted in an industry with low transportation costs (as coke is supplied by many small local producers) but high pollution and energy use.

Figure 1 Coke en.wikipedia.org/wiki/Image:Koks_Brennstoff.jpg

800px-Koks_Brennstoff.jpg

The government wants to move cokemaking to Shanxi, where they can establish bigger facilities. This plan will be more efficient, with less pollution, but will also result in higher transport costs (calculated from a GIS database). The plants in Shanxi will be built with one or more oven batteries, each making 75,000 tonnes of coke a year. The process these plants will use to convert coal to coke is "thermal decomposition". This process results in 1 tonne of coke produced for every 1.3 tonnes of coal processed.

The (simplified) problem we will model has the following details:

  1. There are six coal mines, each able to supply up to a certain amount of coal each year to the plants for processing
  2. There are six customers, each with a certain demand for coke each year
  3. There are six possible plant locations, each able to process a certain amount of coke each year

coke_map.jpg

Each plant has 6 possible sizes, with coke processing levels and associated construction costs shown below:

Size Cost
(kT/yr) (MRMB)
75 4.4
150 7.4
225 10.5
300 13.5
375 16.5
450 19.6

Each Mine has the following coal supply per year:

Mine 1 2 3 4 5 6
Coal Supply (kT/yr) 25.8 728 1456 40 36.9 1100

Each Customer has the following coke demand per year:

Customer 1 2 3 4 5 6
Coke Demand (kT/yr) 83 5.5 6.975 5.5 720.75 5.5

The transportation costs (RMB/kT) between the mines and the plants are as follows:

RMB/kT Plant 1 Plant 2 Plant 3 Plant 4 Plant 5 Plant 6
Mine 1 231737 46813 79337 195845 103445 45186
Mine 2 179622 267996 117602 200298 128184 49046
Mine 3 45170 93159 156241 218655 103802 119616
Mine 4 149925 254305 76423 123534 151784 104081
Mine 5 152301 205126 24321 66187 195559 88979
Mine 6 223934 132391 51004 122329 222927 54357

The transportation costs (RMB/kT) between the plants and the customers are as follows:

RMB/kT Plant 1 Plant 2 Plant 3 Plant 4 Plant 5 Plant 6
Customer 1 6736 42658 70414 45170 184679 111569
Customer 2 217266 227190 249640 203029 153531 117487
Customer 3 35936 28768 126316 2498 130317 74034
Customer 4 73446 52077 108368 75011 49827 62850
Customer 5 174664 177461 151589 153300 59916 135162
Customer 6 186302 189099 147026 164938 149836 286307  
 
FORM FIELD ProblemFormulation ProblemFormulation The formulation...
FORM FIELD ComputationalModel ComputationalModel The computational model...
FORM FIELD Results Results The results...

Revision 132008-04-23 - MichaelOSullivan

Line: 1 to 1
 
META TOPICPARENT name="SubmitCaseStudy" 
<-- Under Construction -->
Line: 87 to 87
 
FORM FIELD CaseStudyType CaseStudyType DIYCaseStudy
FORM FIELD OperationsResearchTopics OperationsResearchTopics LinearProgramming, IntegerProgramming
FORM FIELD ApplicationAreas ApplicationAreas Logistics, Industrial Planning, Fuel Manufacturing
Changed:
<
<		|*FORM FIELD ProblemDescription*|ProblemDescription|*THE COKE PRODUCTION PROBLEM*

Adapted from a real-world problem

Over 29% of world’s coke is made in China. Recently market liberalization has lead to town and village enterprises, with uncertainty in future markets resulting in short-sighted resource use. There are currently many small cokemaking plants with relatively primitive technology. This has resulted in an industry with low transportation costs (as coke is supplied by many small local producers) but high pollution and energy use.

Coke Link to reference en.wikipedia.org/wiki/Image:Koks_Brennstoff.jpg

800px-Koks_Brennstoff.jpg

The government wants to move cokemaking to Shanxi, where they can establish bigger facilities. This plan will be more efficient, with less pollution, but will also result in higher transport costs (calculated from a GIS database). The plants in Shanxi will be built with one or more oven batteries, each making 75,000 tonnes of coke a year. The process these plants will use to convert coal to coke is "thermal decomposition". This process results in 1 tonne of coke produced for every 1.3 tonnes of coal processed.

The (simplified) problem we will model has the following details:

  1. There are six coal mines, each able to supply up to a certain amount of coal each year to the plants for processing
  2. There are six customers, each with a certain demand for coke each year
  3. There are six possible plant locations, each able to process a certain amount of coke each year

coke_map.jpg

Each plant has 6 possible sizes, with coke processing levels and associated construction costs shown below:

Size Cost
(kT/yr) (MRMB)
75 4.4
150 7.4
225 10.5
300 13.5
375 16.5
450 19.6

Each Mine has the following coal supply per year:

Mine 1 2 3 4 5 6
Coal Supply (kT/yr) 25.8 728 1456 40 36.9 1100

Each Customer has the following coke demand per year:

Customer 1 2 3 4 5 6
Coke Demand (kT/yr) 83 5.5 6.975 5.5 720.75 5.5

The transportation costs (RMB/kT) between the mines and the plants are as follows:

RMB/kT Plant 1 Plant 2 Plant 3 Plant 4 Plant 5 Plant 6
Mine 1 231737 46813 79337 195845 103445 45186
Mine 2 179622 267996 117602 200298 128184 49046
Mine 3 45170 93159 156241 218655 103802 119616
Mine 4 149925 254305 76423 123534 151784 104081
Mine 5 152301 205126 24321 66187 195559 88979
Mine 6 223934 132391 51004 122329 222927 54357

The transportation costs (RMB/kT) between the plants and the customers are as follows:

RMB/kT Plant 1 Plant 2 Plant 3 Plant 4 Plant 5 Plant 6
Customer 1 6736 42658 70414 45170 184679 111569
Customer 2 217266 227190 249640 203029 153531 117487
Customer 3 35936 28768 126316 2498 130317 74034
Customer 4 73446 52077 108368 75011 49827 62850
Customer 5 174664 177461 151589 153300 59916 135162
Customer 6 186302 189099 147026 164938 149836 286307  
>
>		|*FORM FIELD ProblemDescription*|ProblemDescription|*THE COKE PRODUCTION PROBLEM*

Adapted from a real-world problem

Over 29% of world's coke is made in China. Recently market liberalization has lead to town and village enterprises, with uncertainty in future markets resulting in short-sighted resource use. There are currently many small cokemaking plants with relatively primitive technology. This has resulted in an industry with low transportation costs (as coke is supplied by many small local producers) but high pollution and energy use.

Figure 1 Coke: [https://en.wikipedia.org/wiki/Image:Koks_Brennstoff.jpg][https://en.wikipedia.org/wiki/Image:Koks_Brennstoff.jpg]]

800px-Koks_Brennstoff.jpg

The government wants to move cokemaking to Shanxi, where they can establish bigger facilities. This plan will be more efficient, with less pollution, but will also result in higher transport costs (calculated from a GIS database). The plants in Shanxi will be built with one or more oven batteries, each making 75,000 tonnes of coke a year. The process these plants will use to convert coal to coke is "thermal decomposition". This process results in 1 tonne of coke produced for every 1.3 tonnes of coal processed.

The (simplified) problem we will model has the following details:

  1. There are six coal mines, each able to supply up to a certain amount of coal each year to the plants for processing
  2. There are six customers, each with a certain demand for coke each year
  3. There are six possible plant locations, each able to process a certain amount of coke each year

coke_map.jpg

Each plant has 6 possible sizes, with coke processing levels and associated construction costs shown below:

Size Cost
(kT/yr) (MRMB)
75 4.4
150 7.4
225 10.5
300 13.5
375 16.5
450 19.6

Each Mine has the following coal supply per year:

Mine 1 2 3 4 5 6
Coal Supply (kT/yr) 25.8 728 1456 40 36.9 1100

Each Customer has the following coke demand per year:

Customer 1 2 3 4 5 6
Coke Demand (kT/yr) 83 5.5 6.975 5.5 720.75 5.5

The transportation costs (RMB/kT) between the mines and the plants are as follows:

RMB/kT Plant 1 Plant 2 Plant 3 Plant 4 Plant 5 Plant 6
Mine 1 231737 46813 79337 195845 103445 45186
Mine 2 179622 267996 117602 200298 128184 49046
Mine 3 45170 93159 156241 218655 103802 119616
Mine 4 149925 254305 76423 123534 151784 104081
Mine 5 152301 205126 24321 66187 195559 88979
Mine 6 223934 132391 51004 122329 222927 54357

The transportation costs (RMB/kT) between the plants and the customers are as follows:

RMB/kT Plant 1 Plant 2 Plant 3 Plant 4 Plant 5 Plant 6
Customer 1 6736 42658 70414 45170 184679 111569
Customer 2 217266 227190 249640 203029 153531 117487
Customer 3 35936 28768 126316 2498 130317 74034
Customer 4 73446 52077 108368 75011 49827 62850
Customer 5 174664 177461 151589 153300 59916 135162
Customer 6 186302 189099 147026 164938 149836 286307  
 
FORM FIELD ProblemFormulation ProblemFormulation The formulation...
FORM FIELD ComputationalModel ComputationalModel The computational model...
FORM FIELD Results Results The results...

Revision 122008-04-02 - MichaelOSullivan

Line: 1 to 1
 
META TOPICPARENT name="SubmitCaseStudy" 
<-- Under Construction -->
Line: 18 to 18
  -->
Changed:
<
<		%BEGINLATEXPREAMBLE% \usepackage{amsmath}
>
>		%BEGINLATEXPREAMBLE% \usepackage{amsmath}
 %ENDLATEXPREAMBLE%

Case Study: The Coke Supply Chain Problem

Line: 40 to 41
  Return to top
Changed:
<
<

Computational Model

>
>

Computational Model

 

The computational model...

Line: 48 to 49
  Return to top
Changed:
<
<

Results

>
>

Results

 

The results...

Line: 56 to 57
  Return to top
Changed:
<
<

Conclusions

>
>

Conclusions

 

In conclusion...

Revision 112008-03-02 - MichaelOSullivan

Line: 1 to 1
 
META TOPICPARENT name="SubmitCaseStudy" 
<-- Under Construction -->
Line: 81 to 81
 

META FORM name="OpsRes.CaseStudyForm"
Changed:
<
<
FORM FIELD Title Title CokeProduction
>
>
FORM FIELD Title Title The Coke Supply Chain
 
FORM FIELD DateSubmitted DateSubmitted 20 Feb 2008
FORM FIELD CaseStudyType CaseStudyType DIYCaseStudy
FORM FIELD OperationsResearchTopics OperationsResearchTopics LinearProgramming, IntegerProgramming
Line: 95 to 95
 |*FORM FIELD StudentTasks*|StudentTasks|*STUDENT TASKS*

1. Write AMPL model, data and script files (coke.mod, coke.dat and coke.run respectively) to solve The Coke Production Problem. Write a management summary for your solution.

What to hand in Your 3 AMPL files. Your management summary.

Extra for Experts' Tasks

1. In The Coke Production Problem the capacity of a plant is given by the sum (over all the different plant sizes) of the plant processing capacity multiplied by the binary variable indicating if that size plant will be constructed, e.g., sum {s in SIZES} Capacity[s] * Build[p, s] gives the capacity of plant p. Since the plants can only have certain capacity levels (corresponding to the plants) we can branch on the plant capacity expression, e.g., 

# This constraint ensures the capacity of Plant 1 is at least 225 kT/yr,
# i.e., a plant of size 3, 4, 5, or 6
subject to Up :
  sum {s in SIZES} Capacity[s] * Build['Plant 1', s] >= 225000;

These branches are another type of constraint branch. Implement 3 of these constraint branches starting at the root node, i.e., the LP relaxation solution. Make sure you check both sides of the branch, e.g., 

# This constraint ensures the capacity of Plant 1 is at least 225 kT/yr,
# i.e., a plant of size 3, 4, 5, or 6
subject to Up :
  sum {s in SIZES} Capacity[s] * Build['Plant 1', s] >= 225000;

and 

# This constraint ensures the capacity of Plant 1 is at most 150 kT/yr,
# i.e., a plant of size 1 or 2
subject to Down :
  sum {s in SIZES} Capacity[s] * Build['Plant 1', s] <= 150000;

Draw the branch-and-bound tree created by your branches.

What to hand in Your AMPL code for implementing the branches. Your drawing of your branch-and-bound tree.

|
META FILEATTACHMENT attachment="800px-Koks_Brennstoff.jpg" attr="h" comment="" date="1203500128" name="800px-Koks_Brennstoff.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\CokeProduction\800px-Koks_Brennstoff.jpg" size="77315" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\CokeProduction\800px-Koks_Brennstoff.jpg" tmpFilename="" user="LaurenJackson" version="1"
META FILEATTACHMENT attachment="coke_map.jpg" attr="h" comment="" date="1203500160" name="coke_map.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\CokeProduction\coke_map.jpg" size="43023" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\CokeProduction\coke_map.jpg" tmpFilename="" user="LaurenJackson" version="1"
Added:
>
>
META TOPICMOVED by="MichaelOSullivan" date="1204454747" from="OpsRes.CokeProduction" to="OpsRes.CokeSupplyChain"

Revision 102008-03-02 - TWikiAdminUser

Line: 1 to 1
 
META TOPICPARENT name="SubmitCaseStudy" 
<-- Under Construction -->
Line: 85 to 85
 
FORM FIELD DateSubmitted DateSubmitted 20 Feb 2008
FORM FIELD CaseStudyType CaseStudyType DIYCaseStudy
FORM FIELD OperationsResearchTopics OperationsResearchTopics LinearProgramming, IntegerProgramming
Changed:
<
<
FORM FIELD ApplicationAreas ApplicationAreas Logistics
>
>
FORM FIELD ApplicationAreas ApplicationAreas Logistics, Industrial Planning, Fuel Manufacturing
 |*FORM FIELD ProblemDescription*|ProblemDescription|*THE COKE PRODUCTION PROBLEM*

Adapted from a real-world problem

Over 29% of world’s coke is made in China. Recently market liberalization has lead to town and village enterprises, with uncertainty in future markets resulting in short-sighted resource use. There are currently many small cokemaking plants with relatively primitive technology. This has resulted in an industry with low transportation costs (as coke is supplied by many small local producers) but high pollution and energy use.

Coke Link to reference en.wikipedia.org/wiki/Image:Koks_Brennstoff.jpg

800px-Koks_Brennstoff.jpg

The government wants to move cokemaking to Shanxi, where they can establish bigger facilities. This plan will be more efficient, with less pollution, but will also result in higher transport costs (calculated from a GIS database). The plants in Shanxi will be built with one or more oven batteries, each making 75,000 tonnes of coke a year. The process these plants will use to convert coal to coke is "thermal decomposition". This process results in 1 tonne of coke produced for every 1.3 tonnes of coal processed.

The (simplified) problem we will model has the following details:

  1. There are six coal mines, each able to supply up to a certain amount of coal each year to the plants for processing
  2. There are six customers, each with a certain demand for coke each year
  3. There are six possible plant locations, each able to process a certain amount of coke each year

coke_map.jpg

Each plant has 6 possible sizes, with coke processing levels and associated construction costs shown below:

Size Cost
(kT/yr) (MRMB)
75 4.4
150 7.4
225 10.5
300 13.5
375 16.5
450 19.6

Each Mine has the following coal supply per year:

Mine 1 2 3 4 5 6
Coal Supply (kT/yr) 25.8 728 1456 40 36.9 1100

Each Customer has the following coke demand per year:

Customer 1 2 3 4 5 6
Coke Demand (kT/yr) 83 5.5 6.975 5.5 720.75 5.5

The transportation costs (RMB/kT) between the mines and the plants are as follows:

RMB/kT Plant 1 Plant 2 Plant 3 Plant 4 Plant 5 Plant 6
Mine 1 231737 46813 79337 195845 103445 45186
Mine 2 179622 267996 117602 200298 128184 49046
Mine 3 45170 93159 156241 218655 103802 119616
Mine 4 149925 254305 76423 123534 151784 104081
Mine 5 152301 205126 24321 66187 195559 88979
Mine 6 223934 132391 51004 122329 222927 54357

The transportation costs (RMB/kT) between the plants and the customers are as follows:

RMB/kT Plant 1 Plant 2 Plant 3 Plant 4 Plant 5 Plant 6
Customer 1 6736 42658 70414 45170 184679 111569
Customer 2 217266 227190 249640 203029 153531 117487
Customer 3 35936 28768 126316 2498 130317 74034
Customer 4 73446 52077 108368 75011 49827 62850
Customer 5 174664 177461 151589 153300 59916 135162
Customer 6 186302 189099 147026 164938 149836 286307  
FORM FIELD ProblemFormulation ProblemFormulation The formulation...
FORM FIELD ComputationalModel ComputationalModel The computational model...
Line: 93 to 93
 
FORM FIELD Conclusions Conclusions In conclusion...
FORM FIELD ExtraForExperts ExtraForExperts
|*FORM FIELD StudentTasks*|StudentTasks|*STUDENT TASKS*

1. Write AMPL model, data and script files (coke.mod, coke.dat and coke.run respectively) to solve The Coke Production Problem. Write a management summary for your solution.

What to hand in Your 3 AMPL files. Your management summary.

Extra for Experts' Tasks

1. In The Coke Production Problem the capacity of a plant is given by the sum (over all the different plant sizes) of the plant processing capacity multiplied by the binary variable indicating if that size plant will be constructed, e.g., sum {s in SIZES} Capacity[s] * Build[p, s] gives the capacity of plant p. Since the plants can only have certain capacity levels (corresponding to the plants) we can branch on the plant capacity expression, e.g., 

# This constraint ensures the capacity of Plant 1 is at least 225 kT/yr,
# i.e., a plant of size 3, 4, 5, or 6
subject to Up :
  sum {s in SIZES} Capacity[s] * Build['Plant 1', s] >= 225000;

These branches are another type of constraint branch. Implement 3 of these constraint branches starting at the root node, i.e., the LP relaxation solution. Make sure you check both sides of the branch, e.g., 

# This constraint ensures the capacity of Plant 1 is at least 225 kT/yr,
# i.e., a plant of size 3, 4, 5, or 6
subject to Up :
  sum {s in SIZES} Capacity[s] * Build['Plant 1', s] >= 225000;

and 

# This constraint ensures the capacity of Plant 1 is at most 150 kT/yr,
# i.e., a plant of size 1 or 2
subject to Down :
  sum {s in SIZES} Capacity[s] * Build['Plant 1', s] <= 150000;

Draw the branch-and-bound tree created by your branches.

What to hand in Your AMPL code for implementing the branches. Your drawing of your branch-and-bound tree.

|
Changed:
<
<
META FILEATTACHMENT attachment="800px-Koks_Brennstoff.jpg" attr="" comment="" date="1203500128" name="800px-Koks_Brennstoff.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\CokeProduction\800px-Koks_Brennstoff.jpg" size="77315" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\CokeProduction\800px-Koks_Brennstoff.jpg" tmpFilename="" user="LaurenJackson" version="1"
META FILEATTACHMENT attachment="coke_map.jpg" attr="" comment="" date="1203500160" name="coke_map.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\CokeProduction\coke_map.jpg" size="43023" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\CokeProduction\coke_map.jpg" tmpFilename="" user="LaurenJackson" version="1"
>
>
META FILEATTACHMENT attachment="800px-Koks_Brennstoff.jpg" attr="h" comment="" date="1203500128" name="800px-Koks_Brennstoff.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\CokeProduction\800px-Koks_Brennstoff.jpg" size="77315" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\CokeProduction\800px-Koks_Brennstoff.jpg" tmpFilename="" user="LaurenJackson" version="1"
META FILEATTACHMENT attachment="coke_map.jpg" attr="h" comment="" date="1203500160" name="coke_map.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\CokeProduction\coke_map.jpg" size="43023" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\CokeProduction\coke_map.jpg" tmpFilename="" user="LaurenJackson" version="1"

Revision 92008-03-01 - TWikiAdminUser

Line: 1 to 1
 
META TOPICPARENT name="SubmitCaseStudy" 
<-- Under Construction -->
Deleted:
<
<
<-- Ready to Review -->
 

Revision 82008-03-01 - TWikiAdminUser

Line: 1 to 1
 
META TOPICPARENT name="SubmitCaseStudy" 
<-- Under Construction -->
Added:
>
>
<-- Ready to Review -->
 

Revision 72008-02-23 - MichaelOSullivan

Line: 1 to 1
 
META TOPICPARENT name="SubmitCaseStudy"
Added:
>
>
<-- Under Construction -->
 

Revision 62008-02-20 - LaurenJackson

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

Revision 52008-02-20 - LaurenJackson

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

Revision 42008-02-20 - LaurenJackson

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

Revision 32008-02-20 - LaurenJackson

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

Revision 22008-02-20 - LaurenJackson

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

Revision 12008-02-20 - LaurenJackson

Line: 1 to 1
Added:
>
>
META TOPICPARENT name="SubmitCaseStudy" 
<--
This template controls both the look and functionality of case study topics.
You should not need to alter the layout, only edit the data using the form above.


Set the view and edit templates:
Comment out the next line to use the TWiki default view 
 
Comment out the next line to use the TWiki default edit  
-->

<--
This topic can only be changed by:  
-->

Case Study: The Coke Supply Chain Problem

Submitted: 20 Feb 2008

Operations Research Topics: LinearProgramming, IntegerProgramming, MasterSlaveConstraints, FacilityLocationProblem

Application Areas: Logistics, Industrial Planning, Fuel Manufacturing

Contents

Problem Description

Adapted from a real-world problem

Over 29% of world's coke is made in China. Recently market liberalization has lead to town and village enterprises, with uncertainty in future markets resulting in short-sighted resource use. There are currently many small cokemaking plants with relatively primitive technology. This has resulted in an industry with low transportation costs (as coke is supplied by many small local producers) but high pollution and energy use.

Figure 1 Coke from en.wikipedia.org/wiki/Image:Koks_Brennstoff.jpg

800px-Koks_Brennstoff.jpg

The government wants to move cokemaking to Shanxi, where they can establish bigger facilities. This plan will be more efficient, with less pollution, but will also result in higher transport costs (calculated from a GIS database). The plants in Shanxi will be built with one or more oven batteries, each making 75,000 tonnes of coke a year. The process these plants will use to convert coal to coke is "thermal decomposition". This process results in 1 tonne of coke produced for every 1.3 tonnes of coal processed.

The (simplified) problem we will model has the following details:

  1. There are six coal mines, each able to supply up to a certain amount of coal each year to the plants for processing
  2. There are six customers, each with a certain demand for coke each year
  3. There are six possible plant locations, each able to process a certain amount of coke each year

coke_map.jpg

Each plant has 6 possible sizes, with coke processing levels and associated construction costs shown below:

Size Cost
(kT/yr) (MRMB)
75 4.4
150 7.4
225 10.5
300 13.5
375 16.5
450 19.6

Each Mine has the following coal supply per year:

Mine 1 2 3 4 5 6
Coal Supply (kT/yr) 25.8 728 1456 40 36.9 1100

Each Customer has the following coke demand per year:

Customer 1 2 3 4 5 6
Coke Demand (kT/yr) 83 5.5 6.975 5.5 720.75 5.5

The transportation costs (RMB/kT) between the mines and the plants are as follows:

RMB/kT Plant 1 Plant 2 Plant 3 Plant 4 Plant 5 Plant 6
Mine 1 231737 46813 79337 195845 103445 45186
Mine 2 179622 267996 117602 200298 128184 49046
Mine 3 45170 93159 156241 218655 103802 119616
Mine 4 149925 254305 76423 123534 151784 104081
Mine 5 152301 205126 24321 66187 195559 88979
Mine 6 223934 132391 51004 122329 222927 54357

The transportation costs (RMB/kT) between the plants and the customers are as follows:

RMB/kT Plant 1 Plant 2 Plant 3 Plant 4 Plant 5 Plant 6
Customer 1 6736 42658 70414 45170 184679 111569
Customer 2 217266 227190 249640 203029 153531 117487
Customer 3 35936 28768 126316 2498 130317 74034
Customer 4 73446 52077 108368 75011 49827 62850
Customer 5 174664 177461 151589 153300 59916 135162
Customer 6 186302 189099 147026 164938 149836 286307

Return to top

Problem Formulation

The formulation...

Return to top

Computational Model

The computational model...

Return to top

Results

The results...

Return to top

Conclusions

In conclusion...

Return to top

Extra for Experts

This problem is similar to the Cosmic Computers Problem, but the facility location is a little different. Rather than face a decision about whether to build a plant or not, we need to determine what type of plant to build. This gives rise to the following variable:

\[ y_{ps} = 1 \text{ if plant $p$ is built with size $s$, 0 otherwise} \]

While solving the Coke Supply Chain Problem, the expression

\[ \sum_{s \in \text{sizes}} y_{ps} \]
will often be fractional. This means that the capacity of the plant
\[ \sum_{s \in \text{sizes}} C_s y_{ps} \]
where $C_s$ is the capacity of a plant of size $s$ will be between the capacities of two different size plants, e.g., 280 kT/yr is between 225 kT/yr plant and a 300 kT/yr plant. We could use constraints to remove the fractionality, e.g.,
\[ \begin{array}{r@{\,}l@{\quad\quad}l} \displaystyle \sum_{s \in \text{sizes}} C_s y_{ps} &amp;\leq 225 &amp; \text{(branching down)} \\ \displaystyle \sum_{s \in \text{sizes}} C_s y_{ps} &amp;\geq 300 &amp; \text{(branching up)} \end{array} \]

These branches will ensure plants have the right capacities, but will still not resolve fractionalities in the $y_{ps}$. However, if we want the capacity of plant $p$ to be $\leq$ 225, then we can remove all the $y_{ps}$ that allow for the capacity to be larger than 225:

\[ \sum_{s \in \text{sizes} | C_s > 225} y_{ps} = 0 \]

Conversely, if we want to branch up, i.e., the capacity is $\geq$ 300, then we can remove all the $y_{ps}$ that allow the capacity to be smaller than 300:

\[ \sum_{s \in \text{sizes} | C_s < 300} y_{ps} = 0 \]

Note For these branches to work properly, the possibility of building no plant must be modelled as building a plant with no capacity (i.e., $C_s$ = 0) for no cost.

Return to top

Student Tasks

  1. Write AMPL model, data and script files (coke.mod, coke.dat and coke.run respectively) to solve the Coke Production Problem. Write a management summary for your solution.

    What to hand in Your 3 AMPL files. Your management summary.

  2. Experts Only Solve the LP relaxation of the Coke Supply Chain Problem integer programme. Using the branches described in Extra for Experts, use AMPL to perform branching on at least 4 nodes and draw the resulting branch-and-bound tree.

    Hint See Extra for Experts in the Cosmic ComputersProblem for an example of constraint branching in AMPL.

    What to hand in Your AMPL code for implementing the branches. Your drawing of your branch-and-bound tree.

Return to top

META FORM name="OpsRes.CaseStudyForm"
FORM FIELD Title Title CokeProduction
FORM FIELD DateSubmitted DateSubmitted 20 Feb 2008
FORM FIELD OperationsResearchTopics OperationsResearchTopics LinearProgramming, IntegerProgramming
FORM FIELD ApplicationAreas ApplicationAreas Logistics
|*FORM FIELD ProblemDescription*|ProblemDescription|*THE COKE PRODUCTION PROBLEM*

Adapted from a real-world problem

Over 29% of world’s coke is made in China. Recently market liberalization has lead to town and village enterprises, with uncertainty in future markets resulting in short-sighted resource use. There are currently many small cokemaking plants with relatively primitive technology. This has resulted in an industry with low transportation costs (as coke is supplied by many small local producers) but high pollution and energy use.

Coke Link to reference en.wikipedia.org/wiki/Image:Koks_Brennstoff.jpg

The government wants to move cokemaking to Shanxi, where they can establish bigger facilities. This plan will be more efficient, with less pollution, but will also result in higher transport costs (calculated from a GIS database). The plants in Shanxi will be built with one or more oven batteries, each making 75,000 tonnes of coke a year. The process these plants will use to convert coal to coke is "thermal decomposition". This process results in 1 tonne of coke produced for every 1.3 tonnes of coal processed.

The (simplified) problem we will model has the following details:

  1. There are six coal mines, each able to supply up to a certain amount of coal each year to the plants for processing
  2. There are six customers, each with a certain demand for coke each year
  3. There are six possible plant locations, each able to process a certain amount of coke each year

Each plant has 6 possible sizes, with coke processing levels and associated construction costs shown below:

Size Cost
(kT/yr) (MRMB)
75 4.4
150 7.4
225 10.5
300 13.5
375 16.5
450 19.6

Each Mine has the following coal supply per year:

Mine 1 2 3 4 5 6
Coal Supply (kT/yr) 25.8 728 1456 40 36.9 1100

Each Customer has the following coke demand per year:

Customer 1 2 3 4 5 6
Coke Demand (kT/yr) 83 5.5 6.975 5.5 720.75 5.5

The transportation costs (RMB/kT) between the mines and the plants are as follows:

RMB/kT Plant 1 Plant 2 Plant 3 Plant 4 Plant 5 Plant 6
Mine 1 231737 46813 79337 195845 103445 45186
Mine 2 179622 267996 117602 200298 128184 49046
Mine 3 45170 93159 156241 218655 103802 119616
Mine 4 149925 254305 76423 123534 151784 104081
Mine 5 152301 205126 24321 66187 195559 88979
Mine 6 223934 132391 51004 122329 222927 54357

The transportation costs (RMB/kT) between the plants and the customers are as follows:

RMB/kT Plant 1 Plant 2 Plant 3 Plant 4 Plant 5 Plant 6
Customer 1 6736 42658 70414 45170 184679 111569
Customer 2 217266 227190 249640 203029 153531 117487
Customer 3 35936 28768 126316 2498 130317 74034
Customer 4 73446 52077 108368 75011 49827 62850
Customer 5 174664 177461 151589 153300 59916 135162
Customer 6 186302 189099 147026 164938 149836 286307  
FORM FIELD ProblemFormulation ProblemFormulation The formulation...
FORM FIELD ComputationalModel ComputationalModel The computational model...
FORM FIELD Results Results The results...
FORM FIELD Conclusions Conclusions In conclusion...
FORM FIELD ExtraForExperts ExtraForExperts
FORM FIELD StudentTasks StudentTasks
View topic | History: r20 < r19 < r18 < r17 | More topic actions...
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback