Java 的 GLPK - 二进制变量 MIP 给出小数结果

Question

我正在尝试使用 GLPK 为 Java (http://glpk-java.sourceforge.net/) 解决基于二进制变量的线性规划问题，但计算结果给出了变量的小数结果。

我省略了大部分代码，但重要的是下面的部分，我将变量定义为二进制

GLPK.glp_add_cols(lp, data.size());
for (int i = 0; i < data.size(); i++) {
            GLPK.glp_set_col_name(lp, i + 1, "x" + (i + 1));
            GLPK.glp_set_col_kind(lp, i + 1, GLPKConstants.GLP_BV);
            }

数据是包含系数的table。

如果我尝试使用预求解器解决问题

glp_iocp iocpParm = new glp_iocp();
iocpParm.setPresolve(GLPK.GLP_ON);
GLPK.glp_init_iocp(iocpParm);
ret = GLPK.glp_intopt(lp, iocpParm);

结果出错

glp_intopt: optimal basis to initial LP relaxation not provided
The   problem   could  not  be  solved

如果我使用单纯形法添加预处理（按照文档的建议）

glp_smcp smcpParm = new glp_smcp();
GLPK.glp_init_smcp(smcpParm);
GLPK.glp_simplex(lp, smcpParm);

结果是分数

Problem   created 
GLPK Simplex Optimizer, v4.63
1 row, 4 columns, 4 non-zeros
      0: obj =   0.000000000e+00 inf =   1.231e+03 (1)
      1: obj =   1.231000000e+03 inf =   0.000e+00 (0)
OPTIMAL LP SOLUTION FOUND
GLPK Integer Optimizer, v4.63
1 row, 4 columns, 4 non-zeros
4 integer variables, all of which are binary
Integer optimization begins...
+     1: mip =     not found yet >=              -inf        (1; 0)
Solution found by heuristic: 1600
+     2: >>>>>   1.400000000e+03 >=   1.400000000e+03   0.0% (1; 0)
+     2: mip =   1.400000000e+03 >=     tree is empty   0.0% (0; 1)
INTEGER OPTIMAL SOLUTION FOUND
z = 1231.0
x1 = 0.769375
x2 = 0.0
x3 = 0.0
x4 = 0.0

如何获得二进制解决方案？

Answer 1

GLPK 为不同类型的求解器（MIP、内点、单纯形）保留单独的结果，因此要获得特定求解器的结果，必须使用相应的函数。

要使用单纯形求解器获得结果，请使用 glp_get 函数。
对于内部指针求解器，使用 glp_ipt 函数。
对于 MIP 求解器，使用 glp_mip 函数。

函数名的其余部分有点不一致。

Java 的 GLPK - 二进制变量 MIP 给出小数结果

GLPK for Java - Binary variable MIP gives fractional result

java

binary-data

linear-programming

glpk