2 2 1 Integer Programming Duality Lagrangean Duality Integer Programming problems are hard to solve in general However there are some sets of constraints that can be sovled more e ciently than others The main idea is to relax di cult constraints by adding penalties to the cost function instead of imposing them as constraints Consider the primal problem min s t c x Ax b x X where X x Z n Dx d Relax the di cult constraints Ax b with Lagrange multipliers p 0 if the constraints are equalities then p is unconstrained we obtain the problem Z p s t min c x p b Ax x X Property Z p is a piecewise concave function The Lagrange dual problem is written as follows ZD maxp 0 Z p Theorem ZD s t min c x Ax b x conv X N b X is a discrete set with a nite number of points while conv X is a continuous set in fact a polyhedron Why Try drawing these sets for a small example We have that the following integer programming weak duality inequalities always hold for a minimization problem of course ZLP ZD ZIP 2 2 2 BT Excercise 11 12 Comparison of relaxations for an as signment problem with side constraints Note that from weak duality for integer programming problems it follows that ZLP ZD1 ZD2 ZD3 ZD4 ZIP Let F x Z n Dx d Then we have ZLP ZD for all cost vectors c if and only if conv F x Dx d Why Note the following relations n FD1 x Z n n ni 1 xij 1 j j 1 xij 1 i FD2 x Z n n ni 1 nj 1 dij xij b n n FD3 x Z n n nj 1 xij 1 i i 1 j 1 dij xij b FD4 x Z n n nj 1 xij 1 i Let PD1 PD2 PD3 and PD4 denote the polyhedra corresponding to the LP relaxation of the constraints in FD1 FD2 FD3 and FD4 respectively Then the following relations hold conv FD1 PD1 conv FD2 PD2 conv FD3 PD3 conv FD4 PD4 Why are these true Well we always have conv FDi PDi And we have equality when the constraints Dx d de ne an integral polyhedron a polyhedron whose vertices are all integer points so conv F conv z Z n Dx d conv x Dx d x Dx d PD the 2nd equality makes use of the fact that the polyhedron is integral Hence it follows that ZLP ZD1 ZD4 Moreover ZLP ZD2 ZD3 ZIP Finally since conv FD3 conv FD2 hence ZD2 ZD3 Therefore we have ZLP ZD1 ZD4 ZD2 ZD3 ZIP 3 MIT OpenCourseWare http ocw mit edu 15 093J 6 255J Optimization Methods Fall 2009 For information about citing these materials or our Terms of Use visit http ocw mit edu terms 1