QBUS6820 Prescriptive Analytics: Fr,om Data To Decisio,n Assignment 2
S -m st r 1, 2023 Out: 14tl1 April 2023
Due: 5t:h May 2023 at 11:59pm
This assignment consists of two problems, some involving multiple parts. Son1e parts require a ,vritten
response and others involve coding. The parts that require a written response are described in this
document, while the coding questions (indicated by S) are described in the associated Jupyter otebook
(. ipynb file).
?
You should submit a PDF to GradeScope for the written parts and match the page number with the questions that you answer,ed. You can find detailed instructions on ho?r to use GradeScope on Canvas. If you fail to match the page to the corresponding question, the marker will not be able to view your response and thus you will be awarded O mark for the question.
You should ans,ver the coding questions by n1odifying the Jupyter otebook appropriately, and ubn1it it through Canvas.
Wh,en a problem asks you to formulate a 1nodel, you need to provide your math,ematical formulation ,vith clear justification of decision variables constraints and objective. If you decide to label any of the data v,ith algebraic sy1nbols, you mut clearly define these (e.g.., let aij be the amount of material i required by product j).
All the problems can be done using only the material from this cla , and we will deduct points from solutions that refer to outside 1naterial.
Written parts must be typed. This means no handwriting and no screen shots are permitted, except for illu trative graphics to supplement ansV\rers. If you are using !licrosoft Word, use the equation editor for mathematical equations/formulas. We recommend using Tu\-TEX or a similar systern for typesetting your ans,ver.
You mu t fill and sign the academic honesty declaration on the next page and . ubmit it through GradeScope.
Question:
Academic integrity declaration
Collaboration policy. You are only allowed to verbally discuss high-level ideas ,vith classn1ates. All detailed model vvorkings and coding should be done individually. You may consult any resources you like on how to use Python and Gurobi (e.g., syntax). However, for the conceptual model building parts you are not permitted to consult resources (e.g., internet forums, websites) except for provided lecture and tutorial content.
Academic honesty declaration. I declare that the submitted vvork is my solely my own, except for high-level ideas that I have discussed vvith the following people:
I declare that I have not consulted any 1naterial besides lecture and tutorial content provided through Canvas.
I understand t hat my work may be submitted to similarity detection soft,vare and a copy of the ,vork may be retained for future similarity checking.
QBUS6820 Assignment 2 Due 5th 1!lay 2023
1. ?Then constructing new roads, a common operational problem that needs to be solved is ho,￥ to terraform the ground profile so that it matches the desired road profile. More concretely (no pun intended), if the ground is bumpy, vve wish to smooth it out by digging dirt in certain places and moving it to fill other places.
This phase is critical for building high quality roads. It often contributes about 25% of construction costs, but can be much higher for difficult roads.
For the segn1ent of road that we consider, ,￥e vvill discretize it into n chunks which we will dig or fill. The data ,￥e are given is the following:
A beginning ground profile p Pn > 0, where each Pi denotes a1nount of dirt present in chunk i.
A target ground profile q > 0 where each denotes the desired amount of dirt in chunk
The cost of transporting a unit of dirt from chunk i to chunk j is Cij > 0.
(a) (5 points) Assume that Pi = Formulate the terraforming problem as a net,￥ork flo,￥ model.
Hint: You can describe your network in t,￥0 ,￥ays, vvith n, nodes or 2n, nodes. Both can be correct. If you use n nodes, your model should have n(n, - 1) arcs. If you use 2n nodes, your model should have n2 arcs.
(b) (5 points) Describe how to modify the model above if the assumption that does not hold.
Pi =
(c) (3 points) Suppose you have a feasible transportation plan that sends a units of dirt from i to j, and sends b units of dirt fro1n j to i. Explain vvhy this is never optimal, and propose a plan
that has a better objective, but the same inflovv/outflo,￥ for each node.
Hint: You should suggest an alternative plan for each of the tvvo possible cases: (i) ,￥hen a > b; and (ii) when a < b.
For parts (d) to (j), we will assun1e that the costs are Cij = cli -jl, and Pi =
(d) (5 points) Assume that the chunks of the road are indexed in order, i.e., chunks 1 and n are left and right endpoints of the road segn1ent, and chunks i and i + 1 are actually physically next to each other (vvith i on the left, i + 1 on the right).
Assume further that the cost of transporting a chunk of dirt from i to j is directly proportional to the physical distance between i and j. This means that
move units
move units
Propose an alternative transportation plan with better objective, but the same inflow/outflow for each node.
Hint: You should suggest an alternative solution for each of the two possible cases: (i) when a > b; and (ii) vvhen a < b.
(e) (3 points) Suppose a transportation plan has the follovving structure:
Cij =cli-JI
Suppose that a, > 0 are two given numbers. Describe why a transportation plan with the
for some c > 0.
following structure cannot be optimal:
Due: 5th lVIay 2023 Page 1 of 3.
QBUS6820 Assignment 2 Due 5th day .2023 move b units
Assuming again that Cij :;;;:: cli -ii for some c > 0, describe ho-,v to adju t thi plan so that it ha.s the same cost, the same inflo,?.r/outflow at each node, but no 'hops" over nodes.
(f) (5 points) Using the insight from parts (d) and (e), propose an alternative model with 2(n -1) variables.
(g) (4 points) When ,ve use optimization models in practice, we have to think how they can be implemented. In the context of terraforrning, thi mean that given an output tran portation plan, 1Are need to figure out ho,v ,ve would actually proceed to dig/fill the various chu11ks. Describe some implementation considerations that the models in parts (a) and (fj do not account
for. (This answer should be short, about 1 to 5 sentences long.)
(h) (5 points) Ir1 addition to transportation costs Cij = cli - jl, there are costs in loading and unloading dirt to be transported. For each unit of dirt to be loaded, ,ve pay ft cost. For each unit of dirt unloaded, "'re pay fu cost. Forn1ulate a model that can account for these costs.
Hint: Here is one ,vay to do it. Have three sets of n nodes: (i, 0), (i L) and ('i, R) for each i E [n]. The nodes (i, L) vvill transport dirt to the left, ,;vhile (i, R) nodes tran port dirt to the right. Specify arcs as appropriate, but pay attention to the, ir directions! You should have fin -2 arcs in total.
(i) (5 points) In practice, there are different types of loading/unloading as well as transportation costs. For large quantities of dirt to be transferred longer distances, companies may ,vish to use larger truck . These typically have cheaper transportation costs, but higher loading/unloading co ts. For ,maller qua.ntitie - of dirt over shorter di ta.nc€s, a bulldozer may suffice. The e hav low loading/unloading costs, but transportation is not as efficient.
For1nulate a model that ca.n capture two types of trai1sportation 1node decisions:
type A with tranL portation costs cj == cA Ii - j I and loading/unloading ff, f; . ? type B with transportation co t c? :::::: cB Ii - j I and loading/unloading ff, J!!.
Hint: You will no"\\r need five sets of n nodes, and 12n - 4 arcs.
(j) (15 points) Sr Please refer to the Jupyter Notebook for this question. ?
QBUS6820 Assignment 2 Due 5th day .2023
2. Public tran 'port -ystems routinely employ optimization techniques. In this question, you Vlill use data gathered from the Sydney train net,vork to formulate models for critical decision-making prob- lems, and implen1ent them in Python. \Ve fir t begin with t"\\ro questio11s on general networks.
(a) (5 points) Let G :::: (N, A) be a network, and let s, t E N be two nodes. A directed walk from s to t is a sequence of arcs (s, n1),, (n1 ,, n2),.... , (nk-1, nk), (nk, t) E A. (Sequentially walking along these arc - ,vill lead you from s to t.) Forrnulate a model to te t ?rhether there exi ts a directed ,valk from s to t or not.
(b) ( 5 points) Let G == ( N,, A) be a netvvork, and let s E J\T be the source node. Suppose that t tm E J\T ate a set of sink nodes. Formulate a single 111odel to sirnultaneously test "'rhether there exists a directed walk from s to each of t1, ..., tm.
Hint? This can be done a.. a maxin1um flow problem. You ,vill need to augment your netv?rork with extra nodes and edge .
Suppose you have the follo,ving data on train segments in Sydney: (ri, di_, Si, ai) for i E [N], where
ri is the station that a train departs from.
di is the departure time of tl1at train fro1n ri.
Si is the station that a train arrive· at (the train does not stop between ri and Si) ? a.i is the arrival time of the train at Si ..
(c) (5 points) Given the train data above, the question you want to anL\Ver is:
Suppose a passenger starts at station .Sstart t time tstart. How quickly can the pas- senger get to a destination station Sena, and vvhat is the optimal route?
Describe how you would use the data to formulate a n'lodel that answers this question.
Hint: You should formulate this as a particular netvvork flow problen1 by describing hovv to construct the nodes, arcs, capacitie · and costs. Your nodes "rill need to be indexed by t,vo things: the station s and the time t.
(d) (5 point ) Given the train data above the question you "\\!?ant to ans"rer is:
Suppose a passenger starts at station 8start at time tstart. ,i\Thich stations can the pas enger reach by time tend > tstart, using only the train net,vork?
Describe ho"\\r you would use the data to formulate a model that ans"\\rers this question.
(e) ( 15 points) ;S, Please refer to the Jupyter Notebook for this q'l.testion. ?
Due: 5th JVIay 2023