Transcript i , j

Hard Optimization
Problems: Practical
Approach
DORIT RON
Tel. 08 934 2141
Ziskind room #303
[email protected]
Course outline
 1st lecture: Introduction and motivation
INTRODUCTION
 What is an optimization problem?
An optimization problem consist of:
 Variables:
x  ( x1, x 2,..., xn )
 Energy functional to be minimized/maximized:
min / max E (x )
Unconstrained minimization
Find the global minimum
An optimization problem consist of:
 Variables:
x  ( x1, x 2,..., xn )
 Energy functional to minimized/maximized:
min / max E (x )
Possibly subject to:
 Equality constraints:
fi ( x)  0,
i  1,..., m
 Inequality constraints:
fi ( x)  0,
i  1,..., p
Constrained minimization
subject to
x  0, y  0
INTRODUCTION
 What is an optimization problem?
 Examples
Example 1: 2D Ising spins
 Discrete (combinatorial) optimization
min -S <i,j> si sj
si = { +1 , -1}
+
+
+
-
+
+
+
+
+
-
+
+
+
+
+
+
-
+
+
+
+
+
+
-
- - + + - - - - - +
+ + - - - - +
+ - + +
+ + + +
- + + -
3D Ising model
 Each spin represents a tiny magnet
 The spins tend to align below a certain Tc
 Ferromagnet – Iron at room temperature
magnet
------ Tc------
non-magnet
----|------------------------|---------------------------|--> T
room temp
ferromagnetism
melting
770oC
1538oC
 At T=0 the system settles at its ground states
Example 2: 1D graph ordering
 Given a graph G=(V,E), find a
permutation  of the vertices that minimizes
E()=  i j wi j | (i) -(j) |p
where i , j are in V and wi j is the edge
weight between i and j (wi j =0 if ij is not in E)
 p=1 : Linear arrangement
 p=2 : Quadratic energy
 p=  : The Bandwidth
Minimum Linear Arrangement Problem
i
wij
j
Minimum Linear Arrangement Problem
i
1
2
j
wij
3
4
5
Minimum Linear Arrangement Problem
i
j
wij

 (i )  2
 ( j)  4
1
2
3
4
5
Minimum Linear Arrangement Problem
i
j
wij

 (i )  2
 ( j)  4
1
wij
2
3
4
5
Minimum Linear Arrangement Problem
i
j
wij

 (i )  2
 ( j)  4
1
wij
2
minimize over all  :
3
4
5
E ( ) =
w
ij
i, j
 (i )   ( j )
Minimum Linear Arrangement Problem
j
wij
i

 (i )  2
 ( j)  4
1
wij
2
minimize over all  :
3
4
5
E ( ) =
w
ij
i, j
E ( )  9
 (i )   ( j )
General Linear Arrangement Problem
 Variable nodes sizes
i
j
xi
xj
E(x)=  i j wi j | xi -xj |p
xi = vi /2 + k:(k)<(i) vk
Other graph ordering problems
 Minimize various functionals:
envelope size, cutwidth, profile of graph, etc.
 Traveling salesman problem – TSP
The Traveling Salesman Problem
The Traveling Salesman Problem
Other graph ordering problems
 Minimize various functionals:
envelope size, cutwidth, profile of graph, etc.
 Traveling salesman problem – TSP
 Graph bisectioning
 Graph partitioning
 Graph coloring
 Graph drawing
Drawing Graphs
Drawing Graphs
Drawing Graphs
Example 3: 2D circuit placement
 Bottleneck in the microchip industry
 Given a hypergraph, find the discrete
placement of each module (gate) while
minimizing the wirelength
The hypergraph for a microchip
Placement on a grid of pins
Placement on a grid of pins
Routing over the placement
Example 3: 2D circuit placement
 Bottleneck in the microchip industry
 Given a hypergraph, find the discrete
placement of each module (gate) while
minimizing the wirelength
 No overlap is allowed
 No overflow is allowed
 Critical paths must be shorter
 Leave white space for routing
 Typical IBM chip ~270 meters on 1cm2
Place and route
Exponential growth of transistors for Intel processors
INTRODUCTION
 What is an optimization problem?
 Examples
 Summary of difficulties
Difficulties:
 Many variables: 106 , 107 …
 Many constraints: 106 , 107 …
 Multitude of local optima
 Discrete nature
 Conflicting objectives
 Reasonable running time
INTRODUCTION




What is an optimization problem?
Examples
Summary of difficulties
Is the global optimum really
needed / obtainable?
PEKO=PLACEMENT EXAMPLE
WITH KNOWN OPTIMUM
 Place the nodes – this is the solution
 Create the net list locally and compactly
 The optimum wire length – the sum of all the
edges between the nodes, is known and can
be proven to be minimal
SOLUTION QUALITY
INTRODUCTION




What is an optimization problem?
Examples
Summary of difficulties
Is the global optimum really
needed / obtainable?
 What is expected of a “good approximate”
solution?
“Good approximate” solution
 As optimal as possible:
high quality solution
 Achievable in linear time
 Scalable in the problem size
RUNTIME
Reality Check
NP-Complete
Intractable
Problems
HEURISTICS
Rigorous
Optimization
Theorems
LIMITED
Industrial
Need for
FAST & GOOD
INTRODUCTION




What is an optimization problem?
Examples
Summary of difficulties
Is the global optimum really
needed / obtainable?
 What is expected of a “good approximate”
solution?
 Multilevel philosophy
MULTILEVEL APPROACH
 PARTIAL DIFFERENTIAL EQUATIONS
(Achi Brandt since the early 70’s)
 STATISTICAL PHYSICS
 CHEMISTRY
 IMAGE SEGMENTATION
 TOMOGRAPHY
 GRAPH OPTIMIZATION PROBLEMS
SOLUTION QUALITY
SOLUTION QUALITY
ORIGINAL PICTURE
ORIGINAL
FENG SHUI (1)
KRAFTWERK
CAPO
FENG SHUI (2)
DRAGON
mPL
OURS
OUR PLACEMENT
Course outline
 1st lecture: Introduction and motivation
 2nd – 4th : Local processing (relaxation)
Quadratic minimization, Newton’s method, Steepest descent, Line search,
Lagrange multipliers, Active set approach, Linear programming
 4th – 5th
: Global approaches
Simulated annealing, Genetic algorithms, Spectral method




6th
7th
8th
9th – 12th
:
:
:
:
Classical geometric multigrid
Algebraic multilevel
Graph coarsening
Advanced multilevel topics