ortools解决LP问题

ortools解决LP问题

ojAlgo可以整合ortools，使用ojAlgo来进行约束条件的模型构造，而使用ortools进行求解。因为我们一开始使用的是ojAlgo，这样可以更小幅度的修改，只需要求解时使用ortools就可以

<dependency>
  <groupId>org.ojalgo</groupId>
  <artifactId>ojalgo</artifactId>
  <version>51.4.1</version>
</dependency>

<!-- https://mvnrepository.com/artifact/com.google.ortools/ortools-java -->
<dependency>
  <groupId>com.google.ortools</groupId>
  <artifactId>ortools-java</artifactId>
  <version>8.2.9025</version>
</dependency>

还是以求解 5x1 + 6x2 + 23x3 + 5x4 + 24x5 + 6x6 + 23x7 + 5x8的最小值为例

ExpressionsBasedModel model = new ExpressionsBasedModel();
model.addVariable(Variable.makeInteger("x"+1).lower(0).weight(5));
model.addVariable(Variable.makeInteger("x"+2).lower(0).weight(6));
model.addVariable(Variable.makeInteger("x"+3).lower(0).weight(23));
model.addVariable(Variable.makeInteger("x"+4).lower(0).weight(5));
model.addVariable(Variable.makeInteger("x"+5).lower(0).weight(24));
model.addVariable(Variable.makeInteger("x"+6).lower(0).weight(6));
model.addVariable(Variable.makeInteger("x"+7).lower(0).weight(23));
model.addVariable(Variable.makeInteger("x"+8).lower(0).weight(5));

// 约束1 2x1+x2+x3+x4>=100
Expression expression = model.addExpression("e" + 1);
expression.set(0,2);
expression.set(1,1);
expression.set(2,1);
expression.set(3,1);
expression.lower(100);

// 约束2 x2+x3+3x5+2x6+x7>=150
Expression expression2 = model.addExpression("e" + 2);
expression2.set(1,2);
expression2.set(2,1);
expression2.set(4,3);
expression2.set(5,2);
expression2.set(6,1);
expression2.lower(150);

// 约束3 x1+x3+3x4+2x6+3x7+5x8>=100
Expression expression3 = model.addExpression("e" + 3);
expression3.set(0,1);
expression3.set(2,1);
expression3.set(3,3);
expression3.set(5,2);
expression3.set(6,3);
expression3.set(7,5);
expression3.lower(100);

SolverORTools tools = SolverORTools.INTEGRATION.build(model);
Optimisation.Result result = tools.solve(null);
System.out.println(result);

可以发现，业务部分上面构造model的地方一点都没有动，只是改了solve的地方

SolverORTools是自己写的Solver，这点ojAlgo做的还是比较好的，插件式的求解器

public final class SolverORTools implements Optimisation.Solver {
    public static final SolverORTools.Integration INTEGRATION = new SolverORTools.Integration();
    static final SolverORTools.Configurator DEFAULT = (solver, options) -> {
    };
    private final MPSolver mySolver;
    private final MPVariable[] myVariables;

    static MPSolver newSolver(ExpressionsBasedModel model) {
        return MPSolver.createSolver("SCIP");
    }

    static State translate(MPSolver.ResultStatus status) {
        switch(status) {
            case NOT_SOLVED:
                return State.UNEXPLORED;
//            case MODEL_INVALID:
//                return State.INVALID;
            case ABNORMAL:
                return State.FAILED;
            case UNBOUNDED:
            case INFEASIBLE:
                return State.INFEASIBLE;
            case FEASIBLE:
                return State.FEASIBLE;
            case OPTIMAL:
                return State.OPTIMAL;
            default:
                return State.FAILED;
        }
    }

    SolverORTools(MPSolver solver, MPVariable[] variables) {
        this.myVariables = variables;
        this.mySolver = solver;
    }

    public void dispose() {

        if (mySolver != null) {
            mySolver.delete();
        }

    }

    public Result solve(Result kickStarter) {
        try{
            State retState = translate(mySolver.solve());
            double retValue = mySolver.objective().value();
            double[] retSolution = new double[myVariables.length];
            if (retState.isFeasible()) {
                for(int i = 0; i < retSolution.length; ++i) {
                    retSolution[i] = myVariables[i].solutionValue();
                }
            }

            return Result.of(retValue, retState, retSolution);
        } catch (Exception e){
            e.printStackTrace();
            return null;
        }

    }

    static {
        Loader.loadNativeLibraries();
    }

    public static final class Integration extends org.ojalgo.optimisation.ExpressionsBasedModel.Integration<SolverORTools> {
        Integration() {
        }

        public SolverORTools build(ExpressionsBasedModel model) {
            // 是否有整型变量
            boolean mip = model.isAnyVariableInteger();
            MPSolver solver = SolverORTools.newSolver(model);

            // 参数
            List<Variable> mVars = model.getVariables();
            int nbVars = mVars.size();
            double posInf = MPSolver.infinity();
            double negInf = -posInf;
            MPVariable[] sVars = new MPVariable[nbVars];

            for(int i = 0; i < nbVars; ++i) {
                Variable mVar = mVars.get(i);
                BigDecimal lb = mVar.getLowerLimit() == null ? BigDecimal.ZERO : mVar.getLowerLimit();
                BigDecimal ub = mVar.getUpperLimit() == null ? BigDecimal.valueOf(Integer.MAX_VALUE) : mVar.getUpperLimit();
                // 整型变量
                boolean integer = mip && mVar.isInteger();
                String name = mVar.getName();
                sVars[i] = solver.makeVar(lb.doubleValue(), ub.doubleValue(), integer, name);
            }
            List<Expression> constraints = model.constraints().collect(Collectors.toList());

            model.constraints().forEach((mConstr) -> {
                BigDecimal lb = mConstr.getLowerLimit() == null ? BigDecimal.valueOf(Integer.MIN_VALUE) : mConstr.getLowerLimit();
                BigDecimal ub = mConstr.getUpperLimit() == null ? BigDecimal.valueOf(Integer.MAX_VALUE) : mConstr.getUpperLimit();
                String name = mConstr.getName();
                MPConstraint sConstr = solver.makeConstraint(lb.doubleValue(), ub.doubleValue(), name);
                Iterator<Structure1D.IntIndex> iterator = mConstr.getLinearKeySet().iterator();

                while(iterator.hasNext()) {
                    Structure1D.IntIndex key = iterator.next();
                    sConstr.setCoefficient(sVars[key.index], mConstr.get(key).doubleValue());
                }

            });
            Expression mObj = model.objective();
            MPObjective sObj = solver.objective();
            sObj.setOptimizationDirection(model.getOptimisationSense() == Sense.MAX);
            Iterator var21 = mObj.getLinearKeySet().iterator();

            while(var21.hasNext()) {
                IntIndex key = (IntIndex)var21.next();
                sObj.setCoefficient(sVars[key.index], mObj.get(key).doubleValue());
            }

            SolverORTools.DEFAULT.configure(solver, model.options);
            model.options.getConfigurator(SolverORTools.Configurator.class).ifPresent((c) -> {
                c.configure(solver, model.options);
            });
            return new SolverORTools(solver, sVars);
        }

        public boolean isCapable(ExpressionsBasedModel model) {
            return !model.isAnyExpressionQuadratic();
        }

        protected boolean isSolutionMapped() {
            return false;
        }
    }

    @FunctionalInterface
    public interface Configurator {
        void configure(MPSolver solver, Options options);
    }
}

底层使用的是SCIP

MPSolver.createSolver("SCIP")

为了解决混合整数规划问题，OR-Tools也提供了几种工具：

• MPSolver：MPSolver接口可用于解决LP问题和MIP问题，因此其中同样包含几个第三方MIP求解器(CBC、SCIP、GLPK、Gurobi)。OR-Tools实际上提供的是统一的求解器接口，内部连接的求解器可以自己配置，默认连接CBC求解器。
• CP-SAT：它是使用SAT(satisfiability)方法的约束规划求解器，是原始约束规划求解器(CP Solver)的高级版。为了提高计算速度，CP-SAT求解器仅处理整数，这意味着必须使用整数来定义优化问题，如果从具有非整数项约束的问题开始，则需要将约束乘以一个足够大的整数，以便所有项都是整数。

在这里我们使用了MPSolver接口，ortools内置了SCIP，不需要在服务器上安装SCIP(安装过程比较复杂)，且集合了各种先进的优化算法，它所包含的求解器主要分为约束规划、线性和整数规划、车辆路径规划以及图论算法这四个基本求解器，能够按照优化问题的类型，提供相对应的不同类和接口。