Courtesy of Sommer Gentry. Used with permission Integer Programming and Branch and Bound Sommer Gentry November 24th. 2003 Adapted from slides by Eric Feron and Brian Williams, 16.410, 2002. Integer Programming(IP) · What is it? Expressing decisions with IP Exclusion between choices Exclusion between constraints Solutions through branch and bound Characteristics Solving Binary IPs Solving mixed IPs and LPs
Integer Programming and Branch and Bound Sommer Gentry November 24th, 2003 Adapted from slides by Eric Feron and Brian Williams, 16.410, 2002. Integer Programming (IP) • What is it? • Expressing decisions with IP – Exclusion between choices – Exclusion between constraints • Solutions through branch and bound – Characteristics – Solving Binary IPs – Solving Mixed IPs and LPs Courtesy of Sommer Gentry. Used with permission
Integer Programs LP: Maximize 3x1+ 4x2 IP: Maximize 3x1+ 4x2 Subiect to: Subject te X1≤4 X1≤4 2x,≤12 2x2≤12 3x1+2x2≤18 3x1+2x2≤18 x1,X2≥0 X1,x2≥0 Xx integers Integer Programming Integer programs are LPs where some variables are integers Why Integer programming? 1. Some variables are not real-valued Boeing only sells complete planes, not fractions 2. Fractional LP solutions poorly approximate integer solutions For Boeing aircraft Co, producing 4 versus 4.5 airplanes results in radically different profits Often a mix is desired of integer and non-integer variables( MILP
Integer Programs LP: Maximize 3x1 + 4x2 Subject to: x1 4 2x2 12 3x1 + 2x2 18 x1 , x2 0 IP: Maximize 3x1 + 4x2 Subject to: x1 4 2x2 12 3x1 + 2x2 18 x1 , x2 0 x1 , x2 integers a) b) c) d) e) x1 x2 Integer programs are LPs where some variables are integers Why Integer programming? 1. Some variables are not real-valued: • Boeing only sells complete planes, not fractions. 2. Fractional LP solutions poorly approximate integer solutions: • For Boeing Aircraft Co., producing 4 versus 4.5 airplanes results in radically different profits. Often a mix is desired of integer and non-integer variables (MILP). Integer Programming
Graphical representation of Ip Integer Programming(IP) · What is it? Making decisions with IP Exclusion between choices Exclusion between constraints Solutions through branch and bound Characteristics Solving Binary IPs Solving mixed IPs and LPs
Graphical representation of IP Integer Programming (IP) • What is it? • Making decisions with IP – Exclusion between choices – Exclusion between constraints • Solutions through branch and bound – Characteristics – Solving Binary IPs – Solving Mixed IPs and LPs
Integer Programming for Decision Making Yes or no"decisions encoded with binary variables 1 if decision is yes 0 if decision is no Binary Integer Programming( BIP: Binary variables linear constraints Binary Integer Programming Example Cal aircraft Manufacturing company Problem Cal wants to expand Build new factory in Los Angeles, San Francisco, or both Build new warehouse(only one) Warehouse must be built close to city of a new factory 2. Available capital: S10,000,000 3. Cal wants to maximize"total net present value"(profitability vs time value of money) Pri 1 Build a factory in L. A? Sir Sam 2 Build a factory in S F? Sam 3 Build a warehouse in L.A.? S61 Sam 4 Build a warehouse in S F? S41 S2m
“Yes or no” decisions encoded with binary variables: 1 if decision is yes xj 0 if decision is no. Binary Integer Programming (BIP): • Binary variables + linear constraints. Integer Programming for Decision Making Problem: 1. Cal wants to expand: • Build new factory in Los Angeles, San Francisco, or both. • Build new warehouse (only one). • Warehouse must be built close to city of a new factory. 2. Available capital: $10,000,000 3. Cal wants to maximize “total net present value” (profitability vs. time value of money) NPV Price 1 Build a factory in L.A.? $9m $6m 2 Build a factory in S.F.? $5m $3m 3 Build a warehouse in L.A.? $6m $5m 4 Build a warehouse in S.F.? $4m $2m Binary Integer Programming Example: Cal Aircraft Manufacturing Company
Binary Integer Programming Example Cal aircraft Manufacturing company What decisions are to be made? 1. Build fac 2. Build factory in SFO 3. Build warehouse in La 4. Build warehouse in SFo I if decision i is yes Introduce 4 binary variables if decision i is no Binary Integer Programming Example Cal aircraft Manufacturing Company 1. Cal wants to expand (TBD) 2. Available capital: $10,000,000 3. Cal wants to maximize"total net present value"(profitability vs time value of money) Build a factory in L.A.? Sam 2 Build a factory in S.F.? 3 Build a warehouse in L.A.? Sam Sam 4 Build a warehouse in S F? S2m What is the objective? Maximize npv. z=9X1+5x+6x3+4 Remaining constraints? Dont go beyond means
What decisions are to be made? 1. Build factory in LA 2. Build factory in SFO 3. Build warehouse in LA 4. Build warehouse in SFO 1 if decision i is yes Introduce 4 binary variables xi = 0 if decision i is no Binary Integer Programming Example: Cal Aircraft Manufacturing Company 1. Cal wants to expand (TBD) 2. Available capital: $10,000,000 3. Cal wants to maximize “total net present value” (profitability vs. time value of money) NPV Price 1 Build a factory in L.A.? $9m $6m 2 Build a factory in S.F.? $5m $3m 3 Build a warehouse in L.A.? $6m $5m 4 Build a warehouse in S.F.? $4m $2m What is the objective? • Maximize NPV: Z = 9x1 + 5x2 + 6x3 + 4x4 Remaining constraints? • Don’t go beyond means: 6x1 + 3x2 + 5x3 + 2x4 <10 Binary Integer Programming Example: Cal Aircraft Manufacturing Company
Binary Integer Programming Example Cal aircraft Manufacturing company LA factory(x ), SFO factory(x2), LA warehouse(x,), SFO warehouse (x4) Build new factory in Los Angeles, San Francisco, or both Build new warehouse(only one Warehouse must be built close to city of a new factory What are the constraints between decisions? Only one warehouse x exclusive-orx 2. Warehouse in LA only if Factory is in LA 3. Warehouse in Sfo only if factory is in SFO Implies x Encoding Choices: An Example Mutually exclusive choices Example: at most 2 decisions in a group can be yes LP Encoding
LA factory(x1), SFO factory(x2), LA warehouse(x3),SFO warehouse (x4) • Build new factory in Los Angeles, San Francisco, or both. • Build new warehouse (only one). • Warehouse must be built close to city of a new factory. What are the constraints between decisions? 1. Only one warehouse: x3 exclusive-or x3 x3 + x4 < 1 2. Warehouse in LA only if Factory is in LA: x3 implies x1 x3 – x1 < 0 3. Warehouse in SFO only if Factory is in SFO: x4 implies x2 x4 - x2 < 0 Binary Integer Programming Example: Cal Aircraft Manufacturing Company • Mutually exclusive choices • Example: at most 2 decisions in a group can be yes: LP Encoding: x1 +…+ xk < 2. Encoding Choices: An Example
Binary Integer Programming Example Cal aircraft Manufacturing company LA factory(xl), SFO factory(x2), LA warehouse (x3), SFO warehouse Build new factory in Los angeles, San francisco, or both Build new warehouse(only one) Warehouse must be built close to city of a new factory What are the constraints between decisions? Only one warehouse x, exclusive-orx +x4<1 2. Warehouse in La only if Factory is in LA x implies x1<0 3. warehouse in Sfo only if factory is in SFO <0 Binary Integer Programming Example Cal aircraft Manufacturing company Complete binary integer program: Maximize z=9x, 5x +6x +4x Subject to: 6x,+ 3x2+5x3+ 2x4 <10 <0 X4-x2≤0 X={0,1},j=1,2,3,4
LA factory(x1), SFO factory(x2), LA warehouse(x3),SFO warehouse (x4) • Build new factory in Los Angeles, San Francisco, or both. • Build new warehouse (only one). • Warehouse must be built close to city of a new factory. What are the constraints between decisions? 1. Only one warehouse: x3 exclusive-or x4 x3 + x4 0 Binary Integer Programming Example: Cal Aircraft Manufacturing Company
Integer Programming(IP) · What is it? Making decisions with IP Exclusion between choices Exclusion between constraints Solutions through branch and bound Characteristics Solving Binary IPs Solving mixed ips and Lps Cooperative Path Planning MILP Encoding: Constraints Min JT Receding horizon Fuel Cost Fn Si< Wijs etc State Space Constraints S+I=As. Bu State Evolution equation Obstacle a voidance Collision avoidance
Integer Programming (IP) • What is it? • Making decisions with IP – Exclusion between choices – Exclusion between constraints • Solutions through branch and bound – Characteristics – Solving Binary IPs – Solving Mixed IPs and LPs Cooperative Path Planning MILP Encoding: Constraints • Min JT Receding Horizon Fuel Cost Fn • sij wij, etc. State Space Constraints • si +1 = Asi + Bui State Evolution Equation • xi xmin + Myi1 -xi -xmax + Myi2 yi ymin + Myi3 Obstacle Avoidance -yi -ymax + Myi4 6 yik 3 • Similar constraints for Collision Avoidance (for all pairs of vehicles)
Obstacles How do we encode? Each obstacle-vehicle pair represents a disjunctive constraint Red vehicle is above obstacle or Red vehicle is below obstacle or Red vehicle is left of obstacle or Red Vehicle is right of obstacle Each disjunct is an inequality if xR, yR are co-ordinates of red vehicle, inequalities above might be xR4, etc. Constraints are not limited to rectangular obstacles or obstacles oriented a particular way equalities might include both co-ordinates Encoding exclusion Constraints Mutually exclusive constraints E Xa Either [3x1+2x2 <18(x, x, real)] [x+4x≤16] · LP Encodin Use big m to turn-off constraint: Either 3x1+2x,<18 aI 4x,<16+ M(and M is very BIG) 3x,+2x<18+M 1+6X2≤16 Use binary y to decide which constraint to turn off: 3x1+2x2≤18+yM 1+2x2≤16+(1-y)M y∈{0,1}
Obstacles How do we encode? • Each obstacle-vehicle pair represents a disjunctive constraint: • Each disjunct is an inequality – if xR, yR are co-ordinates of red vehicle, inequalities above might be: – xR 4, etc. • Constraints are not limited to rectangular obstacles or obstacles oriented a particular way – (inequalities might include both co-ordinates) Red Vehicle is above obstacle OR Red Vehicle is below obstacle OR Red Vehicle is left of obstacle OR Red Vehicle is right of obstacle • Mutually exclusive constraints • Example: Either [ 3x1 + 2x2 < 18 (x1 ,x2 real) ] Or [ x + 4x < 16]. • LP Encoding: • Use Big M to turn-off constraint: Either: 3x1 + 2x2 < 18 and x1 + 4x2 < 16 + M (and M is very BIG) Or: 3x1 + 2x2 < 18 + M and x1 + 6x2 < 16 Encoding Exclusion Constraints • Use binary y to decide which constraint to turn off: 3x1 + 2x2 < 18 + y M x1 + 2x2 < 16 + (1-y)M y {0,1}
Cooperative Path Planning MILP Encoding: Constraints Min JT Receding Horizon Fuel Cost Fn S;≤Wj,etc State Space Constraints S: +I= As+ Bu State Evolution equation X1≤Xmin+My1 my yi< ymin Myi3 Obstacle Avoidance <-ymax My 14 Σyk≤3 At least one enabled Similar constraints for Collision avoidance (for all pairs of vehicles) Encoding Exclusion Constraints Kout ofn constraints hold. At most k ofn hold: f1(x1,x2,…xn)≤d1OR f(x1,x2,…,xn)≤dN where f, are linear expressions LP Encoding Introduce y; to deselect each constraint Constrain K of y; to select constraints ∑y1=N-K ∑y≤N-K Use Big M to turn- off constraint f(x1,--,xn)≤d1+My1 f(x1,--,xn)≤dx+MyN
Cooperative Path Planning MILP Encoding: Constraints • Min JT Receding Horizon Fuel Cost Fn • sij wij, etc. State Space Constraints • si +1 = Asi + Bui State Evolution Equation • xi xmin + Myi1 -xi -xmax + Myi2 yi ymin + Myi3 Obstacle Avoidance -yi -ymax + Myi4 6 yik 3 At least one enabled • Similar constraints for Collision Avoidance (for all pairs of vehicles) • K out of N constraints hold: f1(x1, x2 ,…xn) < d1 OR : fN(x1, x2 , …, xn ) < dN where fi are linear expressions • LP Encoding: • Introduce yi to deselect each constraint: • Constrain K of yi to select constraints: • Use Big M to turn-off constraint: f1(x1, ---, xn ) < d1 + My1 : fN(x1, ---, xn ) < dN + MyN Encoding Exclusion Constraints ¦ d N i yi N K 1 • At most K of N hold: ¦ N i yi N K 1