java - GLPK-Java 解决 MILP 类型问题

Question

虽然我已经知道没有太多关于使用 GLPK-Java 库的文档，但我还是要问...(不，我不能使用其他求解器)

我有一个涉及调度的基本问题。学生学期类(class)有一些基本限制。

示例问题是:

We consider {s1, s2} a set of two students. They need to take two
courses {c1, c2} during two semesters {t1, t2}.
We assume the courses are the same. We also assume that the students
cannot take more than one course per semester, and we'd like to determine the
minimum capacity X that must be offered by the classroom, assuming they
all offer the same capacity.

我们以 CPLEX 格式给出的示例如下所示:

minimize X

subject to
y111 + y112 = 1
y121 + y122 = 1
y211 + y212 = 1
y221 + y222 = 1
y111 + y112 <= 1
y121 + y122 <= 1
y211 + y212 <= 1
y221 + y222 <= 1
y111 + y112 -X <= 0
y121 + y122 -X <= 0
y211 + y212 -X <= 0
y221 + y222 -X <= 0

end

我可以通过 glpsol 命令通过求解器运行它并求解它，但我需要使用 API 编写它。我从来没有真正使用过线性规划，并且文档还有一些不足之处。虽然这充其量只是简单化，但真正的问题涉及解决超过 12 个学期的 600 名学生，他们必须选修 18 门类(class)中的 12 门，其中某些类(class)仅在某些学期可用，而某些类(class)有先决条件。

我需要什么帮助将简单的问题转化为使用 API 的编码示例。我假设一旦我看到非常简单的问题如何映射到 API 调用，我就可以弄清楚如何为更复杂的问题创建应用程序。

从库中的示例中我可以看到您设置了列，在本例中是学期，行是学生

// Define Columns
GLPK.glp_add_cols(lp, 2);   // adds the number of columns
GLPK.glp_set_col_name(lp, 1, "Sem_1");
GLPK.glp_set_col_kind(lp, 1, GLPKConstants.GLP_IV);
GLPK.glp_set_col_bnds(lp, 1, GLPKConstants.GLP_LO, 0, 0);

GLPK.glp_set_col_name(lp, 2, "Sem_2");
GLPK.glp_set_col_kind(lp, 2, GLPKConstants.GLP_IV);
GLPK.glp_set_col_bnds(lp, 2, GLPKConstants.GLP_LO, 0, 0);

此时我假设您需要设置行约束，但我不知所措。任何方向将不胜感激。

Answer 1

使用 API 时，优化问题基本上由问题矩阵表示，其中列是您的变量，行是您的约束。对于您的问题，您必须定义 9 列，代表 y111、y112、... 和 X。

然后您可以通过设置使用的变量(列)继续约束(行)

GLPK.glp_set_row_name(lp, 2, "constraint1");
GLPK.glp_set_row_bnds(lp, 2, GLPKConstants.GLP_FX, 0, 1.0); // equal to 1.0
GLPK.intArray_setitem(ind, 1, 1); // Add first column at first position
GLPK.intArray_setitem(ind, 2, 2); // Add second column at second position    
// set the coefficients to the variables (for all 1. except X is -1. in the example)
GLPK.doubleArray_setitem(val, 1, 1.); 
GLPK.doubleArray_setitem(val, 2, 1.);
GLPK.glp_set_mat_row(lp, 1, 2, ind, val);

这将代表 y111 + y112 = 1 约束 - 11 去。

在 GLPK for Java 包中还应该有一个 glpk 文档，其中包含 GLPK 函数的良好文档(在 glpk for java 中也可用)。另请查看 lp.java 示例。