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，然后用几种不同的线性规划求解器来解决它。