ࡱ> GIBCH( D/ 0|DTimes New RomanȷȷԳ0 0DTahomaew RomanȷȷԳ0 0" DWingdingsRomanȷȷԳ0 00DSymbolgsRomanȷȷԳ0 0@DCourier NewmanȷȷԳ0 01 "   @n?" dd@  @@`` 0(XUjH#$%&'#*+,-./0:12l3745(6789$#$=>AB<CDEF%/ -,2     0!"?@G <0e0e     A@ A5% 8c8c     ?1 d0u0@Ty2 NP'p<'p@A)BCD|E?0 33@338LMUg4adad 0ppp@  <4BdBdȷȷ<4!d!dȷȷ:2___PPT9/ 0? %)#8Introduction to Integer Programming Modeling and MethodsHMichael Trick Carnegie Mellon University CPAI-OR School, Le Croisic 2002*$ Some HistoryInteger Programming goes back a long way: Schrijver takes it back to ancient times (linear diophantine equations), Euler (1748), Monge (1784) and much more.  Proper study began in the 1950s Dantzig (1951): linear programming Gomery (1958): cutting planes Land and Doig (1960): branch and bound Survey books practically every five years since Tremendous practical success in last 10-15 yearsV*ha*ha+%ScopeThis talk will not be comprehensive! Attempt to get across main concepts of integer programming Relaxations Primal Heuristics Branch and Bound Cutting Planes&`>`>,&Integer Program (IP)GMinimize cx Subject to Ax=b l<=x<=u some or all of xj integral&H= /,Rules of the GameMust put in that form! Seems limiting, but 50 years of experience gives  tricks of the trade Many formulations for same problem63Example FormulationsWarehouse location: n stores, m possible warehouses; cost k[j] to open warehouse m; cost c[i,j] to handle store i out of warehouse j. Minimize the total opening costs plus handling costs Subject to Each store assigned to one open warehouse:4Warehouse FormulationVariables x[i,j] = 1 if store i served by warehouse j; 0 otherwise y[j] = 1 if warehouse j open; 0 otherwise Objective Minimize sum_j k[j]y[j]+sum_i,j c[i,j]x[i,j]|-;5Warehouse FormulationIConstraints: sum_j x[i,j] = 1 for all i sum_i x[i,j] <= ny[j] for all j =J<6Binary Integer ProgramsRestrict variables to be 0-1 Many specialized methods OR people are real good at formulating difficult problems within these restrictions$DB.( Key conceptsRelaxation R(IP)  easily solved problem such that Optimal solution value is no more than that of IP If solution is feasible for IP then is optimal for IP If R(IP) infeasible then so is IP Most common is  linear relaxation : drop integrality requirements and solve linear program Others possible: lagrangian relaxation, lagrangian decomposition, bounds relaxation, etc.l#\Z#\Z  -' Illustration0)Linear RelaxationA;(Why this fetish with Linear Relaxations?IP people are very focused on linear relaxations. Why? Sometimes linear=integer Linear relaxations as global constraints Duals and reduced costs&8Z8Z@:Linear=integer formulationsHappens naturally for some problems Network flows Totally unimodular constraint matrices Takes more work, but defined for Matchings Minimum spanning trees Closely associated with polynomial solvabilityj$Z5Z!Z!Z/Z$5!!/B<Duals and Reduced CostsAssociated with the solution of a linear program are the dual values --- one per constraint --- measures the marginal value of changing the right-hand-side of the constraint --- Useful in many algorithmic waysC= Dual exampleSum_i x[i,j]-y[j] <= 0 Suppose facility j* has cost 10 and y*[j*] = 0. The dual value of this constraint is 4. What cost must facility j* have to be appealing? Answer: no more than 10-4=6.D>Dual Example 2Products 1, 2, 3 use chemicals A, B Maximize 3x1+2x2+2x3 Subject to x1+x2+2x3 <= 10; (.667) 5x1+2x2+x3 <= 20; (.667) Solution: x2=6.67 x1=1.67 What objective must a product that uses 4 of A and 3 of B have to be appealing: at least 4.67$%ZZE?.Final advantage of linear relaxations: Global rLinear relaxations are Relatively easy to solve: huge advances in 15 years Incorporate  global information Often provide good bounds and guidelines for integer program Variables with very bad reduced cost likely not in optimal integer solution Rounding doesn t always work, but often gets good feasible solutions@1*Feasible solutionsSolutions that satisfy all the constraints but might not be optimal Generally found by heuristics Can be problem specific Must have value greater than or equal to optimal value (for minimizing)6D6HD6H2+Feasible Solution3-&Fundamental Branch and Bound AlgorithmSolve relaxation to get x* If infeasible, then IP infeasible Else If x* feasible to IP, then x* optimal to IP Else create new problems IP1 and IP2 by branching; solve recursively, stop if prove subproblem cannot be optimal to IP (bounding):Z H4. BranchingCreate two or more subproblems IP1, IP2,& IPn such that Every feasible solution to IP appears in at least one (often exactly one) of IP1, IP2, & IPn x* is infeasible to each of R(IP1), R(IP2), & R(IPn) For linear relaxation, can choose a fraction xj* and have one problem with xj <=[xj] and the other with xj >= [xj]+1 ([x]: round down of x) ^8ZZZZ85/ Illustration70BoundingAlong way, we may find solution x that is feasible to IP. If any subproblem has relaxation value c* >= cx then we can prune that subproblem: it cannot contain the optimal solution. There is no sense continuing on that subproblem.$ylKEStoppingTechnique can stop early with solution within a provable percentage of optimal (compare to be relaxation value) Can also modify to generate all solutions (do not prune on ties)81How to make work better?TBetter formulations Better relaxations (cuts) Better feasible solutions (heuristics)92 FormulationsDifferent formulations of integer programs may act very differently: their relaxations might have radically different bounds  Good Formulation of integer program: provides a better relaxation value (all else being equal).=7Back to Warehouse Example Alternative formulation of  Only use if open constraint x[i,j] <= y[j] for all i,j (versus) sum_i x[i,j] <= ny[j] Which is better?*:;>8 Comparing3Positives to original Fewer constraints: linear relaxation should solve faster Positives to disaggregate formulation Much better bounds (consider having x[i,j]=1 for a particular i,j. What would y[j] be in the two formulations?) (Almost) no comparison! Formulation with more constraints works much better.j9&qN9&qN?9IdealF@Embarrassing FormulationsSome things are very hard to formulate with integer programming: Traveling Salesman problem: great success story (IP approaches can optimize 15,000 city problems!), but best IP approaches begin with an exponentially sized formulation (no  good compact formulation known). Complicated operational requirements can be hard to formulate.*AAGAFurther approaches0Branch and Price Formulations with exponential number of variables with complexity in generating  good variables (see Nemhauser): heavy use of dual values Branch and Cut Improving formulations by adding additional constraints to  cut off linear relaxation solutions (more later)TZZZnZnw Algorithmic Details8Preprocessing Primal Heuristics Branching Cut Generation99 PreprocessingProcess individual rows to detect infeasibilities detect redundancies tighten right-hand-sides tighten variable bounds Probing: examine consequences of fixing 0-1 variable If infeasible, fix to opposite bound If other variables are fixed, inequalities j\5P\5P Preprocessing'Much like simple Constraint Programming&( Improving Coefficients3x1-2x2 1 1. Convert to with pos. coefficients with y1 = 1-x1 3y1 + 2x2 2 2. Note that constraint always satisfied when y1 = 1, so change coefficient 3 to 2 2y1 + 2x2 2 3. Convert back to original x1 -x2 1V Z8ZZSZZZ Z-3#  Improving (?) CoefficientsManual or Automatic?Modeling issue Automatic identification not foolproof Generally easy to see Can provide problem-knowledge to further reduce coefficients&zz Automatic issue Many opportunities will only occur within Branch and Bound tree as variables are fixed  More foolproof as models change&yy (Identifying Redundancy and InfeasibilityUse upper and lower bounds on variables: Redundancy 3x1 - 4x2 + 2x3 6 (max lhs is 5) Infeasibility 3x1 - 4x2 + 2x3 6 (max lhs is 5) While very simple, can be used to fix variables, particularly within B&B tree)Z Z#ZZ#ZZNZ) O PP: Fixing VariablesSimple idea: if setting a variable to a value leads to infeasibility, then must set to another value 3x1-4x2+2x3-3x4 3 Setting x4 to 1 leads to previous infeasible constraint, so x4 must be 0 gZZKZh 2  PP: Implication InequalitiesMany constraints embed restrictions that at most one of x and y (or their complements) are 1. This can lead to implication inequalities. Z81PP: Implication Inequalities4Facility location x1+x2+& +xm mx0 x0 = 0 x1 = 0 x0 = 0 x2 = 0, etc. (1-x0) + x1 1 (or x1 x0) x2 x0 , etc. Automatic disaggregation (stronger!)ruZ&Z $,d  PP: Clique Inequalities These inequalities found by  probing (fix variable and deduce implications). These simple inequalities can be strengthened by combining mutually exclusive variables into a single constraint. Resulting clique inequalities are very  strong when many variables combined.0Z0 Example: Sports SchedulingProblem: Given n teams, find an  optimal (minimum distance, equal distance, etc.) double round robin (every team plays at every other team) schedule. A: @B @C D B C @D B: A D @C @A @D C C: @D A B D @A @B D: C @B @A @C B AFZS Sports Scheduling<Many formulations (not wholly satisfactory) One method: One variable for every  home stand (series of home games) and  away trip (series of away games).  Variables (team A)Some variables:  ConstraintsJCan only do one thing in a time slot y1+x1+x2 1 x1+x2+y2 1 No  Away after Away x1+x2+x3 1 No  Home after Home y1+y2 1 Additional constraints link teams %ZZZ ZZ Z"ZZZ. "Improving FormulationCreate Implication Graph Find cliques#Cliques in graph: can only have one ConstraintshCan only do one thing in a time slot y1+x1+x2 1 x1+x2+y2 1 No  Away after Away x1+x2+x3 + y2 1 No  Home after Home y1+y2 + x1 + x2 1 Additional constraints link teams %ZZZZZZ"ZZZ.  "Clique InequalitiesResulting formulation is much tighter (turns formulation from hopeless to possible) Idea generalized to variables and their complements Can be found automatically, but may be a huge number (and clique generally hard) On divide of  automatic and  manual modeling issuePrimal HeuristicsFeasible solutions at B&B nodes can greatly decrease the solution time Most common: problem-specific heuristics embedded with B&B Some general purpose heuristics: LP Diving, Pivot and Complement LP-Diving(1. Solve LP 2. Stop if infeasible or integral 3. Fix all integral variables (or all 1 s) 4. Select fractional variable and fix to integer 5. Go to 1 BranchingTwo decisions: which B&B node to branch on and how to divide into two problems Node selection Depth First: try for integral solution Best Bound: explore  appealing nodes Adaptive: Depth First first, then best bound&_z_zBranching: How to branchPriorities on variables and sets is extremely important Normal branching is on a variable equals 0 or equals 1, but much more complicated branching possible: x1 + x2 + x3 + x4 1 Could lead to two problems: a) x1 + x2 = 0 b) x3 + x4 =0ZZ:Z        Branching as ModelingSpecially Ordered Sets of Type 2 (no more than 2 positive, must be adjacent): used to model piecewise linear functions: x1,x2,x3,& xm can lead to two problems: 6x/Adding constraintsConstraints can strengthen formulation: we have seen clique inequalities already Can be added on an  as needed basis during calculations (generally to move away from current fractional solution).!Separation ProblemGiven a fractional solution to the LP relaxation, find an inequality that is not satisfied by the fractional solution. Algorithm should be - fast - yield strong inequality - heuristics acceptableTypes of Constraints1. Feasibility: A large number of constraints is used in formulation - connectivity constraints (i.e. TSP) - nonlinearities 2. Problem specific facets - blossom inequalities for matching - comb inequalities for TSP 3. General IP constraints$r{ Gomory Constraints ,Any fractional solution from the simplex method can be separated: xb + 2.5 x1 - 3.2 x2 = 2.1 where current sol. is xb =2.1, x1 = x2 = 0 xb + 2 x1 - 4 x2 - 2 = .1 - .5 x1 -.8 x2 LHS is integer so RHS must be also .1 - .5 x1 -.8 x2 0 is valid and violated by current solution B,*#+B            ,  . HB.HB: Real Version of Gomory CutsICWorking through examplePrevious example becomes .5x1+.2x2 >= .9, which is a good, strong constraint (can extend all this to mixed integer programs easily)"Gomory Constraints (modeling)UAre we done? Very good to have available but likely not the only tool in the arsenal.#0-1 Knapsack CoversFor problems that contain constraints like: Sj N ajxj b C N is a cover if Sj C aj > b then Sj C xj |C| - 1 is valid,  ,>1 $ Separation of Cover InequalitiesGiven fractional LP solution x*, is there a cover C for which x* violates the cover inequality? Solvable by a binary knapsack problem (one constraint IP): can be solved heuristically, or exactly by dynamic programmingLZ %Lifting of Cover InequalitiesConstraints can be strengthened: 20x1+16x2+15x3+10x4+30x5 40 Cover on {1,2,3} leads to x1+x2+x3+0x4+0x5 2 Is the  0 coefficient on x4 the best possible? Can solve knapsack to get x1+x2+x3+x4+0x5 2!J$.& Lifing of Cover Inequalities^We could continue to x5 to get x1+x2+x3+x4+x5 2 If we had done x5 first, we would have got x1+x2+x3+0x4+2x5 2 Different lifting sequences lead to different inequalities XZZ+ZZ=Z <'!Modeling implications4Cover inequalities generally part of the software, rather than the modeling (but if software has capability, do not include in model). Decision is whether to use the inequalities or not essentially numerical question Lifting is extremely important, as is relationship of covers in subproblems to full problem55 JD ConclusionsfThere is lots to integer programming! Interesting interplay between formulations and algorithms Much intelligence embedded in software, making formulations a bit more  fool-proof ("Papers to ReadProgress in Linear Programming Based Branch and Bound Algorithms: An exposition, Ellis Johnson, George Nemhauser, and Martin Savelsbergh MIP: Theory and Practice  Closing the Gap, Robert Bixby, Mary Fenelon, Zonghao Gue, Ed Rothberg, and Roland WunderlingDP:+L  ` 33PP` 3333` ___MMM` 13` 333fpKNāvI` j@v۩ῑ΂H` Q_{>?" dd@,?n<d@ `7 `2@`7``2 n?" dd@   @@``PR    @ ` ` p>> G ?  L (  L L <!x H  "  " L T"xd H  "  " L <t"xU_ H  "  " L T"xd>& H  "  " L N4#xP H  "  " L <#xp H  "  " L C x#x?d?bUv H  "  "  L 6$x U x T Click to edit Master title style! !"$  L 0%x   x RClick to edit Master text styles Second level Third level Fourth level Fifth level!     S"  L 6t%x @ x G* " "  L 6%x @`  x I*  " "  L 64&x ` x I*  " "B L s *޽h ? 3333  Blends4     @Pz (  PT + P +"bb P@ P# Dwo"h P s *PP" P Bd P@"bb P 0  P# Ny"h P s *P  " P BdP 0 "z  P < a*"h  P s *"  P  f?d?+)"  P <4b ?pP x T Click to edit Master title style! !"  P 0b  `   x W#Click to edit Master subtitle style$ $" P 6Tc `p  x K*" " " P 6c `p  x M*$ " " P 6d ` x M*$ " "B P s *޽h ? 3333 00(  x  c $td PpP x x  c $d P `   x H  0޽h ? ^WNff3  P0(  x  c $Tf LU  x x  c $f L  x H  0޽h ? ^WNff3  `0(  x  c $h LU  x x  c $Ti L  x H  0޽h ? ^WNff3X  p (  x  c $E  LSP   x  c $TF  L      TG  ?   < X: variables     l0e0e    BCDEF A@  A5% 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||`xp8@@  0   TG  ? f @Linear objective   l0e0e    BCDEF A@  A5% 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||p8` (@  P   TH  ?0  BLinear constraints   l0e0e    BChDEF A@  A5% 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||8(P(<h@  p  TTI  ?z #  BMakes things hard!  TI  ?j  <    l0e0e    BCPDEF A@  A5% 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||P Xd,@   P H  0޽h ? ^WNff3  0(  x  c $tJ  LU   x  c $J  L    H  0޽h ? ^WNff3  0(  x  c $K  LU   x  c $TL  L    H  0޽h ? ^WNff3  0(  x  c $4N  LU   x  c $N  L    H  0޽h ? ^WNff3  0(  x  c $O  LU   x  c $P  L    H  0޽h ? ^WNff3  0(  x  c $P  LU   x  c $$  L    H  0޽h ? ^WNff3  0(  x  c $D  LU   x  c $  L    H  0޽h ? ^WNff3  6.).@(  x  c $$  LU   vB  ND?  x8   . ~B  ND?2  Z ? 0P  < ~2  N? P ~2  N? P 2   T?p P 2   T? P 2   T? P 2   T?P P 2   T? 0P ~2  N? 0 ~2  N?  ~2  N?  ~2  N?p  2  T?  2  T?  2  T?P  2  T? 0 ~2  N?@0~2  N?@~2  N?@2  T?p@2  T? @ 2  T? @ 2  T?P @ 2   T?@0~2 " N?0`2 # T?`2 $ T?`2 % T?p`2 & T?  `2 ' T?  `2 ( T?P  `2 ) T?0`~B * ND?@@~B + ND?@B , TD?@P B - TD?  0H  0޽h ? ^WNff3  ),L(   ,  0e0e    BCDEF  A5% 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @`P 0 x  c $  LU  x |B  TD?2  Z ? p`  < v2  N? P` v2  N? 0` |2  T? p` |2  T? ` |2  T? @ ` |2  T? P ` |2  T? p` v2  N? p v2  N? P v2  N? 0 v2  N? p |2  T? |2  T? @ |2  T? P |2  T? p v2  N?Ppv2  N?PPv2  N?P0|2  T?Pp|2  T?P |2  T?P@ |2  T?P P |2  T?Ppv2  N?pp|2  T?Pp|2  T?0p|2  T?pp|2 ! T? p|2 " T?@ p|2 # T? P p|2 $ T?pp|B % TD?P P |B & TD? B ' ZD?B ( ZD?P @ vB * ND?0 0 H  0޽h ? ^WNff3  0(  x  c $$  LU   x  c $d  L    H  0޽h ? ^WNff3   0(  x  c $T` LU  x x  c $` L  x H  0޽h ? ^WNff3  0(  x  c $  LU   x  c $  L    H  0޽h ? ^WNff3    0(   x   c $$  LU  b x   c $  L  b H   0޽h ? ^WNff3  0$0(  $x $ c $  LU  b x $ c $  L  b H $ 0޽h ? ^WNff3  @(0(  (x ( c $T(c LU  b x ( c $(c L  b H ( 0޽h ? ^WNff3  P0(  x  c $4*c LU  b x  c $*c L  b H  0޽h ? ^WNff3%  `++e(  x  c $,c LU   vB  ND?2  Tt,c? p`  < p2  H? P` p2  H? 0` v2  N? p` v2  N? ` v2  N? @ ` v2  N? P ` v2  N? p` p2  H? p p2  H? P p2  H? 0 p2  H? p v2  N? v2  N? @ v2  N? P v2  N? p p2  H?Ppp2  H?PPp2  H?P0v2  N?Ppv2  N?P v2  N?P@ v2  N?P P v2  N?Ppp2  H?ppv2  N?Ppv2  N?0pv2  N?ppv2  N? pv2 ! N?@ pv2 " N? P pv2 # N?ppvB $ ND?P P vB % ND? |B & TD? 0|B ' TD? ` @vB ( ND?0 0 v ) N ?`   * T4-c ?*J AFeasible solution +  l0e0e    B`CDEF A@  A5% 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|||`H@ `@@   P H  0޽h ? ^WNff3  p0(  x  c $T.c LU  c x  c $.c L  c H  0޽h ? ^WNff3  0(  x  c $0c LU  c x  c $T1c L  c H  0޽h ? ^WNff3     01* (   /  0e0e    BC@DEF  A5% 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||@@ @`  0  .  0e0e    BC0DEF  A5% 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||00 @`Px  c $3c LU  b vB  ND?2  T3c? p`  < p2  H? P` p2  H? 0` v2  N? p` v2  N? ` v2  N? @ ` v2  N? P ` v2  N? p` p2  H? p p2  H? P p2  H? 0 p2  H? p v2  N? v2  N? @ v2  N? P v2  N? p p2  H?Ppp2  H?PPp2  H?P0v2  N?Ppv2  N?P v2  N?P@ v2  N?P P v2  N?Ppp2  H?ppv2  N?Ppv2  N?0pv2  N?ppv2  N? pv2 ! N?@ pv2 " N? P pv2 # N?ppvB $ ND?P P vB % ND? |B & TD?0 p|B ' TD? vB ) ND?0 0  * TTc ?Z z  2x* +  l0e0e    BPCDEF A@  A5% 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||Ph<4(\T@  P 0 vB , ND? vB - ND?   0 Tc ?Z1z 3IP1 1 Tc ?: Z  3IP2H  0޽h ? ^WNff3  0(  x  c $4c LU  c x  c $c L  c H  0޽h ? ^WNff3  D0(  Dx D c $c LU  b x D c $4c L  b H D 0޽h ? ^WNff3  0(  x  c $Tc LU  e x  c $c L  e H  0޽h ? ^WNff3  0(  x  c $c LU  e x  c $4c L  e H  0޽h ? ^WNff3  0(  x  c $c LU  e x  c $tc L  e H  0޽h ? ^WNff3  0(  x  c $c LU  e x  c $c L  e H  0޽h ? ^WNff3  */ $(    .   0e0e    BCDEF"  A5% 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||@@`0 x   c $e LU  c vB   ND?  |B   TD?2   ZTe? 0P  < v2   N? P v2   N? P |2   T? pP |2   T? P |2   T? P |2   T? P P |2   T? 0P v2   N? 0 v2   N?  v2   N?  v2   N? p |2   T?  |2   T?  |2   T? P  |2   T? 0 v2   N?@0v2   N?@v2   N?@|2   T?@p|2   T?@ |2   T?@ |2   T?@P |2   T?@0v2   N?0`|2   T?`|2 !  T?`|2 "  T?p`|2 #  T? `|2 $  T? `|2 %  T?P `|2 &  T?0`B )  ZD?@ vB +  ND?p0vB ,  ND? vB -  ND? p /  He ?pv h8Formulation gives convex hull of feasible integer points99H   0޽h ? ^WNff3  ,0(  ,x , c $ԗe LU  e x , c $4e L  e H , 0޽h ? ^WNff3   00(  0x 0 c $e LU  e x 0 c $te L  e H 0 0޽h ? ^WNff3 00(  x  c $Te PpP e x  c $e P `   e H  0޽h ? ̙334  @\(  x  c $te LU  e   c $ԝe L <$  0 c H  0޽h ? ^WNff3  P0(  x  c $e LU  f x  c $te L  f H  0޽h ? ^WNff3  ` \(   x  c $Of LU  f   c $Of L <$  0 f H  0޽h ? ^WNff3n     p$ (  $x $ c $Qf LU  f dB $ <DP dB $ <DP P ^B $ 6D ^B $ 6D  $ BdQfj F   1  $ BQfz 1^B  $ 6D^B  $ 6D P ^B  $ 6D p ^ $ 6 P db $ <Z P l  `  $@h0 ,$D 0b $ NZ33?p ,$D 0 $ TRf ?@  ` ,$D 0 NCuts off (1/2, 1/4) and others $  l0e0e    BCDEF A@  Ao 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||(xP(0@  ` ( ,$D 0H $ 0޽h ? ^WNff3p   h(  hx h c $Sf LU  e x h c $Tf LK  e x h c $dTf L  e H h 0޽h ? ^WNff3  0\(  0x 0 c $$Uf LU  f  0 c $Uf L <$  0 f H 0 0޽h ? ^WNff3  40(  4x 4 c $Wf LU  f x 4 c $$Xf L  f H 4 0޽h ? ^WNff3  8*(  8x 8 c $DSf LU  f r 8 S DPf L0D f H 8 0޽h ? ^WNff3  @0(  @x @ c $Zf LU  f x @ c $dZf L  f H @ 0޽h ? ^WNff3  D0(  Dx D c $dWf LU  f x D c $$Of L  f H D 0޽h ? ^WNff3  H0(  Hx H c $e LU  f x H c $e L  f H H 0޽h ? ^WNff3  L0(  Lx L c $e LU  f x L c $c L  f H L 0޽h ? ^WNff3q  !$9P(  Px P c $c LU  e x P c $4c L  e vB P ND?P  P vB P ND?  vB P ND?  vB P ND? vB  P ND? ` `   P Tc ?  12 P Ttc ?   13 P T)c ? v J  14vB P ND?   P T+c ? 6  11p P H33 ? ` p P H33 ?  p P H33 ?  p P H33 ?  p P H33 ?0 P p  P H33 ?0 P p !P H33 ?p "P H33 ? p #P H33 ? $P Tt)c ?0P 1H &P T43c ?s 2@B (P T40c ? 2@C *P T-c ?` C  2@C ,P T  ?`   2@D -P T  ?   1H .P T  ?   1H 0P T  ?0 ^ P  2@E 2P TD  ?0 9 P  2@F 3P TD  ?0P 2y1 5P T  ?Pp 2x1 7P TD  ?0 P  2x2 8P T  ?   2y1 9P TJ  ?0 P  2x3H P 0޽h ? ^WNff3  T\( o( Tx T c $TO  LU  x  T c $M  L <$ 0 x H T 0޽h ? ^WNff3-  9-1- 48X,(  Xx X c $tP  LU  f x X c $E  L  f z X s *K   `  t X c $4e  @  vB X ND?P  P vB X ND?  vB X ND?  vB  X ND? vB  X ND? ` `   X Te ?  12  X Te ?   13  X Th ? v J  14vB X ND?   X T4h ? 6  11p X H33 ? ` p X H33 ?  p X H33 ?  p X H33 ?  p X H33 ?0 P p X H33 ?0 P p X H33 ?p X H33 ? p X H33 ? X Tfe ?0P 1H X T4ge ?s 2@B X Tge ? 2@C X Tge ?` C  2@C X TThe ?`   2@D X The ?   1H X Tie ?   1H  X Ttie ?0 ^ P  2@E !X Tie ?0 9 P  2@F "X T4je ?0P 2y1 #X Tje ?Pp 2x1 $X Tje ?0 P  2x2 %X TTke ?   2y2 &X Tke ?0 P  2x3v2 'X N?`pv2 (X N?pv2 )X N?` p v2 *X N? p@ v2 +X N?` p |B ,X TDo?@@|B .X TDo?@@` |B /X TDo? @@ |B 0X TDo?@ @@` | 2X S T0e0e    B CDEF A@  Ao 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| lPL @  ` | 3X S T0e0e    BPC0DEF A@  Ao 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||P(PP80@  p | 4X S T0e0e    BCDEF A@  Ao 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @ @  p | 5X S T0e0e    BPCDEF A@  Ao 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||PPP8@   p` | 8X S T0e0e    BPC DEF A@  Ao 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||P@P @   H X 0޽h ? ^WNff3.  --066\[-( |00 \x \ c $le LU  e x \ c $tle L  e z \ s *le  `  t \ c $4me  @  z \ s *me  `  t \ c $me  @  vB \ ND?P  P vB  \ ND?  vB  \ ND?  vB  \ ND? vB  \ ND? ` `   \ TTne ?  12 \ Tne ?   13 \ Toe ? v J  14vB \ ND?   \ Ttoe ? 6  11p \ H33 ? ` p \ H33 ?  p \ H33 ?  p \ H33 ?  p \ H33 ?0 P p \ H33 ?0 P p \ H33 ?p \ H33 ? p \ H33 ? \ Toe ?0P 1H \ T4pe ?s 2@B \ Tpe ? 2@C \ Tpe ?` C  2@C \ TTqe ?`   2@D  \ Tqe ?   1H !\ Tre ?   1H "\ Ttre ?0 ^ P  2@E #\ TT  ?0 9 P  2@F $\ T  ?0P 2y1 %\ T  ?Pp 2x1 &\ Tt  ?0 P  2x2 '\ T  ?   2y2 (\ T4  ?0 P  2x3p2 )\ H33?`pp2 *\ H33?pp2 +\ H33?` p p2 ,\ H33? p@ v2 -\ N?` p |B .\ TDo?@@|B /\ TDo?@@` |B 0\ TDo? @@ vB 1\ ND?@ @@` ^ 2\  60e0e    B CDEF @  o 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| lPL @  ` ^ 3\  60e0e    BPC0DEF @  o 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||P(PP80@  p  4\ c Z0e0e    BCDEF @  5% 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E|| @ @  p  5\ c Z0e0e    BPCDEF @  5% 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||PPP8@   p` ^ 6\  60e0e    BPC DEF @  o 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||P@P @   H \ 0޽h ? ^WNff3  @`<( w `~ ` s *  LU  e ~ ` s *  L  e H ` 0޽h ? ^WNff3  Pd0(   dx d c $T  LU  e x d c $  L  e H d 0޽h ? ^WNff3  `p0(  px p c $T  LU  e x p c $  L  e H p 0޽h ? ^WNff3  pt0(  tx t c $  LU  e x t c $t  L  e H t 0޽h ? ^WNff3  x0( X "d  xx x c $  LU  e x x c $  L  e H x 0޽h ? ^WNff3  |0(  |x | c $t  LU  e x | c $  L  e H | 0޽h ? ^WNff3  "G(  x  c $4  LU  e x  c $  L  e  8 p P  !   N 33?p P  11x  H33?P 0   N$33?0   3k-2  N33?  3k-1~  N ?    N?  3k+1   ND?   3k+2   N?p P  1mx   H? p   T ?F   1k  Td ?@` `.Either all of the blue or all of the red are 0/(2/8   "P`0 B  TD33o? B  TD33o?p B  TD33o?p`  B  TD33o? p` ~2  N?P 0 ~2  N?P ~2  N?@ P ~2  N?0 P ~2   N?@H  0޽h ? ^WNff3  0(  x  c $$ LU  e x  c $ L  e H  0޽h ? ^WNff3  0( = x  c $d LU  c x  c $ L  c H  0޽h ? ^WNff3  0(  x  c $D LU  c x  c $ L  c H  0޽h ? ^WNff3  \(  x  c $ LU  c   c $$ L <$ 0 c H  0޽h ? ^WNff3Y   4(  4x 4 c $ LU  c  4 c $d L  c u]y+ sum_j ajxj =d Let d=[d]+f; let aj=[aj] + fj t=y+sum_(j:fj<=f) [aj]xj + sum_(j:fj>f) ([aj]+1)xj So d-t = sum_(j:fj<=f) fjxj+sum_(j:fj>f) (fj-1)xj Either t<=[d] => sum_(j:fj<=f) fjxj >= f t>=[d]+1 => sum_(j: fj>f) (1-fj)xj >= 1-f Divide through to get RHS of 1 in each case. Result gives sum(j:fj<=f) (fj/f)xj + sum(j: fj>f) (1-fj)/(1-f)xj >= 1^Z^   H H 4 0޽h ? ^WNff3  <0(  <x < c $> LU  c x < c $d> L  c H < 0޽h ? ^WNff3  0(  x  c $? LU  c x  c $? L  c H  0޽h ? ^WNff3   0(  x  c $@ LU  c x  c $A L  c H  0޽h ? ^WNff3  00(  x  c $A LU  b x  c $$B L  b H  0޽h ? ^WNff3  @\(  x  c $C LU  b   c $D L <$  0 b H  0޽h ? ^WNff3  P\(  x  c $D LU  b   c $$E L <$ 0 b H  0޽h ? ^WNff3  `0( PbŔ x  c $E LU  b x  c $DF L  b H  0޽h ? ^WNff3  p@0(  @x @ c $$H LU  b x @ c $H L  b H @ 0޽h ? ^WNff3  0(  x  c $I LU  b x  c $$Z L  b H  0޽h ? ^WNff3r00npr Pt w b:> 6 .&%#' )%24z6r8:<@PH@8hp !#$EIKxMOQjl1+0>GpBMOh+'0| hp  8 D P\dFilling in the BlanksPMichael Trick BLC:\Program Files\Microsoft Office\Templates\Presentation Designs\Blends.potmichela18hMicrosoft PowerPointoso@pUe@[.]@ult GoM  6& &&#TNPPp0D x & TNPP &&TNPP    --- !---&o& i=33--- !2. ---&G i=&--77- $G I I=G=AA- $I K K=I=NN- $K M M=K=^^- $M O O=M=ss- $O R R=O=- $R T T=R=- $T V V=T=- $V X X=V=- $X Z Z=X=- $Z \ \=Z=- $\ ^ ^=\=- $^ ` `=^=- $` c c=`=- $c e e=c=- $e g g=e=- $g i i=g=---&&&&+8yj--- !2,8,---&R8yi&--- $R8T8TiRi*- $T8W8WiTi?- $W8Y8YiWiT- $Y8\8\iYik- $\8^8^i\i܁- $^8a8ai^i- $a8c8ciai- $c8e8eici- $e8h8hiei- $h8j8jihi- $j8m8miji- $m8o8oimi- $o8r8rioi- $r8t8tiri- $t8w8witi- $w8y8yiwi---&&&&0;\&--&&- $<0 <5++- $<5 <;??- $<;<@TT- $<@<Fjj- $<F<K- $<K%<Q- $<Q%*<V- $<V*0<\- $<\05<a- $<a5;<g- $<g;@<l- $<l@F<r- $<rFK<w- $<wKQ<}- $<}QV<- $<V\<&&&- & $0\;\;0&&-&& &&-&&]<0&&- $<0 <5++- $<5 <;??- $<;<@TT- $<@<Fjj- $<F<K- $<K%<Q- $<Q%*<V- $<V*0<\- $<\05<a- $<a5;<g- $<g;@<l- $<l@F<r- $<rFK<w- $<wKQ<}- $<}QV<- $<V\<&- --&&--- !oC---&!V\&--###- $!VZVZ\!\333- $ZVV\Z\EEE- $VV\\XXX- $VV\\mmm- $V>V>\\- $>VwVw\>\- $wVV\w\- $VV\\- $V#V#\\- $#V\V\\#\- $\VV\\\- $VV\\- $VV\\- $V@V@\\- $@VyVy\@\- $yVV\y\---&&&&g1&; wwgw; - &g& --9h-- "Tahoma wwgw - 33.*2 rIntroduction to Integer! !  ! !!. 33.+2 rProgramming Modeling and !12 ! .! !! !. 33.2 'rMethods- !.--Q1-- 33"Tahoma; wwgw; - .2 f Michael Trick!   . ..2 Carnegie Mellon University  !    . .62 BCPAI-OR School, Le Croisic 2002      .--"Systemw fB  -&TNPP &՜.+,D՜.+,   $ , _Presentazione su schermoersCBI - Carnegie MellonmoCFj LTimes New RomanTahoma WingdingsSymbol Courier NewBlends9Introduction to Integer Programming Modeling and Methods Some HistoryScopeInteger Program (IP)Rules of the GameExample FormulationsWarehouse FormulationWarehouse FormulationBinary Integer Programs Key concepts IllustrationLinear Relaxation)Why this fetish with Linear Relaxations?Linear=integer formulationsDuals and Reduced Costs Dual exampleDual Example 2/Final advantage of linear relaxations: Global Feasible solutionsFeasible Solution'Fundamental Branch and Bound Algorithm Branching Illustration Bounding StoppingHow to make work better? FormulationsBack to Warehouse Example ComparingIdealEmbarrassing FormulationsFurther approachesAlgorithmic DetailsPreprocessingPreprocessingImproving CoefficientsImproving (?) CoefficientsManual or Automatic?)Identifying Redundancy and InfeasibilityPP: Fixing VariablesPP: Implication InequalitiesPP: Implication InequalitiesPP: Clique InequalitiesExample: Sports SchedulingSports SchedulingVariables (team A) ConstraintsImproving Formulation Find cliques ConstraintsClique InequalitiesPrimal Heuristics LP-Diving BranchingBranching: How to branchBranching as ModelingAdding constraintsSeparation ProblemTypes of ConstraintsGomory ConstraintsReal Version of Gomory CutsWorking through exampleGomory Constraints (modeling)0-1 Knapsack Covers!Separation of Cover InequalitiesLifting of Cover InequalitiesLifing of Cover InequalitiesModeling implications ConclusionsPapers to Read Caratteri utilizzatiModello strutturaTitoli diapositiveF 6> _PID_GUIDAN{EE30EE39-425B-11D6-B7C2-0050046C92E7}_Cmichela  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !#$%&'()*+,-./013456789;<=>?@AFRoot EntrydO)Current User:SummaryInformation("PowerPoint Document(CDocumentSummaryInformation82Root EntrydO)6&lJ@Current User'SummaryInformation("PowerPoint Document(C      !#$%&'()*+,-./013456789F_Cmichela