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