STUDY MATERIAL:
• [CLRS] chapter 16
• Lecture Notes 7, 8
Copyright By PowCoder代写 加微信 powcoder
Combinatorial Optimization Problems
The Greedy Method
Problems:
Coin Change Making
Event Scheduling
Interval Point Cover
More Graph Optimization problems considered later
COMBINATORIAL OPTIMIZATION
find the best solution out of finitely many possibilities.
Mr. Roboto:
Find the best path from A to B avoiding obstacles
There are infinitely many ways to get from A to B.
With brute-force there are exponentially many paths to try.
We can’t try them all.
TheremBauytbyoeuaosnimlypnleeadndtofatrsytf(ininitcerleymmeanntayl)cgrirteiceadlypasthrastegy. to find the best.
Mr. Roboto:
Find the best path from A to B avoiding obstacles
The Visibility Graph: 4n + 2 vertices
(n = # rectangular obstacles)
Combinatorial Optimization Problem (COP)
INPUT: Instance I to the COP.
Feasible Set: FEAS(I) = the set of all feasible (or valid) solutions for instance I,
usually expressed by a set of constraints.
Objective Cost Function:
Instance I includes a description of the objective cost function,
CostI that maps each solution S (feasible or not) to a real number or ±.
Goal: Optimize (i.e., minimize or maximize) the objective cost function.
Optimum Set:
OPT(I) = { Sol FEAS(I) | CostI (Sol) CostI (Sol’), Sol’FEAS(I) } the set of all minimum cost feasible solutions for instance I
Combinatorial means the problem structure implies that only a discrete & finite number of solutions need to be examined to find the optimum.
OUTPUT: A solution Sol OPT(I), or report that FEAS(I) = .
GREEDY METHOD
Greedy attitude:
Don’t worry about the long term consequences of your current action. Just grab what looks best right now.
Most COPs restrict a feasible solution to be a finite set or sequence from among the objects described in the input instance.
E.g., a subset of edges of the graph that forms a valid path from A to B.
For such problems it may be possible to build up a solution incrementally by considering one input object at a time.
GREEDY METHOD is one of the most obvious & simplest such strategies: Selects the next input object x that is the incremental best option at that time. Then makes a permanent decision on x (without any backtracking),
either committing to it to be in the final solution, or
permanently rejecting it from any further consideration.
S = Set of all input
C= Committed objects
R= Rejected objects
U= Undecided objects
Such a strategy may not work on every problem.
But if it does, it usually gives a very simple & efficient algorithm.
Obstacle avoiding shortest A-B path
d(p,q) = straight-line distance between points p and q.
u = current vertex of the Visibility Graph we are at (u is initially A).
If (u,B) is a visibility edge, then follow that straight edge. Done.
Otherwise,
from among the visibility edges (u,v) that get you closer to B, i.e., d(v,B) < d(u,B), make the following greedy choice for v:
(1) Minimize d(u,v) take shortest step while making progress (2) Minimize d(v,B) get as close to B as possible
(3) Minimize d(u,v) + d(v,B) stay nearly as straight as possible
Which of these greedy choices is guaranteed to produce the shortest A-B path?
gresehdoyrtecshtopicaeth(231)
Later we will investigate a greedy strategy that works.
Conflict free object subsets
S = the set of all input objects in instance I
FEAS(I) = the set of all feasible solutions
Definition: A subset C S is “conflict free” if it is contained in some feasible solution:
ConflictFreeI (C) =
true if Sol FEAS(I): C Sol false otherwise
ConflictFreeI (C) = false
means C has some internal conflict and no matter what additional input objects you add to it, you cannot get a feasible solution that way.
E.g., in any edge-subset of a simple path from A to B, every vertex has in-degree at most 1. So a subset of edges, in which some vertex has in-degree more than 1, has conflict.
The Greedy Loop Invariant
The following are equivalent statements of the generic greedy Loop Invariant:
The decisions we have made so far are safe, i.e.,
they are consistent with some optimum solution (if there is any feasible solution).
Either there is no feasible solution, or
there is at least one optimum solution Sol OPT(I) that
includes every object we have committed to (set C), and excludes every object that we have rejected (set R = S – U – C).
S= Set of all input
LI: FEAS(I) = or [ SolOPT(I) : C Sol C U ].
Pre-Cond: S is the set of objects in input instance I
Pre-Cond & PreLoopCode LI
LI: FEAS(I) = or Sol OPT(I) : C Sol C U
LI & exit-cond & LoopCode LI
Greedy method
Greedy Choice:
select x U with best
LI & exit-cond PostLoopCond
Cost(C{x}) possible
U U – {x} § permanently decide on x
if ConflictFree(C{x}) & Cost(C{x}) better than Cost(C)
then C C {x} § ----------- commit to x § else ------------------------------------ reject x
FEAS(I) = or C OPT(I)
PostLoopCond
& PostLoopCode Post-Cond
Post-Cond: output COPT(I) or FEAS(I) =
LI & exit-cond & LoopCode LI U & LI: FEAS(I)= or SolOPT(I): CSolCU
x committed
x rejected
Greedy Choice:
select x U with maximum Cost(C{x}) possible
U U – {x} § permanently decide on x if ConflictFree(C{x}) &
Cost(C{x}) > Cost(C)
then C C {x} § ———– commit to x
may or may not be the same as
§ else ———————————— reject x Sol
LI: FEAS(I)= or Solnew OPT(I): CSolnew CU NOTE
LI & exit-cond & LoopCode LI U & LI: FEAS(I)= or SolOPT(I): CSolCU
x committed
and x Sol
OK. Take Sol =Sol
Greedy Choice:
select x U with maximum Cost(C{x}) possible
U U – {x} § permanently decide on x if ConflictFree(C{x}) &
Cost(C{x}) > Cost(C)
then C C {x} § ———– commit to x
§ else ———————————— reject x
may or may not be the same as Sol
LI: FEAS(I)= or Solnew OPT(I): CSolnew CU
LI & exit-cond & LoopCode LI U & LI: FEAS(I)= or SolOPT(I): CSolCU
x committed
and x Sol
Needs Investigation
Greedy Choice:
select x U with maximum Cost(C{x}) possible
U U – {x} § permanently decide on x if ConflictFree(C{x}) &
Cost(C{x}) > Cost(C)
then C C {x} § ———– commit to x
§ else ———————————— reject x
may or may not be the same as Sol
LI: FEAS(I)= or Solnew OPT(I): CSolnew CU
LI & exit-cond & LoopCode LI U & LI: FEAS(I)= or SolOPT(I): CSolCU
Case 2a: x rejected
and x Sol
OK. Take Sol =Sol
Greedy Choice:
select x U with maximum Cost(C{x}) possible
U U – {x} § permanently decide on x if ConflictFree(C{x}) &
Cost(C{x}) > Cost(C)
then C C {x} § ———– commit to x
§ else ———————————— reject x
may or may not be the same as Sol
LI: FEAS(I)= or Solnew OPT(I): CSolnew CU
LI & exit-cond & LoopCode LI U & LI: FEAS(I)= or SolOPT(I): CSolCU
Case 2b: x rejected
and x Sol
Needs Investigation
Greedy Choice:
select x U with maximum Cost(C{x}) possible
U U – {x} § permanently decide on x if ConflictFree(C{x}) &
Cost(C{x}) > Cost(C)
then C C {x} § ———– commit to x
§ else ———————————— reject x
may or may not be the same as Sol
LI: FEAS(I)= or Solnew OPT(I): CSolnew CU
LI & exit-cond & LoopCode LI Case 1b: x committed and x Sol
Trade off yCx
Some times more than one object on either side is traded off.
Show: Solnew OPT
Show y Sol – C
Solnew Sol {x} – {y} satisfies:
(2) Cost(Solnew) is no worse than Cost(Sol)
(1) Solnew FEAS, &
LI & exit-cond & LoopCode LI Case 2b: x rejected and x Sol
Sol OPT x
Some times more than one object on either side is traded off.
x could not have created a conflict. So, it must have not improved the objective function.
Show: Solnew OPT
Solnew Sol {y}–{x}, forsomeyU-Sol satisfies:
(1) Solnew FEAS, &
(2) Cost(Solnew) is no worse than Cost(Sol)
COIN CHANGE MAKING
Use minimum number of coins to make change for a given amount. Greedy: pick the largest coin that fits first, then iterate.
The Coin Change Making Problem
PROBLEM: Within a coin denomination system, make change for a given amount S, using the fewest number of coins possible.
Greedy Strategy (the obvious one):
Commit to the largest coin denomination that fits within the (remaining) amount, then iterate.
Greedy(S) = the greedy solution for amount S. Optimum(S) = the optimum solution for amount S.
Example 1: Canadian coin denomination system: 25, 10, 5, 1 cents.
S = 98 (Two of many feasible solutions are shown below.)
= 10 + 10 + 10 + 10 + 10 + 10 + 10 + 10 + 10 + 5 + 1 + 1 + 1 13 coins used = 25 + 25 + 25 + 10 + 10 + 1 + 1 + 1 Optimum sol uses 8 coins.
Greedy(98) = Optimum(98) in the Canadian system.
Example 2: Imaginary coin denomination system: 7, 5, 1 kraaps.
S = 10 = 5 + 5 (Optimum) = 7 + 1 + 1 + 1 (Greedy). Greedy(10) Optimum(10) in this system.
The Problem Formulation
INPUT: Coin denomination system a = a1 , a2 , … , an , a1 > and S (all positive integers).
OUTPUT:Thesolutionx=x1 , x2 , …, xn , where
xt = the number of coin type at used, for t = 1..n.
a2 > … > an = 1,
We need an =1 to have a feasible soln for every S.
FEAS: GOAL:
a1x1 + a2x2 + … + anxn = S, &
xt is a non-negative integer, for t=1..n.
Minimize objective cost
x1 + x2 + … + xn.
objective function
feasibility constraints
minimize x1 + x2 + ··· + xn
subject to:
(1) a1x1 + a2x2 +···+anxn =S (2) xtN, for t = 1..n
The Greedy Choice & Objective
Greedy Choice: ConflictFree:
Problem Objective Cost: Greedy Objective Cost:
choose the largest coin that fits
𝑛 𝑥 + 𝜆𝑈 𝑖=1 𝑖
𝑈=𝑆− 𝑛𝑖=1𝑎𝑖𝑥𝑖
At the end: 𝑈 = 0 Greedy Objective = Problem objective
(𝜆 is an unspecified prohibitively large positive number)
The Greedy Loop Invariant
Generic Greedy Loop Invariant ( feasible solution) : SolOPT: CSolCU.
Current greedy solution: x1, x2, …, xn Committed to: x1, x2, …, xt , for some t 1..n. Rejected: no more of a1, a2, …, at-1. Considering: any more of at?
Not yet considered: xk = 0 for k > t.
There is U amount remaining to reach the target value S.
Loop Invariant:
x1, x2, …, xn FEAS(S – U), (need U more to reach target S) Sol = y1, y2, …, yn OPT(S):
yk = xk , for k < t, yt xt ,
xk = 0 , for k > t.
(Sol excludes what Greedy has rejected) (Sol includes what Greedy has committed to)
(not yet considered)
Algorithm: Greedy Coin Change
Pre-Cond: input is a = a1, a2, …, an, a1>a2> … >an =1; and S (all pos integers)
Pre-Cond & PreLoopCode LI
Sol = y1, y2, …, yn OPT(S):
U S; t 1; x1, x2, …, xn 0, 0, …, 0
LI & exit-cond & LoopCode LI
then t t+1
else xt xt +1 § commit to another at
return x1, x2, …, xn
Post-Cond: output x1, x2, …, xn OPT(S)
yk = xk LI & exit-cond
for k < t,
yt xt , xk =0 for k > t.
x1, x2, …, xn FEAS(S – U),
if U < a NO t
PostLoopCond
x1,x2, ...,xnOPT(S)
PostLoopCond
§ reject: no more at
PostLoopCode
Post-Cond
MP = U + (n-t) 26
Efficient implementation
minimize x1 + x2 + ··· + xn
subject to:
(1) a1x1 + a2x2 +···+anxn =S (2) xtN, for t = 1..n
Algorithm Greedy( a1 , a2 , ... , an , S) CoinCount 0; U S
objective function
feasibility constraints
§ takes O(n) time
for t 1 .. n do xt U div at
U U mod at
CoinCount CoinCount + xt end-for
§ largest coin denomination first § xt U/at
§ U U – at xt § objective value
return ( x1 , x2 , ... , xn ; CoinCount) end
Is G(S) = Opt(S) ?
A coin denomination system is called Regular if in that system G(S) = Opt(S) S.
Questions:
(1) In the Canadian Coin System, is G(S) = Opt(S) for all S?
(2) In a given Coin System, is G(S) = Opt(S) for all S?
(3) In a given Coin System, is G(S) = Opt(S) for a given S?
(1) YES. It’s Regular. We will see why shortly.
(2) YES/NO: Yes if the system is Regular. NO otherwise.
There is a polynomial time Regularity Testing algorithm
(described next) to find the YES/NO answer.
(3) YES/NO: Regular system: always yes.
Non-regular system: YES for some S, NO for other S.
Exponential time seems to be needed to find the Yes/No answer. (This is one of the so called NP-hard problems we will study later.)
How to Test Regularity
• Question: Is a given Coin Denomination System Regular,
i.e., in that system is G(S) = Opt(S) for all S?
• Greedy( a1 , a2 , ... , an , S) = (x = x1 , x2 , ... , xn ; G(S) = St xt )
Optimum( a1 , a2 , ... , an , S) = (y = y1 , y2 , ... , yn ; Opt(S) = St yt )
• YES or NO: For the coin denomination system a1 , a2 , ... , an :
S: G(S) = Opt(S).
• There are infinitely many values of S to try.
• However, if there is any counter-example S, there must be one among polynomially many critical values that need to be tested to
determine the Yes/No answer. And, each test can be done fast.
What are these critical values? How are they tested?
Regularity & Critical Values
• Consider the smallest multiple of each coin value that is not smaller than
the next larger coin value:
St = at mt, mt =at-1 /at , fort=2..n.
• Necessary Condition for correctness of Greedy: G(St) mt, for t = 2..n. WHY?
• This also turns out to be sufficient (under some mild pre-condition that is satisfied by virtually any reasonable coin denomination system):
FACT 1: [Regularity Theorem of Magazine, Nemhauser, Trotter, 1975] Pre-Condition: St < at-2 , for t = 3..n
S: G(S) = Opt(S) G(St) mt, for t = 2..n.
Proof: See Lecture Note 7.
Let’s Test the Canadian System
FACT 1: [Magazine, Nemhauser, Trotter, 1975] Pre-Condition: St < at-2 , for t = 3..n
S: G(S) = Opt(S) G(St) mt, for t = 2..n.
mt = at-1 / at
Greedy: G(St)
Pre-Cond: St < at-2
Test: G(St) mt
This table can be constructed and tested in O(n2) time.
Another System
FACT 1: [Magazine, Nemhauser, Trotter, 1975] Pre-Condition: St < at-2 , for t = 3..n
S: G(S) = Opt(S) G(St) mt, for t = 2..n.
mt = at-1 / at
Greedy: G(St)
Pre-Cond: St < at-2
Test: G(St) mt
This table can be constructed and tested in O(n2) time.
What if Pre-Condition doesn’t hold?
FACT 1: [Magazine, Nemhauser, Trotter, 1975] Pre-Condition: St < at-2 , for t = 3..n
S: G(S) = Opt(S) G(St) mt, for t = 2..n.
[This can be tested in O(n2) time.]
S: G(S) = Opt(S) O(n2) critical values test OK in O(n3) time.
See also Lecture Note 7.
FACT 2: [Pearson, 2005]
The Optimum Sub-Structure Property
We just noticed an important property that will be used many times later:
The optimum sub-structure property: any sub-structure of an optimum structure is itself an
optimum structure (for the corresponding sub-instance).
Problems with this property are usually amenable to more efficient algorithmic solutions than brute-force or exhaustive search methods.
This property is usually shown by a “cut-&-paste” argument (see below).
Example 1: The Coin Change Making Problem.
Consider an optimum solution Sol OPT(S). Let G1 be a group of coins in Sol.
Suppose G1 FEAS(U). Then we must have G1 OPT(U). Why?
Because if G1 OPT(U), then we could cut G1 from Sol, and paste in the optimum sub- structure G2 OPT(U) instead. By doing so, we would get a new solution Sol’ FEAS(S) that has an even better objective value than Sol. But that would contradict Sol OPT(S).
Example 2: The Shortest Path Problem.
Let P be a shortest path from vertex A to vertex B in the given graph G.
Let P’ be any (contiguous) sub-path of P. Suppose P’ goes from vertex C to D.
Then P’ must be a shortest path from C to D. If it were not, then there must be an even shorter path P’’ that goes from C to D. But then, we could replace P’ portion of P by P’’ and get an even shorter path than P that goes from A to B.
That would contradict the optimality of P.
EVENT SCHEDULING
A banquet hall manager has received a list of reservation requests for the exclusive use of her hall for specified time intervals
She wishes to grant the maximum number of reservation requests that have no time overlap conflicts
Help her select the maximum number of conflict free time intervals
The Problem Statement
INPUT: A set S = { I1, I2, ···, In} of n event time-intervals Ik = sk , fk, k =1..n, where sk = start time of Ik ,
fk = finishing time of Ik , (sk