Address 10: Integer Programming Branch-and-Bound

Lecture 10 integer programming branch and bound l.jpg
1 / 31
0
0
1018 days ago, 519 views
PowerPoint PPT Presentation

Presentation Transcript

Slide 1

Address 10: Integer Programming & Branch-and-Bound © J. Christopher Beck 2005

Slide 2

Outline Quick scientific programming survey Disjunctive chart Disjunctive programming definition Example 5.3.1 Branch-and-bound Example B.4.1 Note: Some slides taken from see content CD (Iowa State, Amsterdam) © J. Christopher Beck 2005

Slide 3

Review of Mathematical Programming Many planning issues can be defined as numerical projects: Linear Programming Integer Programming See Appendix An in book. © J. Christopher Beck 2005

Slide 4

Linear Programs Minimize subject to © J. Christopher Beck 2005

Slide 5

Solving LPs can be explained productively Simplex strategy (1950s) Interior point techniques (1970s) Polynomial time Has been utilized as a part of practice to take care of colossal issues © J. Christopher Beck 2005

Slide 6

Integer Programming LP where all factors must be number Mixed-whole number programming (MIP) Much more troublesome than LP Most valuable for planning © J. Christopher Beck 2005

Slide 7

Example: Single Machine One machine and n employments Minimize Define the choice factors © J. Christopher Beck 2005

Slide 8

End time of occupation j "Time-ordered" definition – one approach to show a booking issues as a MIP IP Formulation Minimize subject to All exercises begin once Jobs can't cover © J. Christopher Beck 2005

Slide 9

Solving IPs Branch-and-bound strategies Branch on the choice factors Linear programming unwinding gives limits There are different techniques however we will concentrate on B&B We will return to B&B later in the address © J. Christopher Beck 2005

Slide 10

Disjunctive Graph Formulation An option MIP detailing from the time-recorded one Each occupation takes after a given course Picture each employment as a line of hubs : (i,j)=operation on machine i of employment j (1,1) (2,1) (3,1) Conjunctive bends Source (1,2) (2,2) (4,2) Sink (2,3) (1,3) (4,3) (3,3) © J. Christopher Beck 2005

Slide 11

Disjunctive circular segments Graph Representation To display the machines, present the bend set B (...), giving 'an inner circle' of bidirected curve matches on each machine Full Graph G(N, A  B) (1,1) (2,1) (3,1) Conjunctive circular segments Source (1,2) (2,2) (4,2) Sink (2,3) (1,3) (4,3) (3,3) © J. Christopher Beck 2005

Slide 12

Solving the Problem Select one curve from each disjunctive combine (1,1) (2,1) (3,1) Source (1,2) (2,2) (4,2) Sink (2,3) (1,3) (4,3) (3,3) © J. Christopher Beck 2005

Slide 13

Feasibility of the Schedule Are all choices attainable? Coming about diagram must be non-cyclic (1,1) (2,1) (3,1) Source (1,2) (2,2) (4,2) Sink (2,3) (1,3) (4,3) (3,3) © J. Christopher Beck 2005

Slide 14

Conjunctive versus Disjunctive Conjunctive All imperatives must be fulfilled "AND" In JSP they originate from the occupation routings Disjunctive At slightest one of the limitations must be fulfilled "OR" In JSP they originate from the machine use © J. Christopher Beck 2005

Slide 15

Disjunctive Programming Idea Formulate an Integer Program in view of the disjunctive diagram and utilize standard IP arrangement strategies (e.g., B&B) to illuminate it How would we figure a JSP as a disjunctive program? Accept target is to limit makespan (i.e., min C max ) © J. Christopher Beck 2005

Slide 16

Notation N – set of all operations A – set of every single conjunctive limitation B – set of every disjunctive imperative y ij – beginning time of operation (i, j) (i,j)=operation on machine i of occupation j © J. Christopher Beck 2005

Slide 17

Disjunctive Programming Formulation Minimize C max s.t. © J. Christopher Beck 2005

Slide 18

Disjunctive Programming Formulation Minimize C max s.t. All operations must end before makespan © J. Christopher Beck 2005

Slide 19

Disjunctive Programming Formulation Minimize C max s.t. An operation can't begin before the past operation (in the occupation) closes © J. Christopher Beck 2005

Slide 20

Disjunctive Programming Formulation Minimize C max s.t. One disjunctive circular segment must be picked © J. Christopher Beck 2005

Slide 21

Disjunctive Programming Formulation Minimize C max s.t. Begin times can't be negative © J. Christopher Beck 2005

Slide 22

Disjunctive Programming Formulation See Example 5.3.1 You ought to have the capacity to make a disjunctive programming definition for a given JSP case © J. Christopher Beck 2005

Slide 23

OK, now what? Either the time-recorded or the disjunctive definition So we have an IP detailing of the issue, how would we fathom it? Utilizing standard IP arrangement procedures, for example, branch-and-bound Doesn't mean the issue is simple Will now discuss branch-and-bound (B&B) which can be utilized to tackle IPs and other difficult issues © J. Christopher Beck 2005

Slide 24

Branch-and-Bound Idea Systematically look through conceivable variable qualities Use heuristics to pick a choice to attempt ("branch") Use bring down limits on answers for "bound" the pursuit Creates an inquiry tree © J. Christopher Beck 2005

Slide 25

Branch a = 0 a = 1 b = 0 b = 1 b = 0 b = 1 c = 0 c = 1 c = 0 c = 1 c = 0 c = 1 c = 0 c = 1 B&B Search Tree: Branching Imagine an issue with 3 factors a, b, c є {0, 1} 100 90 110 115 80 90 100 110 © J. Christopher Beck 2005

Slide 26

a = 0 a = 1 b = 0 b = 1 b = 0 c = 0 c = 1 c = 0 Bound B&B Search Tree: Bounding Imagine I have an approach to figure a lower bound on the cost at every hub 50 70 80 85 95 80 100 90 80 © J. Christopher Beck 2005

Slide 27

B&B Branch: dole out a heuristic incentive to a variable Creates two subproblems Bound: contrast bring down bound best case scenario known arrangement If LB > best, you can backtrack immediately © J. Christopher Beck 2005

Slide 28

B&B for IP Usually bring down bound is found by unraveling the direct unwinding of the IP LP shaped by disregarding basic limitations Branch on one of the whole number factors with a non-number an incentive to be: more noteworthy than or equivalent to the following most elevated number, or Less than or equivalent to the following least whole number © J. Christopher Beck 2005

Slide 29

End time of employment j IP Formulation Minimize subject to All exercises begin once Jobs can't cover © J. Christopher Beck 2005

Slide 30

x i ≤ floor(r) x i ≥ ceil(r) x k ≤ floor(s) B&B for IP … Solve LP to give cost LB If arrangement in non-whole number, pick x i = (r in non-number) Branch on x i Repeat at next hub © J. Christopher Beck 2005

Slide 31

B&B is Important! We will take a gander at it again in the following address! You ought to comprehend Sections B.3 and B.4 (in Appendix B) © J. Christopher Beck 2005

SPONSORS