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 < 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 Complete binary integer program: Maximize Z = 9x1 + 5x2 + 6x3 + 4x4 Subject to: 6x1 + 3x2 + 5x3 + 2x4 <10 x3 + x4 < 1 x3 - x1 < 0 x4 - x2 < 0 xj < 1 xj = {0,1}, j=1,2,3,4 xj > 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 xR<3 yR>4, 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 < 3 – yR > 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