GLPK線性規劃

Question

我正在處理一些非常大規模的線性規劃問題。 （矩陣目前大致爲1000x1000，這些都是'迷你'）。

我以爲我的程序運行成功，只有我意識到我得到了一些非常不直觀的答案。例如，假設我將x + y + z最大化，並受到一組約束條件的約束x + y < 10和y + z < 5.我運行此並獲得最佳解決方案。然後，我運行相同的方程，但具有不同的約束：x + y < 20和y + z < 5.然而在第二次迭代中，我的最大化減少了！

我苦心經歷並向我保證約束正確加載。

有誰知道這個問題可能是什麼？

我在關於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) 

Answer 1

首先解決有問題的實例與不同的求解器並檢查目標函數值。如果您可以將您的模型導出爲.mps格式（我不知道如何使用GLPK執行此操作，對不起），您可以將mps文件上傳到http://www.neos-server.org/neos/solvers/index.html，並使用幾種不同的LP解算器解決此問題。