Advanced Optimisation with Python
• Integer Programming Modelling Refresher
• Modelling with Binary variables
• Formulating problems with computational efficiency in mind • Presolve
Copyright By PowCoder代写 加微信 powcoder
Integer Programming Modelling Refresher
• An IP in which all variables are required to be integers is called a pure integer programming problem.
• An IP in which only some of the variables are required to be integers is called a mixed integer programming problem.
• An integer programming problem in which all the variables must be 0 or 1 is called a 0-1 IP or BP.
• The LP obtained by omitting all integer or 0-1 constraints on variables is called relaxation of the IP.
Integer Programming Modelling
Stockco is considering four investments. Investment 1 will yield a new present value (NPV) of $16,000; investment 2, an NPV of $22,000; investment 3, an NPV of $12,000; and investment 4, an NPV of $8,000. Each investment requires a certain cash outflow at the present time: investment 1, $5,000; investment 2, $7,000; investment 3, $4,000; and investment 4, $3,000. Currently, $14,000 is available for investment.
Integer Programming Modelling
• Begin by defining a variable for each decision that Stockco must make, i.e. xi is the money invested in option i
• The objective function is NPV obtained by Stockco; Total NPV obtained by Stocko = 16×1 + 22×2 + 12×3 + 8×4
• Stockco faces the constraint that at most $14,000 can be invested.
• Stockco’s 0-1 IP is
maxz=16×1 +22×2 +12×3 +8×4 s.t. 5×1 + 7×2 + 4×3 +3×4 ≤ 14
xj = 0 or 1 (j = 1,2,3,4)
Integer Programming Modelling
What if we have the following requirements?
1. Stockco can invest in at most two investments
x1+x2 +x3 +x4 +x5 2
2. If Stockco invests in investment 2, they must also invent in
investment 1.
3. If Stockco invests in investment 2, they cannot invest in investment 4.
Simple Implications
• If we do A then we must also do B b≥a
• If we do A then we must not do B a + b ≤1
• If we can at most do n out of A, B,…, Z a + b +… + z ≤ n
Implications
• If we do A then we must do B and C b ≥ a and c ≥ a
• If we do A then we must do either B or C b + c≥ a
• If we do B or C then we must do A a ≥ b and a ≥ c
Harder Implications
• If we do both B and C then we must do A
2a ≥ b + c a ≥ b + c -1
Generalised Implications
• If we do two or more of B,C, D or E then we must do A. Try a ≥ b + c +d + e -1
If more than two projects done then a>1 which cannot be as a is binary.
Consider a ≥ (b + c +d + e )/4
This works if b=c=d=e=1 but what if c=d=e=0, for b=1 and c=d=e=0 we
get a ≥1/4 and since a is binary this implies a=1 which is not right.
a ≥ (b + c +d + e – 1 )/3
This would work and A will only be forced if two or more of B, C, D, or E is done.
General If-Then Constraints
If f (x , x ,…, x ) 0 is satisfied, then the constraint 12n
g(x , x ,…, x ) 0 must be satisfied. 12n
-g(x,x ,…,x )My 12n
f(x,x ,…,x )M(1-y) 12n
y = 0 or 1
M is a large enough number not to limit f(x) or –g(x) in any way, infinity would work, but we need the smallest such number to improve the LP relaxation bound to help the solver.
General If-Then Constraints
If X1 + X2 + X3 > 0 then 2 X1 – 3X2 + X3 <= 0
Assume that we have the following bounds defined on our decision variables.
X1 <= 100, X2 <= 40, X3 <= 20
We add the following two constraints together with a new binary decision variable, y
- 2 X1 + 3 X2 – X2 <= 120 y X1 + X2 + X3 <= 160 (1-y)
Either-or constraints
We are given two constraints of the form f(x,x ,...,x )0
12n g(x,x ,....,x )0
We want to ensure at least one of them is satisfied
f(x,x ,...,x )My 12n
g(x,x ,....,x )M(1−y) 12n
y = 0 or 1
M is a large enough number not to limit f(x) or g(x) in any way, infinity would work, but we need the smallest such number to improve the LP relaxation bound to help the solver.
Either-or constraints
We want at least one of the following constraints to be satisfied
X1 + X2 + X3 <= 0 OR 2 X1 – 3X2 + X3 <= 0
Assume that we have the following bounds defined on our decision variables.
X1 <= 100, X2 <= 40, X3 <= 20
We add the following two constraints together with a new binary decision variable, y
X1 + X2 + X3 <= 160 y
2 X1 – 3X2 + X3 <= 220 (1-y)
Formulating problems with computational efficiency in mind
Computational effort
nbinaryvariableshave2n possiblesettingsandhence
2n possible nodes at the bottom of the Branch and Bound solution tree.
eg2100 =1030 (ormillion5)
In practice B&B more efficient than this but still important to reduce
binary variables where possible.
Where applicable make use of Special Ordered Sets (SOS1 and SOS2). See discussion and example in Book 3.4.4 (SOS1) and 3.4.5 (SOS2).
𝑏𝑖𝑗 =ቊ1iftruck𝑖sentontrip𝑗
0 otherwise
where 𝑖 = 1,2,3 and 𝑗 = 1,2
If the trucks are identical in terms of running costs, capacities,
etc then for each integer solution eg
𝑏 =1𝑏 =1𝑏 =1 (1) 11 22 32
there will be symmetric integer solutions, eg
𝑏 =1𝑏 =1𝑏 =1 (2) 21 12 32
Symmetric solution will be obtained at different nodes of the B&B costing us valuable computational time and effort.
𝑛𝑖 = number of trucks sent on trip 𝑗, then (1) and (2) n1 =1and𝑛2 =2
Presolve / Tightening Bounds
𝑀𝑖𝑛 5𝑏 +7𝑏 +10𝑏 +3𝑏 +𝑏
12345 s.t.
𝑏 −3𝑏 +5𝑏 +𝑏 −𝑏 ≥2 (1) 12345
−2𝑏 +6𝑏 −3𝑏 −2𝑏 +2𝑏 ≥0 (2) 12345
−𝑏2 +2𝑏3 −2𝑏4 −𝑏5 ≥1 (3) 𝑏𝑖 𝑖 = 1,2,3,4,5 binary
by(3) 2𝑏3 ≥1+𝑏2 +2𝑏4 +𝑏5 ≥1
⇒𝑏3 ≥1.Thus𝑏3 =1andcanberemoved 2
from the problem.
Presolve / Tightening bounds (cont) Constraint (2) now becomes:
6𝑏 ≥3+2𝑏 +2𝑏 −2𝑏 ≥1 21145
Thus𝑏 ≥ ⇒𝑏 =1 262
Presolve / Tightening bounds (cont) Substituting known values in constraint (3)
Substituting known values into constraint (1) gives
Looking now at the objective function, we see that it will be at minimum when
So we have managed to solve the whole problem simply by analysing the constraints.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com