JMEE7311

Power Systems Operation and

Management
lecture 6

Introduction to Mixed Integer Linear Programming

Review of Power Flow Techniques

Dr. Nassim Iqteit

21-3-2019

Daniel Kirschen
1
LP formulation of Economic Dispatch

C1

L
C1 = a1 + c1 x1
1 2 3

Minimize CT = a1 + a2 + a3 + a1
c1 x1 + c2 x2 + c3 x3 C2 P1MAX
x1
P1MIN
Subject to: x1 + x2 + x3 = L
P1MIN ≤ x1 ≤ P1MAX C2 = a2 + c2 x2

P2MIN ≤ x2 ≤ P2MAX a2
P2MAX x2
P3MIN ≤ x3 ≤ P3MAX C3 P2MIN

• Objective function is linear C3 = a3 + c3 x3

• All constraints are linear
• All variables are real
• Problem can be solved using a3
standard linear programming 2
x3
P3 MIN P3MAX
Can we use LP for unit commitment?

C1
MIN MAX
x1 = 0 or P 1 ≤ x1 ≤ P
2

x2 = 0 or P2MIN ≤ x2 ≤ P2MAX a1
x1
C2 P1MIN P1MAX

x3 = 0 or P3MIN ≤ x3 ≤ P3MAX

The variables no longer have a2

a contiguous domain x2
P2MIN P2MAX
(Non-convex set) C3
Standard linear programming
is no longer applicable

a3
x3 3
P3 MIN P3MAX
Mixed Integer Linear Programming (MILP)
• Some decision variables are integers
• Special case: binary variables {0,1}
• Other variables are real
• Objective function and constraints are linear

Example

Except for the fact that the variables are integer, this looks very much like a linear programming problem.

4
Example

x2
8

4x1 + 2x2 = 15
6

2
x1 + 2x2 = 8
x1 + x2 = 5
0 2 4 6 8
x1
5
LP relaxation

x2 Let us relax the constraint that the

8 variables must be integer.

4x1 + 2x2 = 15 The problem is then a regular LP

6

4 Solution of the relaxed LP

x1 = 2.5; x2 = 2.5; Objective = 12.5

2
x1 + 2x2 = 8
x1 + x2 = 5
0 2 4 6 8
x1
6
Objective: 3x1 + 2x2
LP relaxation….cont.

x2 The solution of the relaxed problem

8 is always better than the solution of
original problem!
(Lower objective for minimization
4x1 + 2x2 = 15 problem, higher for maximization)
6

4 Solution of the relaxed LP

x1 = 2.5; x2 = 2.5; Objective = 12.5

2
x1 + 2x2 = 8
x1 + x2 = 5
0 2 4 6 8 x1
7
Solution of the integer problem

x2
8

4x1 + 2x2 = 15
6

4 Solution of the relaxed LP

x1 = 2.5; x2 = 2.5; Objective = 12.5

2
x1 + 2x2 = 8
x1 + x2 = 5
0 2 4 6 8 x1
8
Solution of the integer problem…cont.

x2
8

4x1 + 2x2 = 15
6 Solution of the original problem
x1 = 2; x2 = 3; Objective = 12.0

4 Solution of the relaxed LP

x1 = 2.5; x2 = 2.5; Objective = 12.5

2
x1 + 2x2 = 8
x1 + x2 = 5
0 2 4 6 8 x1
9
Naïve rounding off

x2

x1

LP solution
IP solution

The optimal integer solution can be far away from the LP solution
“Far away” can be difficult to find when there are many dimensions 10
Finding the integer solution

• Large number of integer variables

• Vast number of possible integer solutions
• Need a systematic procedure to search this solution
space
• Fix the variables to the nearest integer one at a time
• “Branch and Bound” algorithm

11
Example

Relaxed LP solution: (1.75, 0.75)

12
Branch on x1

Problem 0

x1 ≥ 0; x2 ≥ 0 x1 ≥ 0 ; x2 ≥ 0
x1 ≤ 1 x1 ≥ 2
Problem 1 Problem 2 13
Branch on x1

Problem 2
Problem 1

Solution of
Problem 1 Solution of Problem 2

14
Search Tree: first layer

Solution of Problem 1: Solution of Problem 2:

• x1 integer • x1 & x2 integer
• x2 real • Feasible solution of
• Not a feasible solution yet the original problem
• Can still branch on x2 • Bound on the optimum
• Best solution so far
15
Branch on x2

Problem 1

x1 ≤ 1; x2 ≥ 0

x1 ≥ 0; x2 ≥ 0 x1 ≥ 0; x2 ≥ 0
x1 ≤ 1; x2 ≤ 1 x1 ≤ 1; x2 ≥ 2
Problem 3 Problem 4 16
Search Tree: second layer

No solution
No integer solution yet 17
Branch and Bound: what next?

Optimal solution

Solution of relaxed
problem 4 is bounded
by solution of problem
Can’t go any further 2. No point in going
in this direction further
No solution 18
Comments on Branch and Bound

• Search tree gets very big if there are more than a few integer or binary
variables
• Even with the bounds provided by the relaxed solutions, exploring the
tree usually takes a ridiculous amount of time
• Clever mathematicians have developed techniques to identify “cuts”
• Constraints based on the structure of the problem that eliminate part of the
search tree
• “Branch and Cut” algorithm

19
Duality Gap

• Finding the optimal solution for a large problem can take too much
time even with branch and cut
• Best solution of relaxed problem provides a bound on the solution
• Duality gap: Difference between best solutions of relaxed problem and
actual problem
• Stop searching the tree if duality gap is sufficiently small

20
MATLAB
Mixed-integer linear programming (MILP) intlinprog

f, x, intcon, b, beq, lb, and ub are vectors, and A and Aeq are matrices.
You can specify f, intcon, lb, and ub as vectors or arrays.

x = intlinprog(f,intcon,A,b)
x = intlinprog(f,intcon,A,b,Aeq,beq)
x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)
x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub,x0)
Example
f = [8;1];
x = 2×1
intcon = 2;
6.5000
A = [-1,-2;
7.0000
-4,-1;
2,1];
https://yalmip.github.io/allsolvers/ b = [14;-33;20];
x = intlinprog(f,intcon,A,b)
Example

x = 3×1
f = [-3;-2;-1];
intcon = 3; 0
A = [1,1,1]; 5.5000
b = 7; 1.0000
Aeq = [4,2,1];
beq = 12;
lb = zeros(3,1);
ub = [Inf;Inf;1]; % Enforces x(3) is binary
x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)
• Gauss–Seidel
• Newton–Raphson
• Fast Decoupled Method

Assumptions
 “DC” Power Flow

The “DC” power flow makes the most severe approximations:

– completely ignore reactive power, assume all the voltages are always 1.0 per
unit, ignore line conductance
This makes the power flow a linear set of equations, which can be
solved directly: (δ i − δ j ) −1
Pij =
xij δ = −B P

where B is the imaginary part of the bus admittance matrix with the
row and column corresponding to the slack bus deleted, and,
similarly, δ and P omit the slack bus.
27
Approximations N

• Neglect Reactive Power Pi = ∑V V [G

j =1
i j ij cos(δ i − δ j ) + Bij sin(δ i − δ j )]

N
• Neglect Resistance of the Branches P =
i ∑V V B i j ij sin(δ i − δ j )
j =1
−1
• Assume All Voltage Magnitudes = 1.0 p.u  Pi =
N

∑B ij sin(δ i − δ j ) δ = −B P
j =1

N N
(δ i − δ j )
• Assume all angles are small P =
i ∑ B (δ
j =1
ij i − δ j ) or Pi = ∑
j =1
xij

Why is it called dc power flow?

• Reactance plays the role of resistance in dc circuit
• Voltage angle plays the role of dc voltage
• Power plays the role of dc current (δ i − δ j ) (Vi − V j )
Pij = I ij =
xij Rij
 Example

 −25 20 
B= 
 20 −30  (δ1 − δ 2 ) 0 − 0
P12 = = =0
P = -Bδ x12 0.01
(δ 2 − δ 3 ) 0 + 0.05
 P2   −25 20  δ 2  P23 = = =1
  = −  20 −30  δ  x23 0.05
P
 3   3
(δ1 − δ 3 ) 0 + 0.05
−1 P13 = = = 0.5
δ 2   −25 20   1   0  x13 0.1
δ  =    −1.5 =  −0.05
 3  20 −30     
Comparison of different power flow methods

Other Methods
• Fuzzy Logic
• GA
• Particle swarm optimization
HW:
Thank you