Lecture 7: Using MILP To Solve Decision Problems
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
Introduction of Chemical Reaction Engineering Introduction about Chemical Engineering 0:31:15 0:31:09. Lecture 14 Lecture 15 Lecture 16 Lecture 17 Lecture 18 Lecture 19 Lecture 20 Lecture 21 Lecture 22 Lecture 23 Lecture 24 Lecture 25 Lecture 26 Lecture 27 Lecture 28 Lecture
Hooman Askari-Nasab Mining Optimization Laboratory (MOL) University of Alberta, Edmonton, Canada . Abstract A number of mixed integer linear programming (MILP) formulations have been introduced for production scheduling of open pit mines. One of the main obstacles in using MILP formulations for
Lecture 1: A Beginner's Guide Lecture 2: Introduction to Programming Lecture 3: Introduction to C, structure of C programming Lecture 4: Elements of C Lecture 5: Variables, Statements, Expressions Lecture 6: Input-Output in C Lecture 7: Formatted Input-Output Lecture 8: Operators Lecture 9: Operators continued
Mathematical programming, especially Mixed Integer Linear Programming (MILP), because of its rigorousness, flexibility and extensive modeling capability, has become one of the most widely explored methods for process scheduling problems. Applications of MILP based scheduling methods range from the simplest single-stage Corresponding author.
cal programming approaches are developed in the literature: MILP and NLP. While MILP formulations guarantee a global optimum solution, NLP formulations provide several local minimum solutions. Integer linear programming (ILP) to obtai
Security Act of 2007,6 establishes a target of 36 billion gallons of renewable fuels by . Following the work by Zamboni et al.,20 Dal Mas et al.22 developed a dynamic MILP . and their economic impacts in Alabama, through a MILP-based facility location model that minimizes the total transportation cost and takes into
Lecture 1: Introduction and Orientation. Lecture 2: Overview of Electronic Materials . Lecture 3: Free electron Fermi gas . Lecture 4: Energy bands . Lecture 5: Carrier Concentration in Semiconductors . Lecture 6: Shallow dopants and Deep -level traps . Lecture 7: Silicon Materials . Lecture 8: Oxidation. Lecture
6 Introduction to Linguistic Field Methods :, We have also attempted to address the lack of a comprehensive textbook that p.resents the rudiments of field methodology in all of the major areas of linguistic inquiry. Though a number of books and articles dealing with various aspects offield work already exist esee for example Payne 1951, Longacre 1964, Samarin 1967, Brewster 1982, and other .
