北京外国语大学：《运筹学 Operations Research》课程教学资源（课件讲稿）整数规划 Integer Programming

Integer Programming Xi Chen Department of Management Science and Engineering International Business School Beijing Foreign Studies University 4口48+4三4至，至)只0 Xi Chen (chenxi0109@bfsu.edu.cn) Integer Programming 1/42

Integer Programming Xi Chen Department of Management Science and Engineering International Business School Beijing Foreign Studies University Xi Chen (chenxi0109@bfsu.edu.cn) Integer Programming 1 / 42

Introduction Introduction The Branch-and-Bound Method Implicit Enumeration The Cutting Plane Algorithm 4口，4得+4艺至，三风0 Xi Chen (chenxi0109@bfsu.edu.cn) Integer Programming 2/42

Introduction 1 Introduction 2 The Branch-and-Bound Method 3 Implicit Enumeration 4 The Cutting Plane Algorithm Xi Chen (chenxi0109@bfsu.edu.cn) Integer Programming 2 / 42

Introduction Definition 1.1 An integer programming problem (IP)is an LP in which some or all of the variables are required to be non-negative integers,i.e.,the Divisibility Assumption in LP does not hold. A pure integer programming problem max3x为+2x2 s.t.x1+9≤6灯，x2≥0，灯，2 integer. A mixed integer programming problem max3x灯+2x2 s.t.+x2≤6，为，x2≥0，x1 integer.. A 0-1 integer programming problem max X1 -X2 s.t. x1+2x2≤2,2x灯-2≤1 ,X9=0or1. Xi Chen (chenxi0109@bfsu.edu.cn) Integer Programming 3/42

Introduction Definition 1.1 An integer programming problem (IP) is an LP in which some or all of the variables are required to be non-negative integers, i.e., the Divisibility Assumption in LP does not hold. A pure integer programming problem max 3x1 + 2x2 s.t. x1 + x2 ≤ 6 x1, x2 ≥ 0, x1, x2 integer. A mixed integer programming problem max 3x1 + 2x2 s.t. x1 + x2 ≤ 6, x1, x2 ≥ 0, x1 integer. A 0-1 integer programming problem max x1 − x2 s.t. x1 + 2x2 ≤ 2, 2x1 − x2 ≤ 1, x1, x2 = 0 or 1. Xi Chen (chenxi0109@bfsu.edu.cn) Integer Programming 3 / 42

Introduction Definition 1.2 The LP obtained by omitting all integer or 0-1 constraints on variables is called the LP relaxation of the IP. The feasible region for any IP must be contained in the feasible region for the corresponding LP relaxation.For any IP that is a max problem,this implies that Optimal z-value for LP relaxation optimal z-value for IP. Consider max21x为+119 33 s.t.7x+4x2≤13， 灯，x2≥0，灯，2 integer. 7+413 An IP is very difficult to solve because 1 o Enumeration may be impossible. Roundoff may be wrong or infeasible. 05 1D15.20253D )Q0 Xi Chen (chenxi0109@bfsu.edu.cn) Integer Programming 4/42

Introduction Definition 1.2 The LP obtained by omitting all integer or 0 − 1 constraints on variables is called the LP relaxation of the IP. The feasible region for any IP must be contained in the feasible region for the corresponding LP relaxation. For any IP that is a max problem, this implies that Optimal z-value for LP relaxation ≥ optimal z-value for IP. Consider max 21x1 + 11x2 s.t. 7x1 + 4x2 ≤ 13, x1, x2 ≥ 0, x1, x2 integer. An IP is very difficult to solve because Enumeration may be impossible. Roundoff may be wrong or infeasible. Xi Chen (chenxi0109@bfsu.edu.cn) Integer Programming 4 / 42

Introduction Example 1 Gandhi Cloth Company is capable of manufacturing three types of clothing:shirts,shorts,and pants.The manufacture of each type of clothing requires that Gandhi have the appropriate type of machinery available.The machinery needed to manufacture each type of clothing must be rented at the following rates:shirt machinery,$200 per week; shorts machinery,$150 per week;pants machinery,$100 per week.The manufacture of each type of clothing also requires the amounts of cloth and labor shown in the left table.Each week,150 hours of labor and 160 sq yd of cloth are available.The variable unit cost and selling price for each type of clothing are shown in the right table. Formulate an IP whose solution will maximize Gandhi's weekly profits. Resource Reguirements lor Gandhi Reveue ad Costtrmatioor Gandhi Clothing Labor Cloth Clothing Salea Variable Hours】 (Square Yards) Type Price (S] Co时(S) Shirt 4 Shirt 12 6 Shorts 2 Shorts Pants 6 Pants 15 )Q0 Xi Chen (chenxi0109@bfsu.edu.cn) Integer Programming 5/42

Introduction Example 1 Gandhi Cloth Company is capable of manufacturing three types of clothing: shirts, shorts, and pants. The manufacture of each type of clothing requires that Gandhi have the appropriate type of machinery available. The machinery needed to manufacture each type of clothing must be rented at the following rates: shirt machinery, $200 per week; shorts machinery, $150 per week; pants machinery, $100 per week. The manufacture of each type of clothing also requires the amounts of cloth and labor shown in the left table. Each week, 150 hours of labor and 160 sq yd of cloth are available. The variable unit cost and selling price for each type of clothing are shown in the right table. Formulate an IP whose solution will maximize Gandhi’s weekly profits. Xi Chen (chenxi0109@bfsu.edu.cn) Integer Programming 5 / 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 为={&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