SOLVING INTEGER LINEAR PROGRAMS - Computer Science PDF Free Download

1y ago

39 Views

1 Downloads

5.46 MB

93 Pages

Report/dmca

Download PDF

Transcription

SOLVING INTEGERLINEAR PROGRAMS1. Solving the LP relaxation.2. How to deal with fractional solutions?

Integer Linear Program: Examplemaxs.t.0 x1 2x2 0.5x3x1 2x2x1 x2 3x6x1 x2 x6x3 3x4x3 2x4 5x5x4 3x5 4x6x2 x5 x6x 1 , x 2 , · · · , x6x1 , . . . , x 60.2x4x5 0.6x61111111 210Z

Solving ILPsvar x1 integer 0, 10;var x2 integer 0, 10;var x3 integer 0, 10;var x4 integer 0, 10;var x5 integer 0, 10;var x6 integer 0, 10;maximize obj: -x1- 2* x2 -0.5*x3- 0.2* x4 - x5 0.5* x6;c1: x1 2 * x2 1;c2: x1 x2 3* x6 1;c3: x1 x2 x6 1;c4: x3 - 3* x4 1;c5: x3 - 2* x4 -5* x5 1;c6: x4 3* x5 -4 *x6 1;c7: x2 x5 x6 1;solve;display x1, x2,x3, x4, x5, x6;end;

SolutionOriginal ILPx1.val 0x2.val 1x3.val 4x4.val 1x5.val 0x6.val 0Optimal Value: -4.2LP Relaxationx1.val 0.333333333333333x2.val 0.666666666666667x3.val 2.66666666666667x4.val 0x5.val 0.333333333333333x6.val 0Optimal Value: -3.333333

Case-1: Both LP and ILP are feasible.Opt. Solution ofLP relaxationOpt. Solution ofILP

Solving ILPsSolve LP relaxation of the ILP.Case-1: LP relaxation solution satisfies integrality constraint.Case-2: LP relaxation solution does not satisfy the integralityconstraint.

Dealing with Case-2Branch and Bound12Cutting Plane Method.

BRANCH-AND-BOUND:BASIC IDEA

Integer Linear Program: Examplemaxs.t.0 x1 2x2 0.5x3x1 2x2x1 x2 3x6x1 x2 x6x3 3x4x3 2x4 5x5x4 3x5 4x6x2 x5 x6x 1 , x 2 , · · · , x6x1 , . . . , x 60.2x4x5 0.6x61111111 210Z

Step #1: Solve the LP relaxationSolving the LP relaxation.x1.valx2.valx3.valx4.valx5.valx6.val 00.3333333333333330Optimal Value (LP relaxation): -3.333333

Step #2: Choose a branch variablex1.valx2.valx3.valx4.valx5.valx6.val 00.3333333333333330Choose avariable thatshould beintegerOptimal Value (LP relaxation): -3.333333

Step #3: Branching Constraintsmaxs.t.b10 x1 2x2 0.5x3x1 2x2x1 x2 3x6x1 x2 x6x3 3x4x3 2x4 5x5x4 3x5 4x6x2 x5 x6x 1 , x 2 , · · · , x60.2x4x5 0.6x61111111 10Original Problemb2Original Problem Constr.Original Problem Constr. ( x3 2 )( x3 3 )

Visualizationx3 2x3 3

Branch-and-BoundP1P0Original Problem(LP Relaxation)NonIntegralSolutionP3xj bsj cxj bsj cxk : s kOrig. Problem P2xk btk cOrig. Problem xj : s jxjOrig. Problemdsj eP4Orig. Problemxj bsj cxkdtk e

Branch-And-Bound: OperationsBranch-And-Bound Tree: Nodes are ILP P8

Branch-And-Bound Tree7P0Regular Node (to be explored)P3Leaf nodeP4Leaf nodemP5Leaf nodeP0P1P3LeavesP4P2P5P6P7Expand NodeP8

Expanding a NodeSolve the LP relaxation for the node ILP.1.Regular Node(unexplored)Three cases:2.1.2.3.Infeasible.Integral Solution.Fractional Solution.LP relaxation solution

Case-1: Infeasible LP relaxation. LP relaxation is infeasible.Regular Node(unexplored)Infeasible Leaf Node

Case-2: LP relaxation yields integral solution LP relaxation solution is integral: ILP solution LP solution.Regular Node(unexplored)Integral Leaf NodebestObjective : max (lpOptimum, bestObjective)

Case-3: LP relaxation yields a fractionalsolution LP relaxation yields a fractional solution.Regular NodeRegularNode (explored)(unexplored)xj bsj cRegular Node(unexplored)xjdsj eRegular Node(unexplored)LP relaxation solution:x1: x2: x3: Opt. Solution: optSolution

Optimal PruningRegular Node(explored)optSolution bestObjective?LP relaxation solution:x1: x2: x3: Opt. Solution: optSolution

Optimal PruningP0bestObjectiveP1P3P2P4P5P6optSolution bestObjectiveP7P8

Branch-And-Bound Initial NodeOriginal ILP(unexplorednode)bestObjective : -Infinity

BRANCH-AND-BOUND(EXAMPLE)

Original Problemvar x1 integer 0, 10;var x2 integer 0, 10;var x3 integer 0, 10;var x4 integer 0, 10;var x5 integer 0, 10;var x6 integer 0, 10;maximize obj: -x1 - 2* x2 -0.5 * x3 - 0.2* x4 - x5 0.5* x6;c1: x1 2 * x2 1;c2: x1 x2 3* x6 1;c3: x1 x2 x6 1;c4: x3 - 3* x4 1;c5: x3 - 2* x4 -5* x5 1;c6: x4 3* x5 -4 *x6 1;c7: x2 x5 x6 1;solve;display x1, x2,x3, x4, x5, x6;end;

Original ILPinteger solutionx1.val 0x2.val 1x3.val 4x4.val 1x5.val 0x6.val 0Optimal Value: -4.200000LP relaxationx1.val 0.333333333333333x2.val 0.666666666666667x3.val 2.66666666666667x4.val 0x5.val 0.333333333333333x6.val 0Optimal Value: -3.333333

Initial NodebestObjective : - InfinityOriginal Problem(p0.ampl)x3 2p1.amplx3 3p2.amplx1.val 0.333333333333333x2.val 0.666666666666667x3.val 2.66666666666667x4.val 0x5.val 0.333333333333333x6.val 0Optimal Value: -3.333333

Tree #1bestObjective : - Infinityp2.amplOriginal Problem(p0.ampl)x3 2Infeasible!p1.amplx3 3p2.amplx1.val 0.4x2.val 0.55x3.val 3x4.val 0x5.val 0.4x6.val 0.05

p8.amplBnB Treep3.amplx1.val 1x2.val 0x3.val 4.57142857142857x4.val 0x5.val 0.714285714285714x6.val 0.285714285714286Optimal Value: -3.857143p0p1p2p3p5p4p6.amplp6p7x1.val 1x2.val 0x3.val 6x4.val 0x5.val 1x6.val 0.5Optimal Value: -4.750000p8x1.val 1x2.val 0x3.val 5x4.val 0.333333333333333x5.val 0.666666666666667x6.val 0.333333333333333Optimal Value: -4.066667

BnB Treep4.amplp9.amplp0p1bestObjective -4.2p2x1.val 0x1.val 0x2.valx2.val 1 1x3.valx3.val 3 4x4.val 0.666666666666667x4.val 1x5.val 0.111111111111111x5.val 0x6.val 0x6.valValue: 0 -3.744444OptimalOptimal Value: -4.2p3p5p8.amplx1.val 1x2.val 0p7x3.val 6x4.val 0x5.val 1x6.val 0.5Optimal Value: -4.750000p4p6p9p8p10

BnB Treep12.amplp10.amplx1.val 0x2.val 1x3.val 36x4.val 0x5.val 0.33333333333333310.5x6.val 0Optimal Value: -3.833333-5.750000p0p1bestObjective -4.2p2p3p5p4p6p7p9p8p10p11p12

BnB Final Treex1.val 0x2.val 1x3.val 4x4.val 1x5.val 0x6.val 0Optimal Value: -4.200000p0p1bestObjective -4.2p2p3p5p4p6p7p9p8p10p11p12

BRANCH-AND-BOUNDMETHODHeuristics

BnB choices to be made Which unexplored regular leaf node should I expand? How to choose the branching variables? Other tricks: Randomized rounding to find an integer solution? Carrying out BnB at the dictionary level.

BRANCH-AND-BOUNDChoice of unexplored node to expand

General SituationWhich node should I examine first?Unexplored “frontier”

Branch-and-boundp0p1Q: Which one shouldwe examinefirst?p2p3p5p4p6p7p8UnexploredNodes

Goal Minimize the number of nodes explored in the tree. Which node should I expand first: Yield integral solutions. Improve the value of bestObjective.

Unexplored Node Selection Heuristic Deepest node first. Select the node that has largest depth in the tree to explore first. Best LP relaxation solution. Select the node whose LP relaxation has the best answer. Breadth First Search breadth-first.

In Practice ILPs come from some problem domain: eg., We are converting a minimum cost vertex cover computation to ILP. Selection heuristics are best found by experimenting with alarge set of problems from the domain. There is no general rule, unfortunately.

BRANCH-AND-BOUNDChoosing the branch variable

BnB Final Treex1.val 0x2.val 1x3.val 4x4.val 1x5.val 0x6.val 0Optimal Value: -4.200000p0p1bestObjective -4.2p2p3p5p4p6p7p9p8p10p11p12

What if we chose a different branch variable.?bestObjective : - InfinityOriginal Problem(p0.ampl)x5 0q1.ampl(integerfeasible)bestObjective : -4.2x5 1q2.amplx1.val 0.333333333333333x1.val 0x2.valx2.val 0.6666666666666670.5x3.valx3.val 2.666666666666676x4.valx4.val 0 0x5.valx5.val 0.3333333333333331x6.valx6.val 0 0.5OptimalValue:-4.750000Optimal Value:-3.333333

How to select a branch variable? There are heuristics Theof a problem,branch variableis very important.But choiceit is a hardin general. User specifies a variable ordering or priority. There is no single “best heuristic”. Solver heuristics: Often,someexpertisewiththe toproblemdomain Choosefractionalsolutionclosestan integervalue? informs theheuristic. Choose binary (0-1) variables preferentially? Random choice?

BRANCH-AND-BOUNDAt the dictionary level

Thus far Use LP solver as a black box. This lecture: Consider how to fold branch-and-bound in a dictionary setup.Final dictionaryChild # 1BnB Node(Solve LP relaxation)Can I reuse thefinal dictionary?Child # 2

View from the dictionaryxBb···zc0 cN xNFinal dictionaryChild # 1BnB Node(Solve LP relaxation)Claim: Dictionary D’is always infeasible.xj bsj cxBwzb···c0··· cN xN

Proof (Pictorial)x3 2Solution represented bydictionary D and D’x3 3

Example (ILP)var x1 0, 10;var x2 0, 10;var x3 0, 10;maximize obj: x1 x2 -5* x3 ;c1: -2* x1 7 *x2 1;c2: x1 - 2 *x2 5* x3 3;c3: x1 x2 - 3 * x3 7;solve;display x1, x2, x3;end;x4x5x6x7x8x9::::::10 x110 x210 x31 2x1 7x23 x1 2x2 5x37 x1 x2 3x3Slack variables are also integers.

Final Dictionaryx4x5x6x7x1x2zx14.33333333333 0.333333x8 0.666667x9 0.333333x38.666666666670.333333x8 0.333333x9 2.666667x310x333x8 x918x35.666666666670.333333x8 0.666667x9 0.333333x31.33333333333 0.333333x8 0.333333x9 2.666667x37.0 0x8x92x36x10 :6 x1

Dictionary After 5.666666666671.333333333330.333337.0x10 :6 x1 0.333333x8 0.666667x90.333333x8 0.333333x93x80.333333x8 0.333333x80.333333x8 0x8Dictionary becomes primal infeasible.0.333333x32.666667x3x3 x918x30.666667x9 0.333333x30.333333x9 2.666667x30.666667x9 0.333333x3x92x3Back to initialization phaseSimplex?

Dictionary After 5.666666666671.333333333330.333337.0 0.333333x8 0.666667x90.333333x8 0.333333x93x80.333333x8 0.333333x80.333333x8 0x8Dictionary becomes primal infeasible.0.333333x32.666667x3x3 x918x30.666667x9 0.333333x30.333333x9 2.666667x30.666667x9 0.333333x3x92x3Dual Feasible Dictionary!!But not dual final.

How to update after branch?Parent Node(Final Dictionary)add branchconstraintChild Node:1. Add new row.2. Primal Infeasible but Dual FeasibleConsider dual complementdictionary.(Feasible but non-final)Opt. Phase ondual dictionariesFinal dual dictionary LP relaxation(also final primal)solved for childnode!

General Form SimplexParent Node(Final Dictionary)add branchconstraintChild Node:1. Add new row.2. Primal Infeasible but Dual FeasibleConsider dual complementdictionary.(Feasible but non-final)Opt. Phase ondual dictionariesFinal dual dictionary LP relaxation(also final primal)solved for childnode!

General Form Dictionary Give special treatment to bounds on variables.l x u Modify the Simplex algorithm in two ways: Dictionaries now have special ways to track bounds. Pivoting is modified.

Branch-and-Bound with General FormParent Node(Final Dictionary)Simply updateChild Node:variable bound.1. Add new row.2. Primal Infeasible but Dual Feasible

CUTTING PLANEMETHOD

LP Relaxation for ILPOpt. Solution ofLP relaxationOpt. Solution ofILP

Removing a Fractional SolutionBranch and Bound12Cutting Plane Method.

Cutting PlaneHow do we find a cuttingplane?

GOMORY-CHVATALCUTTING PLANEPart 1: Setting up the problem.

ILP in Standard Formmaxs.t.c xAxxx 2b0ZA, b, c are all assumed to be integers.

Conversion to standard from Recap from LP formulations lectures: Equality constraints into two inequalities.0 is missing: Rewrite in case xixi 7! x ixi Convert to by negating both sides. How do we make sure A, b, c are integers?Reasonable assumption: original problem coefficients are rationals.

Integer Coefficients.maxs.t.Scaleconstraints Objectivemaxs.t.2x10.1x10.5x1x1 ,x1 ,2x10.1x10.5x1x1 ,x1 , 0.3x22x22.6x2x2 ,x2 , 0.3x22x22.6x2x2 ,x2 ,0.1x3x3 1.3x3x3x43x0.1x3x3 1.3x3x3x4 2 20.250.150Z 100.25 200.15 1000Z

Conversion to Integer Coefficients.maxs.t.2x10.1x10.5x1x1 ,x1 , 0.3x22x22.6x2x2 ,x2 ,Divide result by 100.1x3x3 1.3x3x3x4 20.250.150Zmax 20x1s.t. 2x150x1x1 ,x1 , 3x2x340x220x3 5260x2 130x3 15x2 ,x30x2 ,x42 Z

Adding Slack Variablesmaxs.t.c xAxxx 2b0Zmaxs.t.c xAx xsx, xsx, xs 2b0Z

Summary We assume problem is in LP standard form. Assume coefficients are rational. ILP standard form: coefficients (A,b,c) are integers. Scale the original rational problem. Make sure that result is divided by scale factor for objective. Advantage of ILP standard form: Slack variables are naturally integers. No need for separate treatment of decision and slack variables.

CUTTING PLANEMETHODPart 2: Gomory-Chvatal Cuts

Overall methodSolve LPrelaxation ofthe problem.Is thesolutionIntegral?Guarantee: Nointeger point is lost.Add a newcutting planeconstraint.NoYesDone.

Cutting Plane Visualization333Second2Optimum2CuttingPlaneFirst optimum10Third2Optimum101230101230012Idea: cutting plane attempts to successively “expose” an integer optimal vertex.3

Cutting Plane Method Deriving the Cutting Plane Gomory-Chvatal Cuts Integrating the method inside Simplex. Using the dual dictionary to avoid initialization phase Simplex.

GOMORY-CHVATAL CUTS

Overall Ideamaxs.t.c xAx xsx, xsx, xsLPRelax 2b0Z1. Solve the LP relaxation using Simplex lDictionary

Final DictionaryxBzb̃z0Optimal solution toILP found!! ÃxN xNNfractcional entriesDerive a cuttingplane

Example: Final Dictionaryx1x4x6z1.23.1x21x22.5 1.3x21.71.2x2 4.3x3 x32.1x32.3x30.5x5x5 x52.1x5x1 1.2, x2 0, x3 0, x4 1, x5 0, x6 2.5

Cutting Plane Derivation: Step 1Step 1Identify row with fractional constant.x1x4x6z1.23.1x21x22.5 1.3x21.71.2x2 4.3x3 x32.1x32.3x30.5x5x5 x52.1x51.2 2 3.1x4.3x0.5x2 3 35 xx11 3.1x4.3x0.5x1.25

Cutting Plane Derivation: Step 2x1 3.1x24.3x3 0.5x5 1.2(x1 3x2 5x3 0x5 ) (0.1x2 0.7x3 0.5x5 ) 1 0.2 {z} {z}AA: integerA B 1.2BB: integer fractionB 0

Claim(x1 3x2 5x3 0x5 ) (0.1x2 0.7x3 0.5x5 ) 1 0.2 Conclusion:{z} {z}ABA1.FractionalpartofBis 0.2A is integer12. B 0.2B has a fractional part. 21.1B 0In other words,4A B 1.21. B – 0.2 is an integer.-32. B - 0.2 0-100BA Yes101.21.2Yes

Cutting Planex1x4x6z1.23.1x21x22.5 1.3x21.71.2x2 4.3x3 x32.1x32.3x30.5x5x5 x52.1x5Cutting Plane:0.1x2 0.7x3 0.5x50.2

Cutting Plane: Definition.xB1FinalDictionary(LP Relax) .b1xBk .bkxBmz bmc0 ··· a1j xIj ak1 xI1 ··· am1 xI1 c1 xI1 ··· ··· a11 xI1 ··· a1n xIn akj xIj ··· akn xIn amj xIj cj xIj ··· ··· amn xIn cn xInCutting Planefrac( ak1 )xI1 · · · frac( akn )xInfrac(x) xbxcfrac(bk )bk 62 Z

bk 62 ZCuttingPlanexB1 .b1 a11 xI1 ··· a1j xIj ··· a1n xInxBk .bk ak1 xI1 ··· akj xIj ··· akn xInxBmz bmc0 am1 xI1 c1 xI1 ··· ··· amj xIj cj xIj ··· ··· amn xIn cn xInfrac( ak1 )xI1 · · · frac( akn )xInfrac(bk )Claim: Every (integer) feasible point of the ILP satisfies thecutting plane constraint.

We havexBk nX( akj )xIj bkj 1Sinceakjb akj c and xIjnXnX( akj )xIjj 1b akj cxIjApplying this to Eq.(1) we obtain:xBk ( akj )xIjxBk nXj 1j 1Therefore, we getbkxBk nXj 1b akj cxIjb akj cxIj(2)(3)The RHS of (3) is an integer, therefore, we conclude:bbk c .b1 a11 xI1 ··· a1j xIj ··· a1n xInxBk .bk ak1 xI1 ··· akj xIj ··· akn xInxBmz bmc0 am1 xI1 c1 xI1 ··· ··· amj xIj cj xIj ··· ··· amn xIn cn xIn0, we obtainj 1nXxB1(1)xBk nXj 1b akj cxIjCombining (4) with (1), we have,Pnbk bbk c j 1 ( akj b akj c)xIjPnIn other words, j 1 frac( akj )xIj frac(bk )(4)bk 62 Z

Examplex1x4x6z1.23.1x21x22.5 1.3x21.71.2x2 4.3x3 x32.1x32.3x30.7x2 0.1x3 0x50.2x2 0.3x3 0.1x50.5x5x5 x52.1x50.50.7

CUTTING PLANEMETHODUpdating the dictionarySetup for subsequent iterations.

Overall methodSolve LPrelaxation ofthe problem.Is thesolutionIntegral?Guarantee: Nointeger point is lost.Add a newcutting planeconstraint.NoYesDone.

Cutting Plane Examplex1x4x6z1.23.1x21x22.5 1.3x21.71.2x2 4.3x3 x32.1x32.3x30.5x5x5 x52.1x5Cutting Plane:0.1x2 0.7x3 0.5x50.2

Adding cutting plane to dictionaryx1x4x6z1.212.51.73.1x2x2 1.3x21.2x2 4.3x3 x32.1x32.3x30.1x2 0.7x3 0.5x5x1x4x6w1z1.212.50.21.73.1x2x2 1.3x2 0.1x21.2x2 4.3x3 x32.1x3 0.7x32.3x30.5x5x5 x5 0.5x52.1x50.5x5x5 x52.1x50.2

Cutting Plane Method Claim: Resulting dictionary after adding cutting plane is primalinfeasible.Cutting PlaneDictionarySolution

Cutting Plane: Examplex1x4x6w1z1.212.50.21.73.1x2x2 1.3x2 0.1x21.2x2 4.3x3 x32.1x3 0.7x32.3x30.5x5x5 x5 0.5x52.1x5Naïve Approach: Re-solve initialization phase Simplex.Dual dictionaryis feasible butnon-final.

Cutting Plane: Solving again after cut.Also final for primalFinal DictionaryLP relaxation.CutPrimal InfeasibleDual FeasibleFinal dictionaryfor DualOptimize thedual problemdictionary.

Original Problem Original Problem Constr. ( x 3 2 ) Original Problem Constr. ( x 3 3 ) b1 b2 . Visualization x 3 2 x 3 3 . Branch-and-Bound Original Problem (LP Relaxation) Orig. Problem x j b s j c Orig. Problem x j ds j e P1 P2 P0 Non Integral Solution x j: s j Orig. Problem x j bs j c x k bt k c