Greedy Algorithm
Submitted to:
Prof. Dr. / Almoataz abdelaziz
by
Ahmed Ismail Saad Ibrahim
ID: 2301519
EPM681 (PG2015)
Introduction to Greedy Algorithm
• A Greedy Algorithm is a problem-solving method where the best
decision is made at each step based on current information, with
the hope that it leads to the overall optimal solution.
• Key Features:
• - Makes locally optimal choices.
• - Simplifies complex problems.
• - Does not backtrack or revise earlier decisions.
Introduction to
Greedy Algorithm
➢ Greedy Algorithm solves optimization problems by
making locally optimal choices.
➢ It assumes that locally optimal solutions lead to a
globally optimal solution.
➢ Does not backtrack or revise earlier decisions.
Applications in Power Systems
- ECONOMIC LOAD - UNIT - OPTIMAL - SHORTEST PATH
DISPATCH (ELD) COMMITMENT CAPACITOR FOR POWER
PROBLEM PLACEMENT ROUTING
Algorithm Workflow
1. Define the 2. Identify decision 3. Apply greedy 4. Evaluate and
objective function. variables. selection iteratively. refine the solution.
Example: Unit Commitment Problem
Scenario: Power generators need to be scheduled to meet electricity
demand over a day while minimizing costs.
Goal: Select the generators to run at each time step such that:
1. Demand is met.
2. Total operating cost is minimized.
Greedy Solution:
1. Rank generators by cost efficiency (e.g., $/MWh).
2. Turn on the cheapest generator first.
3. Add generators in order of cost until demand is met.
Step-by-Step Solution
1. Assume the 2. Available
- G1: 50 MW at - G2: 75 MW at
demand at a time generators and their
$20/MWh $25/MWh
step is 150 MW. costs:
- Remaining
- G3: 100 MW at Greedy Algorithm 1. Select G1 (50
demand = 150 MW
$30/MWh Steps: MW, $20/MWh).
- 50 MW = 100 MW.
- Remaining 3. Select G3 for
2. Select G2 (75
demand = 100 MW remaining 25 MW
MW, $25/MWh).
- 75 MW = 25 MW. at $30/MWh.
Visualization of Unit Commitment
In this example,
1. Start with the
generators are 2. Add the next
cheapest generator
scheduled to meet cheapest (G2).
(G1).
demand step-by-step:
This approach ensures
3. Use higher-cost
demand is met with
generators (G3) only if
minimal costs at each
necessary.
step.
Advantages and
Limitations
Advantages:
• Simple and quick to implement.
• Provides a feasible solution for real-time operations.
• Priorities cost-effectiveness in power generation.
Limitations:
• May not be globally optimal (e.g., higher startup costs
ignored).
• Ignores constraints like ramp rates or minimum on/off
times.
• Assumes accurate generator cost data and availability.
Conclusion
- GREEDY ALGORITHMS OFFER - IDEAL FOR APPLICATIONS - BALANCE SIMPLICITY WITH
PRACTICAL SOLUTIONS IN REQUIRING QUICK AND SOLUTION ACCURACY.
POWER SYSTEMS. EFFICIENT DECISION-MAKING.
References
1. Power System Optimization by
Greedy Methods.
2. IEEE Transactions on Power Systems.
3. Optimization Techniques in Power
Systems (Textbook).
