2y ago

47 Views

2 Downloads

734.71 KB

20 Pages

Transcription

Lecture 7: Using MILP to solve decision problems Decision problemsAbsolute valuesTransformation of a logical “or” into a logical “and”A formal definition of MILPExample: holding patternsPosing the number of holding patterns as a MILPA real example from Air Traffic ControlGraphical interpretation of decision problemsSome variables are on a grid, some are not:Order of arrival of aircraft 2t2Order of arrival of aircraft 1The solution for these twovariables has to be on the grid.t1It does not matter where thesolution for these two variables is1

Discrete order of arrival: deciding the orderFirst kind of decision variables: order of arrivalaircraft 3 minaircraft 3 minORt2t1t1timet2timeAnother way to express this:Now, every time you see an absolute valueAbsolute value: not linear, not affine difficultAbsolute value can be expressed as a logical disjunction(this is just a fancy way to say « or »).OR2

« and » is easy, « or » is difficultReminder: you have already used « and » many timesAll these arelogical “and”Tranformation of an « or » into an « and »Let us pick a very large numberLet us pick a decision variableThe two following statements are equivalent:orand3

Logical explanationTwo cases to investigate:Case 1: d 0becomesbecomesi.e.This is always true (just take M large enough).Therefore, the second condition can be discarded.Logical explanationTwo cases to investigate:Case 1: d 0becomesbecomesi.e.This is always true (just take M large enough).Therefore, the second condition can be discarded.4

Logical explanationTwo cases to investigate:Case 1: d 0becomesbecomesi.e.This is always true (just take M large enough).Therefore, the second condition can be discarded.Logical explanationTwo cases to investigate:Case 1: d 0becomesbecomesi.e.This is always true (just take M large enough).Therefore, the second condition can be discarded.5

Logical explanationTwo cases to investigate:Case 1: d 0becomesCase 2: d 1becomesbecomesThis is always true (just take M large enough).Therefore, the second condition can be discarded.Logical explanationTwo cases to investigate:Case 1: d 0becomesCase 2: d 1becomesbecomesi.e.This is always true (just take M large enough).Therefore, the second condition can be discarded.6

Logical explanationTwo cases to investigate:Case 1: d 0becomesCase 2: d 1becomesbecomesi.e.This is always true (just take M large enough).Therefore, the second condition can be discarded.SummaryTwo cases to investigate:Case 1: d 0becomesCase 2: d 1becomes7

SummaryDepending on the value of d:Case 1: d 0Case 2: d 1In other wordsorTranformation of an « or » into an « and »Let us pick a very large numberLet us pick a decision variableThe two following statements are equivalent:andor8

Tranformation of an « or » into an « and »orandaircraft 3 minaircraft 3 minORt2t1timet1t2timeWhy is it useful?Now you can pose the problem of earliest arrival time ofthe last aircraft with decision enabled for order ofarrival: you can deal with continuous and discretevariables.t1 if d 1, t2 if d 09

Why is it useful?Now you can pose the problem of earliest arrival time ofthe last aircraft with decision enabled for order ofarrival: you can deal with continuous and discretevariables.Aircraft 1 and 2 are separatedby more than (previous slides)Why is it useful?Now you can pose the problem of earliest arrival time ofthe last aircraft with decision enabled for order ofarrival: you can deal with continuous and discretevariables.Aircraft 1 arrives between a1 and b1Aircraft 2 arrives between a2 and b210

A formal definition of a MILPA Mixed Integer Linear Program is a Linear Program inwhich some of the variables are continuous, and someare integer.Holding patterns: how many should an aircraft fly?A holding pattern delays an aircraft by a fixed amountof time, usually T 3 min.Question for ATC:how many holding patternsshould one aircraft do beforeit is allowed to land?CTAS tracks courtesy of NASA Ames11

A holding pattern is a shift by TaircraftTa4 b4a2b2a3 b3aircraft 4aircraft 3aircraft 2aircraft 1a1b1feasible arrival timesA holding pattern is a shift by TaircraftTa4 b4a2b2a3 b3aircraft 4aircraft 3aircraft 2aircraft 1a1b1feasible arrival times12

A holding pattern is a shift by TaircraftTOne holdingpatternTwo holdingpatternsThree holdingpatternsTTTaircraft 4a4 b4a2b2aircraft 3a3 b3aircraft 2aircraft 1a1b1feasible arrival timesA holding pattern is a shift by TOne holdingpatternaircraftTTwo holdingpatternsTTa4 b4a2b2a3 b3Three holdingpatternsTaircraft 4aircraft 3aircraft 2aircraft 1a1b1feasible arrival times13

A holding pattern is a shift by TOne holdingpatternaircraftTwo holdingpatternsTThree holdingpatternsTTaircraft 4a4 b4a2b2aircraft 3a3 b3aircraft 2aircraft 1a1b1feasible arrival timesA holding pattern is a shift by TOne holdingpatternTwo holdingpatternsTTaircrafta4 b4a2b2a3 b3aircraft 4aircraft 3aircraft 2aircraft 1a1b1feasible arrival times14

A holding pattern is a shift by TThis is the set in which we want to scheduleaircraft. We seek one arrival time for eachaircraft in each of the colored sets.aircraftaircraft 4a4 b4a2b2aircraft 3a3 b3aircraft 2aircraft 1a1b1feasible arrival timesA holding pattern can be expressed as a MILPThe number of holding patterns is a decision variable (thedecision is actually made by the human Air Traffic Controller).aircraftTTTa4 b4a2a1b2a3 b3aircraft 4aircraft 3aircraft 2aircraft 1b1feasible arrival times15

A holding pattern can be expressed as a MILPThe number of holding patterns is a decision variable (thedecision is actually made by the human Air Traffic aircraft 4a4 b4a2b2aircraft 3a3 b3aircraft 2aircraft 1a1b1feasible arrival timesA holding pattern can be expressed as a MILPActually, the human air traffic controller has the possibility toschedule aircraft 2 anywhere in the fourth time interval (i.e.with three holding patterns).aircraftTTTa4 b4a2a1b2a3 b3aircraft 4aircraft 3aircraft 2aircraft 1b1feasible arrival times16

A holding pattern can be expressed as a MILPThis is can be expressed in terms of two linear constraintsinvolving integer and continuous variablesaircraftTTTaircraft 4a4 b4a2b2aircraft 3a3 b3aircraft 2aircraft 1a1b1feasible arrival timesA holding pattern can be expressed as a MILPThis is can be expressed in terms of two linear constraintsinvolving integer and continuous variables, more generally,for any admissible interval for aircraft 2:For n holdingpatternsaircraftTTTa4 b4a2a1b2a3 b3aircraft 4aircraft 3aircraft 2aircraft 1b1feasible arrival times17

An real example from transportation (air traffic control)Problem: separating aircraft by 3 min: how to schedule theaircraft so the last aircraft comes as early as possible.aircraft 3 minaircraft 4aircraft 3aircraft 2aircraft 1feasible arrival timesAn real example from transportation (air traffic control)Problem: separating aircraft by 3 min: how to schedule theaircraft so the last aircraft comes as early as possible.aircraft 3 minaircraft 4aircraft 3aircraft 2aircraft 1t2feasible arrival times18

An real example from transportation (air traffic control)Problem: separating aircraft by 3 min: how to schedule theaircraft so the last aircraft comes as early as possible. 3 minaircraft 3 minaircraft 4aircraft 3aircraft 2aircraft 1t2t1feasible arrival timesAn real example from transportation (air traffic control)Problem: separating aircraft by 3 min: how to schedule theaircraft so the last aircraft comes as early as possible. 3 min 3 minaircraft 3 minaircraft 4aircraft 3aircraft 2aircraft 1t2t1t3feasible arrival times19

An real example from transportation (air traffic control)Problem: separating aircraft by 3 min: how to schedule theaircraft so the last aircraft comes as early as possible. 3 min 3 min at least 3 minaircraft 3 minaircraft 4aircraft 3aircraft 2aircraft 1t2t1t3t4feasible arrival timesAn real example from transportation (air traffic control)This is a Mixed Integer Linear Program (MILP):- Some variables are integer (the order of arrival): 3, 1, 2, 4 - Some variables are continuous (the times of arrival)- The problem can be posed as a linear program involvingboth integer and continuous variables. 3 min at least 3 minaircraft 3 minaircraft 4aircraft 3aircraft 2aircraft 1t2t1t3t4feasible arrival times20

A holding pattern is a shift by T This is the set in which we want to schedule aircraft. We seek one arrival time for each aircraft in each of the colored sets. aircraft 1 aircraft 2 aircraft 3 feasible arrival times aircraft aircraft 4 a1 b1 a2 b2 a3 b3 a4 b4 A holding pattern can be expressed as a MILP

Related Documents: