Java Cplex 降低最优性和第一个可行的解决方案

Question

我正在开发一个用 Java 编写的 LP 并使用 cplex 作为求解器。找到最佳解决方案需要一些时间。如果我有一个计算速度更快的可行解决方案或者只是一个优化性降低的解决方案就足够了。

在CPLEX用户手册中我发现了以下两个参数:

为了实现最优: https://www.ibm.com/support/knowledgecenter/SSSA5P_12.7.0/ilog.odms.cplex.help/CPLEX/Parameters/topics/EpOpt.html

cplex.setParam(IloCplex.Param.Simplex.Tolerances.Optimality, 1.0e-1);

对于第一个可行的解决方案:

cplex.setParam(IloCplex.Param.MIP.Limits.Solutions, 1);

我在模型中使用了这两个参数，但目标函数的解以及计算时间保持不变。

此外，我在下面的小LP中也使用过它们，但没有成功。

package cplexTest;

import ilog.concert.*;
import ilog.cplex.*;

public class TestC {
    public static void main (String[] args) {
       model1();
}

   public static void model1() {
       try {
           IloCplex cplex = new IloCplex();
           cplex.setParam(IloCplex.Param.Simplex.Tolerances.Optimality, 1.0e-1);
           cplex.setParam(IloCplex.Param.MIP.Limits.Solutions, 100);

           //variables
           IloNumVar x = cplex.numVar(0, Double.MAX_VALUE, "x");
           IloNumVar y = cplex.numVar(0, Double.MAX_VALUE, "y");

           //expressions
           IloLinearNumExpr objective = cplex.linearNumExpr();
           objective.addTerm(0.12, x);
           objective.addTerm(0.15, y);

           // define objective
           cplex.addMinimize(objective);

           //define constraints
           cplex.addGe(cplex.sum(cplex.prod(60, x), cplex.prod(60, y)),300);
           cplex.addGe(cplex.sum(cplex.prod(12, x), cplex.prod(6, y)),36);
           cplex.addGe(cplex.sum(cplex.prod(10, x), cplex.prod(30, y)),90);

           //solve
           if (cplex.solve()) {
               System.out.println("obj = "+cplex.getObjValue());
               System.out.println("x = "+cplex.getValue(x));
               System.out.println("y = "+cplex.getValue(y));
           }
           else {
               System.out.println("Model not solved");
           }
       }
       catch (IloException exc) {
           exc.printStackTrace();
       }
   }
}

Answer 1

您可能应该发布日志以获得更好的答案，但我可以提出几点。

1. LP 通常求解速度很快。 MIP 可能会很慢。
2. 如果您的 LP 非常大，请尝试内点法。对于大型问题，内点(屏障)方法可以比原始或对偶单纯形法快得多。内点求解器还可以使用多个线程(单纯形仅是串行的)。
3. 对于非常大的 LP，您可能需要观察内存使用情况(特别是在使用并发 LP 方法时)。如果超出 RAM 大小，算法可能会开始“抖动”(由于通过虚拟内存使用磁盘 IO 而减慢速度)。因此，请关闭并发 LP，并仅使用最佳的 LP 算法。
4. 一般来说，您不应该对降低的成本容忍度进行修改，除非您确实有充分的理由这样做并且您知道自己在做什么。要找到一个可行的点，请删除您的目标。您还可以考虑使模型变得稀疏。
5. 解决方案限制适用于 MIP 模型，而不适用于 LP。