Encoding Finite Domain Functions Function has one out of n possible values: a1X1+ 「d,ord LP Encoding: y∈{0,1}i=1,2, axl x,=(2,d) Encoding Constraints Fixed-charge problem: f(x k:+ 0 if x=0 Minimizing costs Minimizing Zf, (x,)+---+ f,(x,) Yes or no decisions: should each of the activities be undertaken? Introduce auxiliary variables I ifx>o O ifx=0 z=∑cx+ky Which can be written as a linear constraint using big m
• Function has one out of n possible values: a1x1+ . . . an xn = [d1 or d2 … or dp] • LP Encoding: yi {0,1} i=1,2,…p ( 6 yi ) =1 a1x1+ . . . an xn= (6L di yi ) Encoding Finite Domain Functions • Fixed – charge problem: fi (xj ) = | kj + cj xj if xj >0 | 0 if xj =0 Minimizing costs: Minimizing z=f1(x1) +---+ fn(xn) Yes or no decisions: should each of the activities be undertaken? Encoding Constraints Introduce auxiliary variables: y1, …, yn = 0,1 y = 1 if x > 0 0 if x = 0 Which can be written as a linear constraint using big M: x <yM ¦ n i i i i i Z c x k y 1
Integer Programming(IP) · What is it? Making decisions with IP Exclusion between choices Exclusion between constraints Solutions through branch and bound P Characteristics Solving Binary IPs Solving mixed ips and Lps Naive approach: rounding a simple way to solve an ip might be to round the non-integer solution to the nearest feasible integer. In practice, try it! In theory this idea makes no sense at all Consider Maximize Z=21x,+11x, Subject to7x1+4x2≤13 x1≥0,x2≥0,x1,x2 Integer Optimal solution x is(13/7, 0)
Integer Programming (IP) • What is it? • Making decisions with IP – Exclusion between choices – Exclusion between constraints • Solutions through Branch and Bound – IP Characteristics – Solving Binary IPs – Solving Mixed IPs and LPs Naïve approach: rounding • A simple way to solve an IP might be to round the non-integer solution to the nearest feasible integer. In practice, try it! • In theory, this idea makes no sense at all. Consider • Optimal solution x* is (13/7,0) 0, 0, , integer Subject to 7 4 13 Maximize 21 11 1 2 1 2 1 2 1 2 x x x x x x Z x x t t d