DOC PREVIEW
SJSU ISE 230 - Integer Programming 3

This preview shows page 1-2-3-4-27-28-29-30-56-57-58-59 out of 59 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 59 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 59 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 59 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 59 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 59 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 59 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 59 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 59 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 59 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 59 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 59 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 59 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 59 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Integer Programming 3Review from Last LectureBranch and BoundOn Bounds from Linear ProgrammingOverview of cutting planesGoals of this lecturePowerPoint PresentationSlide 8Slide 9Set Packing ProblemSlide 11The First Integer Programming FormulationSlide 13Getting an improved LPAn improved integer programSlide 16Slide 17Slide 18Slide 19Slide 20Slide 21ReviewUsing Cutting PlanesSlide 24Slide 25More on adding constraints“Pure” Cutting Plane TechniqueWhere do these cuts come from?Problem SpecificThe LP RelaxationGetting constraints from coversSlide 32After one cutAfter two cutsObtaining a stronger constraintAfter “three” cutsWe eliminate the redundant constraintsSummary for knapsack problemSlide 39Comments on the TSPThe TSP as an IP, almostSubtour: a cycle that passes through a strict subset of citiesA subtour breaking constraintSlide 44Formulation of the TSP as an IPMore on the TSPGomory Cuts: a method of generating cuts using LP tableausGomory CutsWhat to do if coefficients are negativeIn generalHow to generate cutting planes?Integer Programming SummaryIP Solution Techniques SummaryExample: Fire company location.Example for the Fire Station ProblemSet covering problemCovering constraints are commonIndependent Set (set packing)Set Packing constraints arise often in manufacturing and logisticsMIT and James Orlin © 20031Integer Programming 3Brief Review of Branch and Bound Cutting plane techniques for getting improved boundsMIT and James Orlin © 20032Review from Last LectureInvestment 1 2 3 4 5 6 Cash Required (1000s) $5 $7 $4 $3 $4 $6 NPV added (1000s) $16 $22 $12 $8 $11 $19 Investment budget = $14,000maximize 16x1 + 22x2 + 12x3 + 8x4 +11x5 + 19x6subject to 5x1 + 7x2 + 4x3 + 3x4 +4x5 + 6x6  14 xj binary for j = 1 to 6MIT and James Orlin © 20033Branch and Bound12 3x1 = 0 x1 = 14444444x2 = 0425x2 = 16x2 = 07x2 = 144 44 44The incumbent solution has value 43 8x3 = 09x3 = 110x3 = 011x3 = 112x3 = 013x3 = 143 43 43 43 44-8 9 10 11--14 1516 17444418 19-38MIT and James Orlin © 20034On Bounds from Linear ProgrammingWe found an incumbent integer solution with a value of 43.The best LP solution value is between 44 and 45.Is there a way that we could have directly established an upper bound between 43 and 44? Perhaps we could form a “better linear program.”The closer the LP is to the Integer Program, the better.Note: not all LP formulations are the same in terms of “closeness”MIT and James Orlin © 20035Overview of cutting planesTry to get better bounds so that more nodes of the branch and bound tree can be fathomed, and the fathoming can be done earlier.Recall: we eliminate a node j if the LP bound for j is no more than the value of the incumbent.–The lower the bound (for a maximization problem) the betterThis lecture will provide several approaches for obtaining bounds.MIT and James Orlin © 20036Goals of this lectureIllustrate how valuable obtaining better LP’s can beIllustrate techniques for obtaining better bounds–set packing–capital budgeting–traveling salesman problem–general integer programsMIT and James Orlin © 20037What is the maximum number of diamonds that can be packed on a Chinese checkerboard.Special Thanks to Professor Andreas Schulz for this example.MIT and James Orlin © 20038The diamonds are not permitted to overlap, or even to share a single circle. What is the best packing you can find?MIT and James Orlin © 20039Is this the best possible?MIT and James Orlin © 200310Set Packing ProblemLet D be the collection of diamondsLet O be the pairs of diamonds that overlap. – (d, d’)  O, implies that diamonds d and d’ have a point in commonDecision variables: xd for d  D–xd = 1 if diamond d is selected–xd = 0 if diamond d is not selected.MIT and James Orlin © 200311How many decision variables are there?There are 88 black circles.For each black circle, one can hang a yellow diamond from it.So, there are 88 possible yellow diamonds.And there are 88 green and red diamonds.for a total of 264 diamonds.MIT and James Orlin © 200312The First Integer Programming Formulation10 1Maximize subject to for all ( , ') and integer for dd Dd dd dxx x d d Ox x d D��+ � �� � ��The optimal objective value for this IP is 27.The optimal objective value for the LP relaxation is 132.This problem is known as the set packing problem.MIT and James Orlin © 200313For many dots, there are 12 diamonds that go through the dot.56871234Heading towards an improved IP formulation.MIT and James Orlin © 200314Getting an improved LPx1 + x2  1x1 + x3  1x1 + x4  1x2 + x3  1x2 + x4  1x3 + x4  1x1, x2, x3, x4  {0,1}Conclusion: x1 + x2 + x3 + x4  1We say that S is an overlapping set of diamonds, if every two diamonds in S overlap.1 dd Sx���for each overlapping set S.MIT and James Orlin © 200315An improved integer program10 1Maximize subject to for each overlapping set and integer for dd Ddd Sd dxx Sx x d D���� � ���The optimal objective value for this IP is 27The optimal objective value for the LP relaxation is 27.5Next: a proof that the at most 27 diamonds can be packed.MIT and James Orlin © 200316Node Weight11/21/31/60The weight of a diamond is the sum of its node weights.MIT and James Orlin © 200317Node Weight11/21/31/60The weight of a diamond is the sum of its node weights.Each diamond has weight at least 1.MIT and James Orlin © 200318Node Weight11/21/31/60The weight of 28 independent diamonds would be at least 28. But the total weight of all nodes is 27.5The weight of 27 independent diamonds is at least 27. 18 124 6MIT and James Orlin © 200319Node Weight11/21/31/60No solution has more than 27 diamonds.The weights were the shadow prices for the LPMIT and James Orlin © 200320The Optimal Solution AgainMIT and James Orlin © 200321Set Packing ProblemPutting items into storageManufacturing–How many car doors pack into a metal sheet?–How many rolls of paper can be cut from a giant roll?Closely related to fire station problem: set covering.MIT and James Orlin © 200322Review There may be different ways of formulating an IP.–Each way gives the same IP–The LPs may be very different–Some LPs have different boundsNEXT: The geometry of Integer Programs and Linear ProgramsUsing Cutting PlanesExample. Minimize x + 10y


View Full Document

SJSU ISE 230 - Integer Programming 3

Download Integer Programming 3
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Integer Programming 3 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Integer Programming 3 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?