Сравнение Алгоритмов

Алгоритм БГ с $t_0,...,t_n$
Алгоритм БГ с LLL, и вычислением частного
Их векторные версии
--

Задача (пример Штурмфельса)

Матрица $A$ и тестовые данные приведены ниже.

Задача:

$$ w^Tu \rightarrow min\\ s.t. Au=b, $$

где $w^T=[1,1,1,1,4,3,2,1,7,5,3,1,10,7,4,1],~b=[220,215,93,64,108,286,71,127]$.

Оптимальный план: $$ \begin{bmatrix} 108 & 112 & 0 & 0\\ 0 & 174 & 41 & 0\\ 0 & 0 & 30 & 63\\ 0 & 0 & 0 & 64 \end{bmatrix} $$

$A$ -- матрица оператора суммирования по строкам и столбцам



In [25]:

    
vec =vector([2,3,4,5])
len(vec)









    Out[25]:





4



In [2]:

    
import time

##initial data

A=matrix([[1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0],
          [0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0],
          [0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0],
          [0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1],
          [1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0],
          [0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0],
          [0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0],
          [0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1]])

feasibleSolution=vector([68,119,26,7,
        20,84,17,94,
        15,54,14,10,
        5,29,14,16])

Алгоритм 1



In [5]:

    
load("StandardGBIP.sage")

start = time.time()#measuring the time

#first row is for t
optimizationOrder=TermOrder('lex',9)+TermOrder('wdeglex',(
                     1,1,1,1,
                     4,3,2,1,
                     7,5,3,1,
                    10,7,4,1))
feasibleSolution=vector([68,119,26,7,
        20,84,17,94,
        15,54,14,10,
        5,29,14,16])

StdGBIP.SolveOptimizationProblem(A,optimizationOrder,feasibleSolution)

print(time.time() - start)#measuring the time









    



Size of the Grobner basis of I_t: 127
Size of the Valuable Grobner basis of I_t: 36
Feasible Solution:(68, 119, 26, 7, 20, 84, 17, 94, 15, 54, 14, 10, 5, 29, 14, 16)
Optimal Solution:
x1^108*x2^112*x6^174*x7^41*x11^30*x12^63*x16^64
0.320125818253

Алгоритм 2



In [11]:

    
load("QuotGBIP.sage")

start = time.time()#measuring the time

#first row is for t
optimizationOrder=TermOrder('wdeglex',(
                     1,1,1,1,
                     4,3,2,1,
                     7,5,3,1,
                    10,7,4,1))
feasibleSolution=vector([68,119,26,7,
        20,84,17,94,
        15,54,14,10,
        5,29,14,16])

QuotGBIP.SolveOptimizationProblem(A,optimizationOrder,feasibleSolution)

print(time.time() - start)#measuring the time









    



t,x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15,x16
Size of the Grobner basis of I_t: 93
Size of the Valuable Grobner basis of I_t: 36
Feasible Solution:(68, 119, 26, 7, 20, 84, 17, 94, 15, 54, 14, 10, 5, 29, 14, 16)
Optimal Solution:
x1^108*x2^112*x6^174*x7^41*x11^30*x12^63*x16^64
0.230621099472

Алгоритм 3



In [52]:

    
load("LatticeBuchberger.sage")

start = time.time()#measuring the time

#first row is for t
optimizationOrder=['deglex',vector([
                     1,1,1,1,
                     4,3,2,1,
                     7,5,3,1,
                    10,7,4,1])]
feasibleSolution=vector([68,119,26,7, 20,84,17,94, 15,54,14,10, 5,29,14,16])

LatticeBuchberger.SolveOptimizationProblem(A,optimizationOrder,feasibleSolution)

print(time.time() - start)#measuring the time









    



[ 1  0  0 -1  0  0  0  0  0  0  0  0 -1  0  0  1]
[ 0  1  0 -1  0  0  0  0  0  0  0  0  0 -1  0  1]
[ 0  0  1 -1  0  0  0  0  0  0  0  0  0  0 -1  1]
[ 0  0  0  0  1  0  0 -1  0  0  0  0 -1  0  0  1]
[ 0  0  0  0  0  1  0 -1  0  0  0  0  0 -1  0  1]
[ 0  0  0  0  0  0  1 -1  0  0  0  0  0  0 -1  1]
[ 0  0  0  0  0  0  0  0  1  0  0 -1 -1  0  0  1]
[ 0  0  0  0  0  0  0  0  0  1  0 -1  0 -1  0  1]
[ 0  0  0  0  0  0  0  0  0  0  1 -1  0  0 -1  1]
Buchberger.....
10
33
47
59
75
95
101
103
105
107
107
Filtering...
36
Minimize....
36
(69, 119, 26, 6, 20, 84, 17, 94, 15, 54, 14, 10, 4, 29, 14, 17)
(73, 121, 26, 0, 20, 88, 17, 90, 15, 54, 14, 10, 0, 23, 14, 27)
(73, 121, 26, 0, 20, 98, 17, 80, 15, 54, 14, 10, 0, 13, 14, 37)
(73, 121, 26, 0, 20, 108, 17, 70, 15, 54, 14, 10, 0, 3, 14, 47)
(73, 121, 26, 0, 20, 111, 24, 60, 15, 54, 14, 10, 0, 0, 7, 57)
(73, 121, 26, 0, 23, 111, 31, 50, 12, 54, 14, 13, 0, 0, 0, 64)
(73, 121, 26, 0, 33, 111, 31, 40, 2, 54, 14, 23, 0, 0, 0, 64)
(73, 121, 26, 0, 35, 119, 31, 30, 0, 46, 14, 33, 0, 0, 0, 64)
(73, 121, 26, 0, 35, 129, 31, 20, 0, 36, 14, 43, 0, 0, 0, 64)
(73, 121, 26, 0, 35, 139, 31, 10, 0, 26, 14, 53, 0, 0, 0, 64)
(73, 121, 26, 0, 35, 149, 31, 0, 0, 16, 14, 63, 0, 0, 0, 64)
(83, 111, 26, 0, 25, 159, 31, 0, 0, 16, 14, 63, 0, 0, 0, 64)
(93, 101, 26, 0, 15, 169, 31, 0, 0, 16, 14, 63, 0, 0, 0, 64)
(103, 91, 26, 0, 5, 179, 31, 0, 0, 16, 14, 63, 0, 0, 0, 64)
(108, 91, 21, 0, 0, 179, 36, 0, 0, 16, 14, 63, 0, 0, 0, 64)
(108, 101, 11, 0, 0, 169, 46, 0, 0, 16, 14, 63, 0, 0, 0, 64)
(108, 111, 1, 0, 0, 159, 56, 0, 0, 16, 14, 63, 0, 0, 0, 64)
(108, 112, 0, 0, 0, 167, 48, 0, 0, 7, 23, 63, 0, 0, 0, 64)
('opt', (108, 112, 0, 0, 0, 174, 41, 0, 0, 0, 30, 63, 0, 0, 0, 64))
22.6999659538



In [ ]: