ortools解决LP问题

发表于 2021-04-24 更新于 2025-08-17 分类于数据结构与算法 Waline：阅读次数：本文字数： 7.9k 阅读时长 ≈ 7 分钟

使用 ojAlgo+OR-Tools 求解线性规划（LP）问题

OR-Tools（Google Optimization Tools）是谷歌开源的优化工具库，支持线性规划（LP）、混合整数规划（MIP）等多种问题，内置 CBC、SCIP 等高效求解器。结合 ojAlgo 的模型构建能力与 OR-Tools 的求解能力，可在最小化代码修改的前提下，提升复杂优化问题的求解效率。本文以具体示例介绍这种整合方案。

方案优势

模型构建复用：用 ojAlgo 的直观 API 定义变量和约束，无需重写模型逻辑。
求解能力增强：OR-Tools 支持多种高效求解器（如 SCIP、CBC），尤其擅长处理大规模整数规划问题。
低侵入性：仅需修改求解部分代码，业务逻辑（变量、约束定义）保持不变。

环境配置

依赖引入

在pom.xml中添加 ojAlgo 和 OR-Tools 的依赖：

<!-- ojAlgo：模型构建 -->
<dependency>
    <groupId>org.ojalgo</groupId>
    <artifactId>ojAlgo</artifactId>
    <version>51.4.1</version>
</dependency>

<!-- OR-Tools：求解器 -->
<dependency>
    <groupId>com.google.ortools</groupId>
    <artifactId>ortools-java</artifactId>
    <version>8.2.9025</version>
</dependency>

问题定义

求解以下整数线性规划问题（与前文 ojAlgo 示例一致）：
目标函数：minimize 5x₁ + 6x₂ + 23x₃ + 5x₄ + 24x₅ + 6x₆ + 23x₇ + 5x₈
约束条件：

2x₁ + x₂ + x₃ + x₄ ≥ 100
2x₂ + x₃ + 3x₅ + 2x₆ + x₇ ≥ 150
x₁ + x₃ + 3x₄ + 2x₆ + 3x₇ + 5x₈ ≥ 100
变量约束：所有变量为非负整数（xᵢ ≥ 0且为整数）

代码实现与解析

核心逻辑

用 ojAlgo 构建模型：定义变量、目标函数和约束条件（与纯 ojAlgo 方案完全一致）。
用 OR-Tools 求解：通过自定义的SolverORTools类，将 ojAlgo 模型转换为 OR-Tools 可处理的格式，调用 SCIP 求解器求解。

完整代码

1. 模型构建与求解入口

import org.ojalgo.optimisation.ExpressionsBasedModel;
import org.ojalgo.optimisation.Expression;
import org.ojalgo.optimisation.Optimisation;
import org.ojalgo.optimisation.Variable;

public class OjAlgoOrToolsDemo {
    public static void main(String[] args) {
        // 1. 用ojAlgo构建模型（与纯ojAlgo方案完全一致）
        ExpressionsBasedModel model = new ExpressionsBasedModel();

        // 添加变量（非负整数，权重为目标函数系数）
        model.addVariable(Variable.makeInteger("x1").lower(0).weight(5));
        model.addVariable(Variable.makeInteger("x2").lower(0).weight(6));
        model.addVariable(Variable.makeInteger("x3").lower(0).weight(23));
        model.addVariable(Variable.makeInteger("x4").lower(0).weight(5));
        model.addVariable(Variable.makeInteger("x5").lower(0).weight(24));
        model.addVariable(Variable.makeInteger("x6").lower(0).weight(6));
        model.addVariable(Variable.makeInteger("x7").lower(0).weight(23));
        model.addVariable(Variable.makeInteger("x8").lower(0).weight(5));

        // 约束1：2x1 + x2 + x3 + x4 ≥ 100
        Expression constraint1 = model.addExpression("constraint1");
        constraint1.set(0, 2); // x1系数
        constraint1.set(1, 1); // x2系数
        constraint1.set(2, 1); // x3系数
        constraint1.set(3, 1); // x4系数
        constraint1.lower(100);

        // 约束2：2x2 + x3 + 3x5 + 2x6 + x7 ≥ 150
        Expression constraint2 = model.addExpression("constraint2");
        constraint2.set(1, 2); // x2系数
        constraint2.set(2, 1); // x3系数
        constraint2.set(4, 3); // x5系数
        constraint2.set(5, 2); // x6系数
        constraint2.set(6, 1); // x7系数
        constraint2.lower(150);

        // 约束3：x1 + x3 + 3x4 + 2x6 + 3x7 + 5x8 ≥ 100
        Expression constraint3 = model.addExpression("constraint3");
        constraint3.set(0, 1); // x1系数
        constraint3.set(2, 1); // x3系数
        constraint3.set(3, 3); // x4系数
        constraint3.set(5, 2); // x6系数
        constraint3.set(6, 3); // x7系数
        constraint3.set(7, 5); // x8系数
        constraint3.lower(100);

        // 2. 用OR-Tools求解（仅修改求解部分）
        SolverORTools solver = SolverORTools.INTEGRATION.build(model);
        Optimisation.Result result = solver.solve(null);

        // 3. 输出结果
        System.out.println("求解状态：" + result.getState()); // 最优状态为OPTIMAL
        System.out.println("目标函数最小值：" + result.getValue());
        System.out.println("变量最优解：");
        double[] solution = result.getSolution();
        for (int i = 0; i < solution.length; i++) {
            System.out.println("x" + (i + 1) + " = " + solution[i]);
        }
    }
}

2. 整合工具类`SolverORTools`

该类负责将 ojAlgo 模型转换为 OR-Tools 的MPSolver可处理的格式，是连接两者的核心：

import com.google.ortools.Loader;
import com.google.ortools.linearsolver.MPConstraint;
import com.google.ortools.linearsolver.MPObjective;
import com.google.ortools.linearsolver.MPSolver;
import com.google.ortools.linearsolver.MPVariable;
import org.ojalgo.optimisation.*;
import org.ojalgo.structure.IntIndex;
import org.ojalgo.structure.Structure1D;

import java.math.BigDecimal;
import java.util.Iterator;
import java.util.List;
import java.util.stream.Collectors;

public final class SolverORTools implements Optimisation.Solver {
    public static final Integration INTEGRATION = new Integration();
    private final MPSolver solver;
    private final MPVariable[] variables;

    // 静态加载OR-Tools原生库
    static {
        Loader.loadNativeLibraries();
    }

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

    // 求解方法
    @Override
    public Result solve(Result kickStarter) {
        try {
            // 调用OR-Tools求解器
            MPSolver.ResultStatus status = solver.solve();
            // 转换求解状态（OR-Tools状态 → ojAlgo状态）
            State state = translate(status);
            // 获取目标函数值
            double objectiveValue = solver.objective().value();
            // 获取变量解
            double[] solution = new double[variables.length];
            if (state.isFeasible()) {
                for (int i = 0; i < variables.length; i++) {
                    solution[i] = variables[i].solutionValue();
                }
            }
            return Result.of(objectiveValue, state, solution);
        } catch (Exception e) {
            e.printStackTrace();
            return null;
        }
    }

    // 状态转换（OR-Tools → ojAlgo）
    private static State translate(MPSolver.ResultStatus status) {
        switch (status) {
            case OPTIMAL:
                return State.OPTIMAL;
            case FEASIBLE:
                return State.FEASIBLE;
            case INFEASIBLE:
            case UNBOUNDED:
                return State.INFEASIBLE;
            default:
                return State.FAILED;
        }
    }

    @Override
    public void dispose() {
        if (solver != null) {
            solver.delete();
        }
    }

    // 整合器：将ojAlgo模型转换为OR-Tools模型
    public static class Integration extends ExpressionsBasedModel.Integration<SolverORTools> {
        @Override
        public SolverORTools build(ExpressionsBasedModel model) {
            // 创建OR-Tools求解器（使用SCIP）
            MPSolver solver = MPSolver.createSolver("SCIP");
            if (solver == null) {
                throw new RuntimeException("无法创建SCIP求解器");
            }

            // 1. 转换变量（ojAlgo Variable → OR-Tools MPVariable）
            List<Variable> ojVariables = model.getVariables();
            int varCount = ojVariables.size();
            MPVariable[] mpVariables = new MPVariable[varCount];
            double infinity = MPSolver.infinity();

            for (int i = 0; i < varCount; i++) {
                Variable var = ojVariables.get(i);
                // 变量下界（默认0）
                double lower = var.getLowerLimit() != null ? var.getLowerLimit().doubleValue() : 0;
                // 变量上界（默认无穷大）
                double upper = var.getUpperLimit() != null ? var.getUpperLimit().doubleValue() : infinity;
                // 是否为整数变量
                boolean isInteger = var.isInteger();
                // 创建OR-Tools变量
                mpVariables[i] = solver.makeVar(lower, upper, isInteger, var.getName());
            }

            // 2. 转换约束（ojAlgo Expression → OR-Tools MPConstraint）
            List<Expression> constraints = model.constraints().collect(Collectors.toList());
            for (Expression expr : constraints) {
                // 约束下界（默认负无穷）
                double lower = expr.getLowerLimit() != null ? expr.getLowerLimit().doubleValue() : -infinity;
                // 约束上界（默认正无穷）
                double upper = expr.getUpperLimit() != null ? expr.getUpperLimit().doubleValue() : infinity;
                // 创建OR-Tools约束
                MPConstraint mpConstraint = solver.makeConstraint(lower, upper, expr.getName());

                // 设置约束系数
                Iterator<Structure1D.IntIndex> iterator = expr.getLinearKeySet().iterator();
                while (iterator.hasNext()) {
                    IntIndex index = iterator.next();
                    int varIndex = index.index;
                    double coefficient = expr.get(index).doubleValue();
                    mpConstraint.setCoefficient(mpVariables[varIndex], coefficient);
                }
            }

            // 3. 转换目标函数
            Expression objective = model.objective();
            MPObjective mpObjective = solver.objective();
            // 设置优化方向（最小化/最大化）
            mpObjective.setOptimizationDirection(model.getOptimisationSense() == Sense.MAX);
            // 设置目标函数系数
            Iterator<Structure1D.IntIndex> objIterator = objective.getLinearKeySet().iterator();
            while (objIterator.hasNext()) {
                IntIndex index = objIterator.next();
                int varIndex = index.index;
                double coefficient = objective.get(index).doubleValue();
                mpObjective.setCoefficient(mpVariables[varIndex], coefficient);
            }

            return new SolverORTools(solver, mpVariables);
        }

        @Override
        public boolean isCapable(ExpressionsBasedModel model) {
            // 仅支持线性模型（非二次）
            return !model.isAnyExpressionQuadratic();
        }

        @Override
        protected boolean isSolutionMapped() {
            return false;
        }
    }
}

结果解析

输出结果

求解状态：OPTIMAL
目标函数最小值：600.0
变量最优解：
x1 = 30.0
x2 = 40.0
x3 = 0.0
x4 = 0.0
x5 = 0.0
x6 = 35.0
x7 = 0.0
x8 = 0.0

结果验证

目标函数值：5×30 + 6×40 + 6×35 = 150 + 240 + 210 = 600，符合最小值要求。
约束满足：三个约束均取等号（100、150、100），满足所有条件。

OR-Tools 的核心优势

多求解器支持：内置 CBC（默认）、SCIP、GLPK 等求解器，可根据问题类型切换（示例中用 SCIP）。
高效求解：针对大规模 MIP 问题优化，求解速度优于纯 ojAlgo。
无需单独安装求解器：OR-Tools 内置 SCIP 等求解器的二进制库，无需在服务器上手动安装。
扩展性强：支持约束规划（CP-SAT）、车辆路径规划（VRP）等复杂问题。

总结

通过 ojAlgo 构建模型、OR-Tools 求解的方案，兼顾了模型定义的简洁性和求解效率。这种整合方式特别适合：

已有 ojAlgo 模型代码，需提升求解性能的场景；
处理大规模整数规划或混合整数规划问题；
需要灵活切换求解器（如从 CBC 切换到 SCIP）的需求。

OR-Tools 的强大求解能力与 ojAlgo 的友好 API 结合，为 Java 优化问题提供了高效且易维护的解决方案