线性规划约束的定义问题

Question

我和我的朋友正在尝试实现一个纸，最后一步需要解决一个线性规划问题才能得到最终的结果。我们对LP不太熟悉，所以我想寻求您的帮助。

下面是基于PROFSET模型的函数

​

​

下面是建议的约束

(1)

​

​

(2)

​

​

其中：

1. Pa和Qi是二元决策变量。
2. J是所有可用的类别
3. F是频繁范畴的集合。
4. Φ是选定类别的总数。

约束(1)实际上表示，如果在某些项集A中包含了范畴I，则气是1，其中Pa =1。

基本上，我们试图使用一些常见的开源lp解决程序(比如joptimizer)，但是我们不知道如何定义这些约束，特别是那些定义集包含规则的约束。这些解决方案中的大多数人似乎只接受不平等。

那么，您知道如何定义这些约束吗？或者把它们转化成不平等什么的？任何帮助都将不胜感激。

谢谢

Answer 1

写成等式的约束也可以写成两个不等式。例如：

• A*x=b与
• A*x<=b和A*x>=b

为了写出这样的LP，有两种方法。

1. 要对其进行硬编码，意味着用代码编写所有东西，例如用Java编写。
2. 用一种名为AMPL：https://ampl.com/resources/the-ampl-book/的“语言”来编写它，作为第二种方式，您不需要真正了解一种编程语言。AMPL将您的LP神奇地转换为代码，并将其提供给一个解决程序，例如: CPLEX、Gurobi (可获得的学术许可)或开源: GLPK。AMPL还提供了一个在线平台，您可以将模型作为.mod文件提供，数据以.dat文件的形式提供。

如果你仍然想硬编码，你的LP GLPK有很好的例子，例如在JAVA中：

public class Lp {
    //  Minimize z = -.5 * x1 + .5 * x2 - x3 + 1
    //
    //  subject to
    //  0.0 <= x1 - .5 * x2 <= 0.2
    //  -x2 + x3 <= 0.4
    //  where,
    //  0.0 <= x1 <= 0.5
    //  0.0 <= x2 <= 0.5
    //  0.0 <= x3 <= 0.5

public static void main(String[] arg) {
    glp_prob lp;
    glp_smcp parm;
    SWIGTYPE_p_int ind;
    SWIGTYPE_p_double val;
    int ret;

    try {
        // Create problem
        lp = GLPK.glp_create_prob();
        System.out.println("Problem created");
        GLPK.glp_set_prob_name(lp, "myProblem");

        // Define columns
        GLPK.glp_add_cols(lp, 3);
        GLPK.glp_set_col_name(lp, 1, "x1");
        GLPK.glp_set_col_kind(lp, 1, GLPKConstants.GLP_CV);
        GLPK.glp_set_col_bnds(lp, 1, GLPKConstants.GLP_DB, 0, .5);
        GLPK.glp_set_col_name(lp, 2, "x2");
        GLPK.glp_set_col_kind(lp, 2, GLPKConstants.GLP_CV);
        GLPK.glp_set_col_bnds(lp, 2, GLPKConstants.GLP_DB, 0, .5);
        GLPK.glp_set_col_name(lp, 3, "x3");
        GLPK.glp_set_col_kind(lp, 3, GLPKConstants.GLP_CV);
        GLPK.glp_set_col_bnds(lp, 3, GLPKConstants.GLP_DB, 0, .5);

        // Create constraints

        // Allocate memory
        ind = GLPK.new_intArray(3);
        val = GLPK.new_doubleArray(3);

        // Create rows
        GLPK.glp_add_rows(lp, 2);

        // Set row details
        GLPK.glp_set_row_name(lp, 1, "c1");
        GLPK.glp_set_row_bnds(lp, 1, GLPKConstants.GLP_DB, 0, 0.2);
        GLPK.intArray_setitem(ind, 1, 1);
        GLPK.intArray_setitem(ind, 2, 2);
        GLPK.doubleArray_setitem(val, 1, 1.);
        GLPK.doubleArray_setitem(val, 2, -.5);
        GLPK.glp_set_mat_row(lp, 1, 2, ind, val);

        GLPK.glp_set_row_name(lp, 2, "c2");
        GLPK.glp_set_row_bnds(lp, 2, GLPKConstants.GLP_UP, 0, 0.4);
        GLPK.intArray_setitem(ind, 1, 2);
        GLPK.intArray_setitem(ind, 2, 3);
        GLPK.doubleArray_setitem(val, 1, -1.);
        GLPK.doubleArray_setitem(val, 2, 1.);
        GLPK.glp_set_mat_row(lp, 2, 2, ind, val);

        // Free memory
        GLPK.delete_intArray(ind);
        GLPK.delete_doubleArray(val);

        // Define objective
        GLPK.glp_set_obj_name(lp, "z");
        GLPK.glp_set_obj_dir(lp, GLPKConstants.GLP_MIN);
        GLPK.glp_set_obj_coef(lp, 0, 1.);
        GLPK.glp_set_obj_coef(lp, 1, -.5);
        GLPK.glp_set_obj_coef(lp, 2, .5);
        GLPK.glp_set_obj_coef(lp, 3, -1);

        // Write model to file
        // GLPK.glp_write_lp(lp, null, "lp.lp");

        // Solve model
        parm = new glp_smcp();
        GLPK.glp_init_smcp(parm);
        ret = GLPK.glp_simplex(lp, parm);

        // Retrieve solution
        if (ret == 0) {
            write_lp_solution(lp);
        } else {
            System.out.println("The problem could not be solved");
        }

        // Free memory
        GLPK.glp_delete_prob(lp);
    } catch (GlpkException ex) {
        ex.printStackTrace();
    ret = 1;
    }
System.exit(ret);
}

/**
 * write simplex solution
 * @param lp problem
 */
static void write_lp_solution(glp_prob lp) {
    int i;
    int n;
    String name;
    double val;

    name = GLPK.glp_get_obj_name(lp);
    val = GLPK.glp_get_obj_val(lp);
    System.out.print(name);
    System.out.print(" = ");
    System.out.println(val);
    n = GLPK.glp_get_num_cols(lp);
    for (i = 1; i <= n; i++) {
        name = GLPK.glp_get_col_name(lp, i);
        val = GLPK.glp_get_col_prim(lp, i);
        System.out.print(name);
        System.out.print(" = ");
        System.out.println(val);
    }
}}