Column Generation for WDM Optical Network Design phần 2 ppsx

Column Generation – main steps

Solve restricted

master problem

For all

commodities

(s, d)

Using costs computed in the

previous 2 steps, find the shortest

path for commodity (s, d)

Compute Pz,(s,d) for all z already

in the model

Length of SP <

w(s,d)?

Any new lightpaths

used in the SP?

Add new flow path

variables

Add new lps and

corresponding constraints

Reduced cost

nonnegative for

all commodities?

LP solved

Compute Pz,(s,d) for all z not in

the model by solving the all-pair

SP problem

Yes

Yes

Yes

No

No

No