IE 515
Discrete Optimization
Lecture 09: Enumerative Algorithms
Dynamic Programming
• The Shortest Path Problem: Given a
digraph ! = (!, !), two distinguished
nodes !, ! ∈ !, and nonnegative arc
costs !!" for !, ! ∈ !, find a minimum
cost ! − ! path
• If the shortest path from s to t passes by node
p, the subpaths (s,p) and (p,t) are shortest
paths from s to p, and p to t respectively
The Shortest Path
Problem
• Can we use this idea to find a shortest path?
The Shortest Path
Problem
• Let d(v) denote the length of a shortest path
from s to v.
• Observe that ! ! = min !
! ! + !!"
!∈! !
• In words, if I know the length of the shortest
paths from s to every neighbor of v, I can find
the length of a shortest path to v.
• Cycles can be a problem, otherwise an O(m)
algorithm is apparent.
The Shortest Path
Problem
• For arbitrary directed graphs, we need to
somehow impose an ordering.
• One way is to define a more general recursion
• Let Dk(v) denote the length of a shortest path
from s to v containing at most k arcs.
!! ! = min !!!! ! + min
!
!!!! ! + !!"
!∈! !
• O(mn) algorithm
• d(j)=Dn-1(j)
Dynamic Programming
• An optimal solution value for one problem is
calculated recursively from the optimal values
of slightly different problems
• Principle of Optimality (Bellman)
• Pieces of optimal solutions are themselves
optimal
• state: points for which values need to be calculated
• stage: steps which define the ordering
0-1 Knapsack Problem
!
! = max !! !! !
!!!
!
!! !! ≤ !!
!!!
!! ∈ 0,1 , ! = 1, … , !!
• aj’s and b are positive integers
0-1 Knapsack Problem
• We think the right-hand side λ taking values
0,1,…,b as the states
• The subset of variables x1,…,xk, represented by
k, as the stage
• The rth stage problem Pr(λ)
!
!! (!) = max !! !! !
!! ∈ !,! ,!!!,…,!
!!!
!
!! !! ≤ !!
!!!
0-1 Knapsack Problem
• ! = !! (!)! gives the optimal value of the
knapsack problem
• Consider an optimal solution x* for Pr(λ)
• If xr* = 0, fr(λ)=fr-1(λ)
• If xr* = 1, fr(λ)=cr + fr-1(λ-ar)
• Hence,
!! ! = max !!!! ! , !! + !!!! ! − !! !
0-1 Knapsack Problem
• Start with f0(λ)=0
• Successively calculate f1(λ),…, fn(λ) for all
integral λ values, 1≤λ≤b
• To obtain the optimal solution, iterate
back from the optimal value fn(b)
• Calculation of each fr(λ) requires a
constant number of operations
• O(nb)
Integer Knapsack
Problem
!
! = max !! !! !
!!!
!
!! !! ≤ !!
!!!
!! ∈ ℤ! , ! = 1, … , !!
• aj’s and b are positive integers
Integer Knapsack
Problem
• We think the right-hand side λ taking values
0,1,…,b as the states
• The subset of variables x1,…,xk, represented by
k, as the stage
• The rth stage problem Pr(λ)
!
!! (!) = max !! !! !
!! ∈ℤ! ,!!!,…,!
!!!
!
!! !! ≤ !!
!!!
Integer Knapsack
Problem
• ! = !! (!)!gives the optimal value of the
knapsack problem
• Consider an optimal solution x* for Pr(λ)
• If xr* = t
!! ! = !! ! + !!!! ! − !!! !
!
for some ! ∈ 0,1, … , !
!!
• Hence,
!! ! = max !! ! + !!!! ! − !!! !
!
!∈ !,!,…, !
!
Integer Knapsack
Problem
• Start with g0(λ)=0
• Successively calculate g1(λ),…, gn(λ) for all
integral λ values, 1≤λ≤b
• To obtain the optimal solution, iterate
back from the optimal value gn(b)
• Calculation of each gr(λ) requires a
constant number of operations for each t
value
• O(nb2)
Integer Knapsack
Problem
• Can we do better?
• If xr* = 0, gr(λ)=gr-1(λ)
• If xr* ≥ 1, gr(λ)=cr + gr(λ-ar)
• Hence,
!! ! = max !!!! ! , !! + !! ! − !! !
• O(nb)
Branch & Bound
• Break the problem into a series of smaller
problems that are easier to solve
• ! = max !! !: ! ∈ ! !
• If we decompose S into smaller sets
! = !! ∪ !! ∪ … ∪ !! !
and calculate ! ! = max !! !: ! ∈ !! , ! = 1, … , !!
we should have ! = max ! ! !
!
Branch & Bound
• Typically we use enumeration trees, with leaves
altogether correspond to a complete
enumeration
Branch & Bound
• Does not have to be binary
Branch & Bound
• Since total enumeration is not plausible for
most problems, the idea is to use an implicit
enumeration scheme
• Pruning some nodes in the enumeration tree
• Using upper and lower bound information
Pruning by Optimality
Pruning by Bound
Further Branching
Branch & Bound
• How do we obtain bounds?
• Primal bounds by feasible solutions
• Dual bounds by relaxation (or duality)
• For IP, usually LP relaxations
• Nodes (subproblems) that must still be
examined are called active
• We do not store a tree but a list of active nodes
• If we can’t prune an active node, how to branch?
• Most fractional variable
• The best feasible solution found so far is called
incumbent
Branch & Bound
• How to choose the active node to be examined
next?
• Arbitrarily
• Depth-First (try to obtain a feasible solution as fast
as possible
• possibility to improve primal bound
• reoptimizing is easy if we just add a single constraint
• Best-Node First (the node with the largest upper
bound for a max problem)
• Attempt to minimize the number of nodes examined
Branch & Bound
• Read CPLEX manual for “parameters”
• Branching Priorities
• Which variable?
• What direction?
• GUB/SOS branching
• balanced B&B trees
• Cutoffs: providing initial feasible solutions
• LP relaxation fine-tuning (simplex pricing strategies,
considering interior-point methods)
• Strong branching
• Branching up and down are tried first for a little while, the
direction with the most impact is carried out
Branch & Bound
• Two types of “hard” problems
• Finding a feasible solution is difficult
• Local search
• Metaheuristics
• Feasibility pump
• Optimality gap is too large
• Strengthen the formulation (adding cuts, Lagrangian
relaxation, column generation)