Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
(optimal) Database delete/insert sequence
digraph deps {
A -> B;
B -> C;
A -> D;
E -> D;
}
Minimize
a_i + b_i + c_i + d_i + e_i
Subject To
c01: a_d - b_d <= -1
c02: b_d - c_d <= -1
c03: a_d - d_d <= -1
c04: e_d - d_d <= -1
c05: c_d - c_i <= -1
c06: b_d - b_i <= -1
c07: c_i - b_i <= -1
c08: b_i - a_i <= -1
c09: d_d - d_i <= -1
c10: d_i - a_i <= -1
c11: e_d - e_i <= -1
c12: d_i - e_i <= -1
Bounds
1 <= a_d <= 10
1 <= b_d <= 10
1 <= c_d <= 10
1 <= d_d <= 10
1 <= e_d <= 10
1 <= a_i <= 10
1 <= b_i <= 10
1 <= c_i <= 10
1 <= d_i <= 10
1 <= e_i <= 10
Integer
a_d
b_d
c_d
d_d
e_d
c_i
b_i
a_i
d_i
e_i
End
Problem:
Rows: 12
Columns: 10 (10 integer, 0 binary)
Non-zeros: 24
Status: INTEGER OPTIMAL
Objective: obj = 22 (MINimum)
No. Row name Activity Lower bound Upper bound
------ ------------ ------------- ------------- -------------
1 c01 -1 -1
2 c02 -1 -1
3 c03 -1 -1
4 c04 -1 -1
5 c05 -1 -1
6 c06 -3 -1
7 c07 -1 -1
8 c08 -1 -1
9 c09 -1 -1
10 c10 -3 -1
11 c11 -3 -1
12 c12 -1 -1
No. Column name Activity Lower bound Upper bound
------ ------------ ------------- ------------- -------------
1 a_i * 6 1 10
2 b_i * 5 1 10
3 c_i * 4 1 10
4 d_i * 3 1 10
5 e_i * 4 1 10
6 a_d * 1 1 10
7 b_d * 2 1 10
8 c_d * 3 1 10
9 d_d * 2 1 10
10 e_d * 1 1 10
Integer feasibility conditions:
KKT.PE: max.abs.err = 0.00e+00 on row 0
max.rel.err = 0.00e+00 on row 0
High quality
KKT.PB: max.abs.err = 0.00e+00 on row 0
max.rel.err = 0.00e+00 on row 0
High quality
End of output
#/bin/bash
# dot -Tpng dependency-relationship.dot | display -
glpsol --cpxlp fk.lp -o output.txt
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment