私はいくつかの非常に大規模な線形計画問題に取り組んでいます。(マトリックスは現在、およそ 1000x1000 であり、これらは「ミニ」のものです。)
プログラムが正常に実行されたと思っていましたが、非常に直感的でない答えが得られていることに気付きました。たとえば、一連の制約 x+y<10 および y+z <5 に従って、x+y+z を最大化するとします。これを実行すると、最適なソリューションが得られます。次に、同じ方程式を実行しますが、制約は異なります: x+y<20 および y+z<5。しかし、2 回目の反復では、最大化が減少します。
私は骨の折れる作業を行い、制約が正しくロードされていることを確認しました。
問題が何であるかを知っている人はいますか？
lpx_check_kkt に関するドキュメントで、ソリューションが正しいか信頼性が高い (または信頼性が低い) 可能性が高いことを示しているように見えるものを見つけましたが、その使用方法がわかりません。
試みたところ、lpx_check_kkt が定義されていないというエラー メッセージが表示されました。
誰かがエラーを見つけられることを期待して、補遺としていくつかのコードを追加しています。この結果は、最適解が見つかったと主張することです。それでも、上限を上げるたびに、最適ではなくなります。
境界が上昇し、下降していないことを確認しました。
size = 10000000+1
ia = intArray(size)
ja = intArray(size)
ar = doubleArray(size)
prob = glp_create_prob()
glp_set_prob_name(prob, "sample")
glp_set_obj_dir(prob, GLP_MAX)
glp_add_rows(prob, Num_constraints)
for x in range(Num_constraints):
Variables.add_variables(Constraints_for_simplex)
glp_set_row_name(prob, x+1, Variables.variers[x])
glp_set_row_bnds(prob, x+1, GLP_UP, 0, Constraints_for_simplex[x][1])
print 'we set the row_bnd for', x+1,' to ',Constraints_for_simplex[x][1]
glp_add_cols(prob, len(All_Loops))
for x in range(len(All_Loops)):
glp_set_col_name(prob, x+1, "".join(["x",str(x)]))
glp_set_col_bnds(prob,x+1,GLP_LO,0,0)
glp_set_obj_coef(prob,x+1,1)
for x in range(1,len(All_Loops)+1):
z=Constraints_for_simplex[0][0][x-1]
ia[x] = 1; ja[x] = x; ar[x] = z
x=len(All_Loops)+1
while x<Num_constraints + len(All_Loops):
for y in range(2, Num_constraints+1):
z=Constraints_for_simplex[y-1][0][0]
ia[x] = y; ja[x] =1 ; ar[x] = z
x+=1
x=Num_constraints+len(All_Loops)
while x <len(All_Loops)*(Num_constraints-1):
for z in range(2,len(All_Loops)+1):
for y in range(2,Num_constraints+1):
if x<len(All_Loops)*Num_constraints+1:
q = Constraints_for_simplex[y-1][0][z-1]
ia[x] = y ; ja[x]=z; ar[x] = q
x+=1
glp_load_matrix(prob, len(All_Loops)*Num_constraints, ia, ja, ar)
glp_exact(prob,None)
Z = glp_get_obj_val(prob)