Transcript PPT

Constrained Integer Network
Flows
April 25, 2002
Constrained Integer Network Flows
• Traditional Network Problems With
Side-Constraints and Integrality
Requirements
• Motivated By Applications in Diverse
Fields, Including:
– Military Mission-Planning
– Logistics
– Telecommunications
Minimum-Cost Network Flows
• Definition
– Minimize Flow Cost
– b Represents
Demands and
Supplies
– Special Properties
• Spanning Tree Basis
• A Is Totally Unimodular
• Integer Solutions if b, l,
and u Are Integer
• Row Rank of A Is |V|-1
Minimize:
cx
Subject To:
Ax  b
x
xu
MCNF
• Special Structure
Has Lead To Highly
Efficient Algorithms
Shortest-Path Problems
• One-to-One (SP)
– Find Shortest-Path
From s To t
– b = et - es
• One-to-All (ASP)
– Find Shortest-path
From s To All Other
Vertices
– b = 1 - |V|es
Minimize:
cx
subject to:
Ax  b
x0
SP/ ASP
• Special Solution
Algorithms
– Label Setting
– Label Correcting
Resource-Constrained Shortest Path
• Find Shortest Path
From s To t Limited
By Constraint on a
Resource
• Side-Constraint
Destroys Special
Structure of MCNF
Minimize:
cx
subject to:
Ax  b
sx  q
xij  B, (i, j )  E
RCSP
• Solutions NonInteger Unless
Integrality Enforced
RCSP: Aircraft Routing
• Time-Critical-Target Available For
Certain Time Period
• Aircraft Need To Be Diverted To Target
• Planners Wish To Minimize Threats
Encountered by Aircraft
• Multiple Aircraft ( 100s or 1000s )
Considered for Diversion
RCSP: Aircraft Routing
• Grid Network
Representation
• Arc Cost: Threat
• Arc Side-Constraint
Value: Time
• Total Time, Including
Decision Making, Is
Constrained
(0,10)
(10,10)
Target
Point 2
Threat
Values
20
30
40
50
Point 1
(0,0)
(10,0)
*Diagonal Arcs Are Included, But Not Shown
Multicommodity Network Flow
• Minimize Cost of
Flows For All
Commodities
• Total Flow for All
Commodities on Arcs
Is Restricted
• Non-Integer Solutions
• Solution Strategies
– Primal Partitioning
Minimize:
 cx
k
kK
subject to:
Ax k  b k , k  K
x
k
ij
  ij , (i, j )  E
x
k
ij
 uij , (i, j )  E
k K
k K
xijk  0, (i, j )  E , k  K
MCF
– Price & Resource
Directive
Decompositions
– Heuristics
Origin-Destination Integer MCF
• Specialization of MCF
– One Origin & One Destination Per
Commodity
– Commodity Flow Follows a Single Path
• Integer-Programming Problem
• Two Formulations
– Node-Arc
– Path-Based
Origin-Destination Integer MCF
Minimize:
 q cx
k
k
Minimize:
Ax k  b k , k  K
q
kK
k
x  uij , (i,j)  E
k
ij
xijk  B, (i, j )  E ,
k  K
ODIMCF1
• ODIMCF1: Node-Arc
Formulation
• Rows: |V||K| + |E|
• Variables: |K||E|
k
p
 q 
ij
k
kK
kK
subject to:
q c
subject to:
pP ( k )
k
kK
y
pP ( k )
pP ( k )
k
p
y kp
p
y kp  uij , (i, j )  E
 1, k  K
y kp  B, k  K ,
p  P (k )
ODIMCF2
• ODIMCF2: Path-Based
Formulation
• Rows: |K| + |E|
• Variables: Dependent on
Network Structure
ODIMCF: Rail-Car Movement
• Grain-Cars Are “Blocked” for Movement
• Blocks Move From Origin To Destination
through Intermediate Stations
• Grain-Trains Limited on Total Length
and Weight
• Blocks Need To Reach Destinations
ASAP
ODIMCF: Rail-Car Movement
• Arcs - Catching a Train or Remaining at
a Station
• Vertex - Station+Train Arrival/Departure
Stations
A
Remain at A
a1
a2
a3
a4
Catch a Train
B
b1
C
c1
b2
c2
b3
c3
b4
Time
b5
c4
ODIMCF: MPLS Networks
• Traffic Is Grouped by Origin-Destination
Pair
• Each Group Moves Across the Network
on a Label-Switched Path (LSP)
• LSPs Need Not Be Shortest-Paths
• MPLS’s Objective Is Improved Reliability,
Lower Congestion, & Meeting Quality-ofService (QoS) Guarantees
ODIMCF: MPLS Networks
MPLS Switches
LSP
LSR
LSR
IP Net
IP Net
LSR
LSR: Label-Switch Router
LSR
MPLS Network
Binary MCF
• MCF Specialization
– xk Binary
– l=0
– bk = et - es
• ODIMCF Variant
– qk = 1 for all k
Minimize:
 cx
k
kK
subject to:
Ax k  b k , k  K
x
k K
k
ij
 uij , (i, j )  E
xijk  B, (i, j )  E , k  K
BMCF
Current & Proposed Algorithmic
Approaches
RCSP: Current Algorithms
• Lagrangian Relaxation, RRCSP()
– Lagrangian 1
• Network Reduction
Techniques
• Use Subgradient
Optimization To Find
Lower Bound
• Tree Search to Build
a Path
Minimize:
cx   (sx  q )
subject to:
Ax  b
xij  0, (i, j )  E
RRCSP()
– Lagrangian 2
• Bracket Optimal
Solution Changing 
• Finish Off With kshortest Paths
RCSP: Proposed Algorithm
• Objectives
– Solve RCSP For
One Origin, s, and
Many Destinations, T
– Reduce Cumulative
Solution Time
Compared To
Current Strategies
• Overview
– Solves Relaxation
(ASP())
– Relaxation Costs Are
Convex Combination
of c and s
– ASP() Solved
Predetermined
Number of Times
RCSP: Proposed Algorithm
• Algorithm
– Relax SideConstraint Forming
ASP()
Minimize:
((1   )c  s)x
subject to:
Ax  b
xij  0, (i, j )  E
ASP()
• ASP With s As Origin
– Select n Values for 
• 01
– Solve ASP() For
Each Value of 
– For Each t in T Find
Smallest  Meeting
Side-Constraint For t
RCSP: Proposed Algorithm
(0,10)
• Aircraft Routing
Example
– c - Threat on Arcs
– s - Time To Traverse
Arcs
– 10 Values for 
Evaluated
– Results Recorded
For 2 Points And
Target
(10,10)
Target
Point 2
Threat
Values
20
30
40
50
Point 1
(0,0)
Value
of

0.00
0.11
0.22
0.33
0.44
0.56
0.67
0.78
0.89
1.00
Point 1
Accum
Accum
Time
Threat
23.0
0
23.0
0
23.0
0
15.8
880
15.8
880
15.8
880
15.8
880
15.0
1680
13.2
4640
12.6
11480
(10,0)
Point 2
Accum
Accum
Time
Threat
24.8
0
24.8
0
11.4
880
9.8
1200
9.8
1200
9.8
1200
9.8
1200
9.8
1200
9.0
2800
9.0
2800
Accumulated Time and Distance For
Each Value of 
RCSP: Proposed Algorithm
(0,10)
(0,10)
(10,10)
Target
Target
Point 2
(10,10)
Threat
Values
Point 2
Threat
Values
20
30
40
50
20
30
40
50
Point 1
Point 1
(0,0)
(10,0)
Minimum Threat Routing
 = 0.0
(0,0)
(10,0)
Intermediate Routing Option
 = 0.44
RCSP: Proposed Algorithm
12000
(0,10)
(10,10)
Point 2
Threat
Values
20
30
40
50
Accumulated Threat
10000
Target
8000
6000
4000
2000
0
80
Point 1
130
180
230
Accum ulated Tim e
(0,0)
(10,0)
Minimum Time Routing
 = 1.0
Point 1
Point 2
Accumulated Threat
vs
Time To Target
280
RCSP: Proposed Algorithm
• Further Considerations
– Normalization of c and s
– Reoptimization of ASP()
– Number of Iterations (Values of )
– Usage As Starting Solution For RCSP
– Other Uses
ODIMCF: Current Algorithms
• Techniques For Generic Binary IP
• Branch-and-Price-and-Cut
– Designed Specifically For ODIMCF
– Incorporates
• Path-Based Formulation (ODIMCF2)
• LP Relaxations With Price-Directive
Decomposition
• Branch-and-Bound
• Cutting Planes
ODIMCF: Current Algorithms
• Branch-and-Priceand-Cut (cont.)
– Algorithmic Steps
• Solve LP Relaxation
At Each Node Using:
– Column-Generation
» Pricing Done
As SP
– Lifted-Cover
Inequalities
• Branch By Forbidding
a Set of Arcs For a
Commodity
– Select Commodity k
– Find Vertex d At
Which Flow Splits
– Create 2 Nodes in
Tree Each
Forbidding ~Half
the Arcs at d
– Has Difficulty
• Many Commodities
• |A|/|V|  ~2
ODIMCF: Proposed Algorithm
• Heuristic Based On Market Prices
• Circumstances
– Large Sparse Networks
– Many Commodities
– Arcs Capable of Supporting Multiple
Commodities
ODIMCF: Proposed Algorithm
• Arc Costs, cij´ = f(rij, uij, cij, qk)R
– Uses Non-Linear Price Curve, p(z, uij) R
– Based On
•
•
•
•
Original Arc Cost, cij
Upper Bound, uij
Current Capacity Usage, rij
Demand of Commodity, qk
ODIMCF: Proposed Algorithm
c´ij = f(rij, uij, cij, qk) As an Area
(Percentage of Original)
Marginal Arc Cost
1200%
1000%
p(z, uij)
800%
600%
Current Usage, rij
Demand, qk
400%
200%
0%
70%
Area = Arc Cost, c´ij
Marginal Arc Cost
80%
90%
100%
110%
z : Arc Capacity Usage
(Percentage of Upper Bound)
120%
130%
Upper Bound, uij
ODIMCF: Proposed Algorithm
(Percentage of Original)
Marginal Arc Cost
1200%
Arc Cost For Increasing rij
1000%
800%
600%
400%
200%
0%
70%
80%
90%
100%
z : Arc Capacity Usage
(Percentage of Upper Bound)
110%
120%
ODIMCF: Proposed Algorithm
Total System Cost
(Percentage of Original)
Marginal Arc Cost
1200%
1000%
800%
600%
Additional Cost To
Other Commodities
Total Additional
System Cost
Arc Cost To
Commodity
400%
200%
0%
70%
80%
Current System Cost
90%
100%
z : Arc Capacity Usage
(Percentage of Upper Bound)
110%
Current
Usage, rij 120%
ODIMCF: Proposed Algorithm
• Basic Algorithm
– Initial SP Solutions
– Update r
– Until Stopping
Criteria Met
• Randomly Choose k
• Calculate New Arc
Costs
• Solve SP
• Update r
• Selection Strategy
– Iterative
– Randomized
• Infeasible Intermediate Solutions
• Stopping Criteria
– Feasible
– Quality
– Iteration Limit
ODIMCF: Proposed Algorithm
4
• Considerations
– Form of p(z, uij)
– Commodity
Differentiation
Marginal Arc Cost
(Percentage of Original)
600%
• Under-Capacitated Net
• Preferential Routing
– Selection Strategy
– Advanced Start
3
2
500%
400%
1
300%
200%
0
100%
0%
88%
93%
98%
103%
z : Arc Capacity Usage
(Percentage of Upper Bound)
– Cooling Off of p(z, uij)
• Step 0 - SP
• Steps 1… Increasing
Enforcement of u
ODIMCF: Proposed Algorithm
Problem
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Vertices Arcs
25
50
25
50
25
100
25
100
50
100
50
100
50
200
50
200
100
200
100
200
100
400
100
400
200
400
200
400
200
800
200
800
CommoTotal
Geometrice
Geometric Mean
dities
Capacity Mean of Arc UB
of Demands
30
1,783
31.72
8.53
60
3,709
67.09
8.86
30
1,554
13.62
9.00
60
2,312
21.28
8.91
123
8,470
78.00
9.15
245
15,391
143.98
8.75
123
5,985
27.83
8.94
245
11,180
52.46
8.86
495
40,146
188.36
9.14
990
79,226
373.07
8.87
495
26,016
61.68
8.84
990
52,107
123.84
8.96
1,990 191,409
450.18
8.95
3,980 379,380
893.11
8.78
1,990 123,705
146.46
9.06
3,980 238,767
282.35
8.99
ODIMCF: Proposed Algorithm
Problem
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Objective
Value
73,770
149,074
Percent
Avg
Median
Utilization Utilization Utilization Avg Hops
69.2%
58.1%
70.7%
4.30
69.3%
59.9%
67.0%
4.28
341,129
648,538
71.6%
74.5%
66.5%
69.7%
77.2%
77.2%
5.05
4.73
365,695
1,665,958
3,218,316
914,655
1,846,896
7,721,548
15,131,327
4,377,348
8,310,650
67.0%
75.2%
73.5%
69.0%
70.1%
73.1%
72.7%
68.6%
68.2%
64.0%
71.6%
69.9%
66.0%
67.6%
69.0%
68.8%
65.5%
65.4%
70.0%
80.0%
73.4%
74.0%
75.9%
73.0%
74.1%
72.7%
68.8%
3.01
5.94
5.94
3.69
3.66
7.00
7.01
4.16
4.08
Time
0.04
0.01
0.08
0.18
0.52
0.10
1.50
0.31
0.58
1.48
1.83
2.74
11.97
34.00
15.43
45.67
ODIMCF: Proposed Algorithm
Problem
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Solution Values
Algorithm
SP
73,770
65,691
149,074
135,746
41,925
68,154
341,129
310,324
648,538
596,083
155,134
365,695
297,042
1,665,958
1,574,431
3,218,316
3,134,172
914,655
744,239
1,846,896
1,540,285
7,721,548
7,390,720
15,131,327 14,564,093
4,377,348
3,685,457
8,310,650
7,273,759
Gap
12.3%
9.8%
9.9%
8.8%
23.1%
5.8%
2.7%
22.9%
19.9%
4.5%
3.9%
18.8%
14.3%
Infeasibility of SP
Infeasible Arcs
Total Violation
Count
Percent
Value
Percent
7
14.0%
41
2.3%
4
8.0%
158
4.3%
20
20.0%
198
12.7%
18
18.0%
281
12.2%
20
20.0%
842
9.9%
22
22.0%
1,163
7.6%
49
24.5%
1,144
19.1%
44
22.0%
1,679
15.0%
41
20.5%
2,921
7.3%
34
17.0%
4,193
5.3%
97
24.3%
5,026
19.3%
107
26.8%
11,029
21.2%
83
20.8%
15,525
8.1%
86
21.5%
31,901
8.4%
203
25.4%
27,365
22.1%
206
25.8%
52,329
21.9%
ODIMCF: Proposed Algorithm
Problem
1*
2*
3*
4*
5
6
7
8
9
10
11
12
13
14
15
16
CPLEX
Nodes
Cuts
11
16
0
10
0
48
22
162
Time
0.23
0.25
0.20
40.10
1.53
5.68
23.20
38.27
71.97
Out of Memory
1277.53
Out of Memory
Out of Memory
Out of Memory
Out of Memory
Out of Memory
Value
72,810
140,688
59,959
81,739
328,529
620,861
172,233
326,168
1,611,888
809,429
Algorithm
Value
Gap
73,770
1.3%
149,074
6.0%
341,129
648,538
3.8%
4.5%
365,695
1,665,958
3,218,316
914,655
1,846,896
7,721,548
15,131,327
4,377,348
8,310,650
12.1%
3.4%
13.0%
SP
Value
65,691
135,746
41,925
68,154
310,324
596,083
155,134
297,042
1,574,431
3,134,172
744,239
1,540,285
7,390,720
14,564,093
3,685,457
7,273,759
Gap
10.8%
3.6%
43.0%
19.9%
5.9%
4.2%
11.0%
9.8%
2.4%
8.8%
*CPLEX65 Used MIP To Find Integer Solution. All Other Problems Solved As LP
Relaxations With No Attempt At Integer Solution.
BMCF: Proposed Algorithm
• Modification of Proposed Algorithm For
ODIMCF
• Commodities Are Aggregated By Origin
– A is the Set of Aggregations
• Pure Network Sub-Problems Replace
SPs of ODIMCF
BMCF: Proposed Algorithm
Commodity
1
2
3
4
5
6
Origin
1
1
1
3
3
4
Dest
3
2
3
4
1
2
• Original
Commodities
– Demands of 1
– Single Origin &
Destination
– SP
Aggregation
1
Origin
Dest
1
2
3
3
4
3
2
1
4
2
Demand
qa
2
1
1
1
1
• Aggregations
–
–
–
–
Demands  1
Single Origin
Multiple Destinations
MCNF
BMCF: Proposed Algorithm
• Aggregation MCNFs
Solved On Modified
Network
– Each Original Arc Is
Replaced With qa
Parallel Arcs
– Parallel Arcs Have
• Convex Costs
Derived From p(z, uij)
• Upper Bounds of 1
i
cij
(0 , uij)
j
cij3
(0 , 1)
i
cij2
(0 , 1)
cij1
(0 , 1)
j
BMCF: Proposed Algorithm
Parallel Arc Costs
(Percentage of Original)
Marginal Arc Cost
1200%
1000%
Demand,
800%
qa =
p(z, uij)
3
600%
Current Usage, rij
cij3
400%
cij2
200%
0%
70%
cij1
80%
90%
100%
110%
z : Arc Capacity Usage
One Unit of Flow
(Percentage of Upper Bound)
120%
130%
Upper Bound, uij
BMCF: Proposed Algorithm
• Basic Algorithm
–
–
–
–
Form Aggregates
Solve Initial MCNFs
Update r
Until Stopping
Criteria Met
•
•
•
•
•
Randomly Choose a
Create Parallel Arcs
Calculate Arc Costs
Solve MCNF
Update r
• Considerations
– ODIMCF
Considerations
– ODIMCF vs BMCF
– Aggregation Strategy
• Multiple Aggregations
per Vertex
• Which Commodities
To Group
Expected Contributions
• Will Address Important Problems With
Wide Range of Applications
• Efficient Algorithms Will Have a
Significant Impact in Several Disparate
Fields
Notation
•
•
•
•
•
A - Matrix
x - Vector
0 - Vector of All 0’s
1 - Vector of All 1’s
ei - 0 With a 1 at ith
Position
• xi - ith element of x
• x - Scalar
•
•
•
•
•
•
A - Set
|A| - Cardinality of A
 - Empty Set
R - Set of Reals
B - {0,1}, Binary Set
Rmxn - Set of mxn Real
Matrices
• Bm - Set of Binary, m
Dimensional Vectors
Notation: Networks
• A - Node-Arc
Incidence Matrix
• x - Arc Flow Variables
• c - Arc Costs
• s - Arc Resource
Constraint Values
• u - Arc Upper Bounds
• l - Arc Lower Bounds
• b - Demand Vector
• All Networks Are
Directed
• xij Is the Flow
Variable for ( i, j )
• E - Set of Arcs
• V - Set of Vertices
i
cij , sij
(l ij , uij)
j
Notation: Problem Abbreviations
• MCNF - MinimumCost Network Flow
• SP - Shortest Path
• ASP - One-To-All
Shortest-Path
• RCSP - Resource
Constrained
Shortest-Path
• MCF - Multicommodity Flow
• ODIMCF - Origin
Destination Integer
Multicommodity
Network Flow
• BMCF - Binary
Multicommodity
Network Flow