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