Introduction Define x1=number of shirts produced each week x2=number of shorts produced each week x3 number of pants produced each week and for i=1,2,3,define 为={&f交28 mand We can have the following IP model: max6x+4x2+7x3-200y1-150y2-100y3 s.t. 3xM+2X2+6x3≤150 (Labor constraint) 4x1+3x2+4x3 160 (Cloth constraint) xM≤Myh,x2≤M2y2,x3≤My3,(Fixed charge) 灯，2，x3≥0，灯，2,3 integer, y1,y2,3=0or1. 30Q0 Xi Chen (chenxi0109@bfsu.edu.cn) Integer Programming 6/42
Introduction Define x1 = number of shirts produced each week x2 = number of shorts produced each week x3 = number of pants produced each week and for i = 1, 2, 3, define yi = 1, if xi > 0 are manufactured, 0, if xi = 0. We can have the following IP model: max 6x1 + 4x2 + 7x3 − 200y1 − 150y2 − 100y3 s.t. 3x1 + 2x2 + 6x3 ≤ 150 (Labor constraint) 4x1 + 3x2 + 4x3 ≤ 160 (Cloth constraint) x1 ≤ M1y1, x2 ≤ M2y2, x3 ≤ M3y3, (Fixed charge) x1, x2, x3 ≥ 0, x1, x2, x3 integer, y1, y2, y3 = 0 or 1. Xi Chen (chenxi0109@bfsu.edu.cn) Integer Programming 6 / 42
The Branch-and-Bound Method Introduction 2The Branch-and-Bound Method Implicit Enumeration The Cutting Plane Algorithm 4口4+4三4至，至)只0 Xi Chen (chenxi0109@bfsu.edu.cn) Integer Programming 7/42
The Branch-and-Bound Method 1 Introduction 2 The Branch-and-Bound Method 3 Implicit Enumeration 4 The Cutting Plane Algorithm Xi Chen (chenxi0109@bfsu.edu.cn) Integer Programming 7 / 42
The Branch-and-Bound Method If you solve the LP relaxation of a pure IP and obtain a solution in which all variables are integers,then the optimal solution to the LP relaxation is also the optimal solution to the IP. Example 2 The Telfa Corporation manufactures tables and chairs.A table requires 1 hour of labor and 9 square board feet of wood,and a chair requires 1 hour of labor and 5 square board feet of wood.Currently,6 hours of labor and 45 square board feet of wood are available.Each table contributes $8 to profit,and each chair contributes $5 to profit. Formulate and solve an IP to maximize Telfa's profit. max 8为+5x2 s.t. x1+x2 <6 (Labor constraint) 9为+5x2≤45 (Vood constraint),x,x2≥0，x,x2 integer. Xi Chen (chenxi0109@bfsu.edu.cn) Integer Programming 8/42
The Branch-and-Bound Method If you solve the LP relaxation of a pure IP and obtain a solution in which all variables are integers, then the optimal solution to the LP relaxation is also the optimal solution to the IP. Example 2 The Telfa Corporation manufactures tables and chairs. A table requires 1 hour of labor and 9 square board feet of wood, and a chair requires 1 hour of labor and 5 square board feet of wood. Currently, 6 hours of labor and 45 square board feet of wood are available. Each table contributes $8 to profit, and each chair contributes $5 to profit. Formulate and solve an IP to maximize Telfa’s profit. max 8x1 + 5x2 s.t. x1 + x2 ≤ 6 (Labor constraint) 9x1 + 5x2 ≤ 45 (Wood constraint), x1, x2 ≥ 0, x1, x2 integer. Xi Chen (chenxi0109@bfsu.edu.cn) Integer Programming 8 / 42
The Branch-and-Bound Method ABC=feusible region for subproblens 2 ●=P Teasible point IP celaxution's feusible region DEFG-feasible pegion for subprohlem 3 .feasihle peint for original IP 1+5■45 Opiimal LP solution to subprobdem I 与=375 5■2.25 =165 1=1 124 x S3 ￡=41 1=2 Subproblem 3 = Xi Chen (chenxi0109@bfsu.edu.cn) Integer Programming 9/42
The Branch-and-Bound Method Xi Chen (chenxi0109@bfsu.edu.cn) Integer Programming 9 / 42
The Branch-and-Bound Method LAf teusihle region fur xubpredlom 5 No fesible regin fur xubprnhlem 4 Gra i 2 does ace imercet AAC) C-41 H- 4-(地.) t1 124 s女nhhm2 1=2 A fosinte fegiosh for sunprodom 5 三4 A=asinte rog'ke fur山bTn 与= N■Isps鲜im了 马22 1 Subprobicm 4 13 Xi Chen (chenxi0109@bfsu.edu.cn) Integer Programming 10/42
The Branch-and-Bound Method Xi Chen (chenxi0109@bfsu.edu.cn) Integer Programming 10 / 42