HiGHS - 线性优化软件

• 关于 HiGHS
• 文档
• 安装
  • 使用 CMake 从源代码构建
  • 使用 Meson 构建*
  • 使用 Nix 构建*
  • 预编译二进制文件
• 运行 HiGHS
• 接口
  • Python
  • C
  • C#
  • Fortran
• 参考资料

关于 HiGHS

HiGHS 是一款高性能的串行与并行求解器，适用于大规模稀疏线性优化问题，其形式如下：

$$\min \frac{1}{2}{x}^{T}Qx+c^{T}x\text{s.t.}L\le Ax\le U;l\le x\le u$$

其中，$Q$ 必须为半正定矩阵。若 $Q$ 为零矩阵，则部分变量可能需要取整数值。因此，HiGHS 能够求解线性规划（LP）问题、凸二次规划（QP）问题以及混合整数规划（MIP）问题。它主要采用 C++ 编写，同时包含少量 C 语言代码。已在多种 Linux、MacOS 和 Windows 系统环境下进行开发与测试，且无需第三方依赖。

HiGHS 拥有原始和对偶修正单纯形求解器，最初由 Qi Huangfu 编写，后经 Julian Hall 进一步开发。此外，它还包含由 Lukas Schork 编写的 LP 内点法求解器、Michael Feldmeier 编写的 QP 活动集求解器，以及 Leona Gottwald 编写的 MIP 求解器。Julian Hall 和 Ivet Galabova 也为 HiGHS 添加了其他功能，其中 Ivet Galabova 负责 HiGHS 的软件工程以及与 C、C#、FORTRAN、Julia 和 Python 的接口开发。

欲了解更多关于 HiGHS 的信息，请访问 https://www.highs.dev。

尽管 HiGHS 在 MIT 许可下免费提供，但我们非常乐意通过邮件 highsopt@gmail.com 了解用户的使用体验并提供建议。

文档

文档可在 https://ergo-code.github.io/HiGHS/ 获取。

安装

使用 CMake 从源代码构建

HiGHS 使用 CMake 作为构建系统，要求 CMake 版本至少为 3.15。要在名为“build”的新子目录中生成构建文件，请运行：

    cmake -S . -B build
    cmake --build build

这将安装可执行文件 bin/highs 和库 lib/highs。

要测试编译是否成功，请切换到构建目录并运行

    ctest

关于使用 CMake 构建的更多详细信息，请参见 HiGHS/cmake/README.md。

使用 Meson 构建

作为替代方案，可以使用 meson 构建界面安装 HiGHS：

meson setup bbdir -Dwith_tests=True
meson test -C bbdir

meson 构建文件由社区提供，HiGHS 开发团队不提供官方支持。 如果您使用此方法时遇到问题，请考虑通过查阅 HiGHS 贡献指南 来贡献修复或更新。

使用 Nix 构建

有一个 nix flake 提供了 highs 二进制文件：

nix run .

您甚至可以无需安装任何东西即可运行，前提是您已安装nix：

nix run github:ERGO-Code/HiGHS

nix flake 还提供了 python 包：

nix build .#highspy
tree result/

以及一个用于测试它的 devShell：

nix develop .#highspy
python
>>> import highspy
>>> highspy.Highs()

nix 构建文件由社区提供，HiGHS 开发团队不提供官方支持。

预编译二进制文件

预编译静态二进制文件可从 https://github.com/ERGO-Code/HiGHS/releases 获取。

此外，还有一个包含适用于 Windows x64 共享库的软件包。

*-mit 二进制软件包包含 HiGHS，并采用 MIT 许可。 *-apache 二进制软件包包含 HiGHS 及 HiPO，由于 HiPO 依赖项的许可限制，采用 Apache 许可。有关更多信息，请参阅 THIRD_PARTY_NOTICES.md。

如果您对更多平台和二进制文件有任何疑问或需求，请通过 hello@highs.dev 与我们联系。

运行 HiGHS

HiGHS 可以读取 MPS 文件和（CPLEX）LP 文件，以下命令用于求解 ml.mps 中的模型：

    highs ml.mps

命令行选项

当从命令行运行 HiGHS 时，一些基本选项值可直接指定。更多选项可通过文件进行指定。其使用格式如下：

$ bin/highs --help
usage:
      ./bin/highs [options] [file]

options:
      --model_file file          File of model to solve.
      --options_file file        File containing HiGHS options.
      --read_solution_file file  File of solution to read.
      --read_basis_file text     File of initial basis to read.
      --write_model_file text    File for writing out model.
      --solution_file text       File for writing out solution.
      --write_basis_file text    File for writing out final basis.
      --presolve text            Set presolve option to:
                                   "choose" * default
                                   "on"
                                   "off"
      --solver text              Set solver option to:
                                   "choose" * default
                                   "simplex"
                                   "ipm"
      --parallel text            Set parallel option to:
                                   "choose" * default
                                   "on"
                                   "off"
      --threads int              Set maximum number of threads to use:
                                 0: automatic * default
      --run_crossover text       Set run_crossover option to:
                                   "choose"
                                   "on" * default
                                   "off"
      --time_limit float         Run time limit (seconds - double).
      --random_seed int          Seed to initialize random number
                                 generation.
      --ranging text             Compute cost, bound, RHS and basic
                                 solution ranging:
                                   "on"
                                   "off" * default
  -v, --version                  Print version.
  -h, --help                     Print help.

有关选项的完整列表，请参阅文档网站的选项页面。

接口

HiGHS/highs/interfaces 目录下提供了适用于 C、C#、FORTRAN 和 Python 的 HiGHS 接口，HiGHS/examples/ 目录下包含示例驱动文件。有关语言和建模接口的更多信息，请访问 https://ergo-code.github.io/HiGHS/stable/interfaces/other/。

我们很乐意通过发送邮件至 highsopt@gmail.com 提供合理程度的支持。

Python

Python 包 highspy 是 HiGHS 的轻量级包装器，可在 PyPi 上获取。通过运行以下 pip 命令即可轻松安装：

$ pip install highspy

或者，也可以从源代码构建 highspy。下载 HiGHS 源代码并运行

pip install .

从根目录开始。

Python 包 highspy 依赖于 numpy 包，如果 numpy 尚未安装，它也会一并安装。

可以使用小型示例 HiGHS/examples/call_highs_from_python_highspy.py 来测试安装是否成功。

Google Colab 示例笔记本 也演示了如何调用 highspy。

要在 Python 中使用 HiPO，需要额外安装 highspy-extras。它包含 HiPO 的依赖项，并采用 Apache 2.0 许可。可以通过以下命令安装：

$ pip install highspy[extras]

有关更多详细信息，请参见 https://ergo-code.github.io/HiGHS/ 中的“Interfaces”->“Python”->“HiPO in Python”部分。

C

C API 位于 HiGHS/highs/interfaces/highs_c_api.h 中。默认构建中已包含此 API。有关更多详细信息，请查阅文档网站 https://ergo-code.github.io/HiGHS/。

CSharp

nuget 包 Highs.Native 可在 https://www.nuget.org 获取，具体链接为 https://www.nuget.org/packages/Highs.Native/。

可通过 dotnet 将其添加到您的 C# 项目中。

dotnet add package Highs.Native --version 1.15.1

此 nuget 包包含适用于以下平台的运行时库：

• win-x64
• win-x86
• linux-x64
• linux-arm64
• macos-x64
• macos-arm64

本地构建的详细信息可在 nuget/README.md 中找到。

Fortran

Fortran API 位于 HiGHS/highs/interfaces/highs_fortran_api.f90。它未包含在默认构建中。有关更多详细信息，请查阅文档网站 https://ergo-code.github.io/HiGHS/。

参考文献

如果您在学术环境中使用 HiGHS，请予以认可并引用以下文章。

Parallelizing the dual revised simplex method Q. Huangfu and J. A. J. Hall Mathematical Programming Computation, 10 (1), 119-142, 2018. DOI: 10.1007/s12532-017-0130-5