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/42The 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