ortools-线性规划求解高阶使用 - 文档翻译

以下翻译并不逐字翻译.

Advanced LP Solving

Despite the maturity of LP technology, some use cases require more advanced techniques. For example, a number of different LP algorithms and implementations are available, each of which has strengths and weaknesses. Furthermore, numerical instability can cause solvers to slow down or fail to solve certain models.

尽管线性规划求解器的技术已经非常成熟, 但是在一些案例中依然需要一些更为先进的技术. 例如, 在大量的不同线性规划的求解算法和其实现中, 不同的算法之间各有优劣. 此外, 数值的不稳定可能导致模型的求解非常缓慢或是无法求解.

This guide introduces the concepts and provides examples to help you get the most performance and reliability out of LP solvers.

以下将介绍相关的案列, 以充分了解各个线性求解算法的性能和可靠性

一. 前言

基础概念温习以及相关内容的了解.

1.1 对偶规划

dual programming

$原问题的标准形式:\\ \max\; z = \sum_{j=1}^nc_jx_j\\ s.t \begin{cases} \sum_{j = 1} ^ n a_{ij}x_j = b_i(i = 1, ..., m)\\ x_j \geq 0(j = 1, ..., n) \end{cases}\\ \\ 对偶问题(DLP):\\ \min\; w = \sum_{i = 1} ^ m b_iy_i\\ s.t \begin{cases} \sum_{i = 1} ^ m a_{ij}y_i \geq c_j(j = 1,...,n)\\ y_i\; 无约束 (i = 1, ..., m) \end{cases}$

1.2 单纯形法

单纯形法所遇到的问题

1.3 内点法

Interior Method

屏障法

Barrier Method

$\min_x f(x) \\ s.t. \quad h_i(x) \le 0, i = 1, \ldots, m\\ Ax = b$

1.4 线性规划算法的支持

• CLP_LINEAR_PROGRAMMING or CLP, clp线性规划求解器, https://www.coin-or.org/Clp/faq.html, 免费
• CBC_MIXED_INTEGER_PROGRAMMING or CBC, cbc混合整数求解器, 免费, https://coin-or.github.io/Cbc/intro.html
• GLOP_LINEAR_PROGRAMMING or GLOP, Google线性求解器, 免费
• BOP_INTEGER_PROGRAMMING or BOP, bop整数求解器
• SAT_INTEGER_PROGRAMMING or SAT or CP_SAT, sat整数求解器, http://match.stanford.edu/reference/index.html
• SCIP_MIXED_INTEGER_PROGRAMMING or SCIP, scip混合整数求解器
• GUROBI_LINEAR_PROGRAMMING or GUROBI_LP, GUROBI线性求解器, 商业
• GUROBI_MIXED_INTEGER_PROGRAMMING or GUROBI or GUROBI_MIP, GUROBI混合线性求解器, 商业
• CPLEX_LINEAR_PROGRAMMING or CPLEX_LP, CPLEX线性求解器, 商业
• CPLEX_MIXED_INTEGER_PROGRAMMING or CPLEX or CPLEX_MIP, CPLEX混合整数求解器, 商业
• XPRESS_LINEAR_PROGRAMMING or XPRESS_LP, XPRESS线性求解器, 商业
• XPRESS_MIXED_INTEGER_PROGRAMMING or XPRESS or XPRESS_MIP, XPRESS混合整数求解器, 商业
• GLPK_LINEAR_PROGRAMMING or GLPK_LP, GLPK, 免费, https://www.gnu.org/software/glpk/
• GLPK_MIXED_INTEGER_PROGRAMMING or GLPK or GLPK_MIP, 免费

from ortools.linear_solver import pywraplp

solver = pywraplp.Solver.CreateSolver("CLP")

二. 概念

Concepts

This section presents key concepts for advanced use of LP solvers. We assume that readers are familiar with the concept of duality in LP.

注意阅读下面内容之前, 最好对对偶线性规划有所了解.

2.1 线性规划求解器算法家族

Families of LP algorithms

The following classes of algorithms for LP are accessible via OR-Tools.

以下是ortools实现的算法

1. The Simplex algorithm was the first practical LP algorithm and remains the most popular. The algorithm walks along the vertices (corner points) of the feasible region, iteratively improving the value of the objective function until reaching an optimal solution. There are two types of simplex algorithms:

   单纯形法, 这是第一个实用的线性规划求解算法, 至今依然还很流行.

   1. Primal simplex takes steps along the vertices of the primal feasible region. This variant is particularly effective at solving a sequence of LP problems with varying objective functions, that is, where the primal feasible region is fixed.

      原始单纯形法, 沿着原始可行域的顶点采取步骤. 这种变体在解决一系列具有不同目标函数的LP问题时特别有效, 即在原始可行区域是固定的情况下.

   2. Dual simplex takes steps along the vertices of the dual feasible region. This variant is particularly effective at solving a sequence of LP problems where the dual feasible region is fixed, for example, when only bounds on variables change. For this reason, dual simplex is used extensively in MIP solvers.

      对偶单纯形法沿着可行域的顶点采取步骤. 这种变体在解决对偶可行区域固定的LP问题序列时特别有效, 例如, 当只有变量的边界变化时. 因此, 对偶单纯形在MIP求解中得到了广泛的应用.

2. Barrier or interior-point methods were the second practical family of algorithms for LP. Barrier methods pair theoretical guarantees of efficient (polynomial time) convergence with reliable performance in practice. They complement the simplex algorithm when it performs poorly; for example, some solvers offer to run both simplex and barrier in parallel, returning the solution from the algorithm that finishes first.

   屏障或内部点方法是 LP 的第二个实用线性规划算法. 屏障方法将有效(多项式时间)收敛的理论保证与可靠的实践性能结合起来. 单纯算法在性能不佳时作为其补充; 例如, 一些求解器单纯形算法和屏障法并行运行, 返回最先解决的方案.

3. First-order methods are a family of algorithms that use exclusively gradient information (that is, first-order derivatives) to guide the iterations. Gradient descent is a well-known example. These methods are popular in nonlinear optimization and machine learning. For LP, first-order methods can scale to larger problems than simplex and barrier, and may also have much smaller memory requirements. On the other thand, they are more sensitive to numerical issues and may struggle to obtain highly accurate solutions.

   一阶方法, 即利用梯度下降来实现. 这种方法广泛用于非线性问题优化和机器学习中. 这种方法的使用到更为广泛的问题上, 因为对于内存的要求更低. 但是需要注意的是, 这种方法对于数值的精度更为敏感, 也许无法获得高精度的求解结果.

   即牺牲数值的精度换取求解的适用性和求解的速度.

The table below lists the LP solvers available in OR-Tools and indicates which of the three families of algorithms is implemented in each solver.

下表列出了OR-Tools中可用的LP求解器, 并指出在每个求解器中实现了三种算法中的哪一种.

G indicates the solver is developed by Google. L indicates that the solver requires a license issued by the respective third-party developer.

G标记的求解器为Google所开发的算法.

L标记为取得授权的第三方的算法.

ortools提供了其他的求解器的支持.

See Recommendations for suggestions on which solvers and algorithms to use.

关于使用哪种算法, 见下面的推荐部分内容.

2.2 求解结果的内在含义

What does solving really mean?

For getting the most out of LP solvers, it's important to understand what is implied when a solver claims to have found a solution to an LP problem. This section covers the basics necessary for answering this question, in particular given numerical imprecision and non-uniqueness of solutions.

这一点非常重要, 为了最大限度地利用LP求解器, 对于理解当求解器声称找到了LP问题的解决方案时所隐含的含义. 本节涵盖了回答这个问题所需的基础知识, 特别是在数值不精确和解的非唯一性的情况下.

2.2.1 公差

Tolerances

LP solvers almost always use floating-point arithmetic, making their solutions subject to numerical imprecision. To account for this, and to improve performance by avoiding effort on solutions that are already good enough, solvers accept solutions- and claim to have solved a problem- when these solutions satisfy conditions up to certain tolerances.

线性规划求解算法通常使用浮点数来计算, 这使得结果总是存在一定的数值精度问题. 考虑到这一点, 通过避免在已经足够好的解决方案上花费精力来提高性能, 当这些解决方案满足一定的"公差" 条件时, 求解器就会返回得到的解决方案.

Consider the linear programming problem.

线性规划原问题

\begin{align*} \min\quad & -2x_1 - x_2 \\ \text{s.t.}\quad& x_1 + x_2 \le 1\\ & x_1, x_2 \ge 0 \end{align*}

and its corresponding dual problem

对偶问题

\begin{align*} \max\quad& y \\ \text{s.t.}\quad& -2 - y \ge 0\\ &-1 - y \ge 0 \\ &y \le 0 \end{align*}

This pair of problems has a unique optimal primal solution of $x_1 = 1, x_2 = 0$ and dual solution $y = -2$. Which solutions could be accepted as optimal by a solver? To answer this, we define the following quantities:

• The duality gap is the difference between the primal objective value and the dual objective value, in this case, $|(-2x_1 - x_2) - y|$.
• The primal infeasibilities are the violations of the primal constraints, in this case, $(\max\{ (x_1+x_2) - 1, 0 \}, \max\{-x_1, 0\}, \max\{-x_2, 0\})$.
• The dual infeasibilities are the violations of the dual constraints, in this case, $(\max\{ 2 + y, 0 \}, \max\{ 1 + y, 0 \}, \max\{ y, 0 \})$.

A solver declares a solution as optimal if the duality gap, the primal infeasibilities, and the dual infeasibilities are smaller than a given tolerance.'

如果对偶间隙, 原始不可行性和对偶不可行性小于给定限制, 则求解器将该解声明为最优解.

Notably, the application of the tolerances varies for both natural and idiosyncratic reasons across solvers and algorithms. For example, the duality gap in the simplex algorithm is driven only by numerical imprecision, while the primal and dual infeasibilities are present even in exact arithmetic. Some methods directly enforce the bound constraints $x_1 \ge 0, x_2 \ge 0,$ and $y \le 0$, while others treat violations of bound constraints differently from violations of linear constraints like $x_1 + x_2 \le 1$. For some solvers, tolerances are absolute; that is, there is a parameter $\epsilon$, and solutions are considered optimal if the duality gap and all primal and dual infeasibilities are less than or equal to $\epsilon$. For other solvers, tolerances are relative, meaning that they scale with the size of the coefficients in the problem.

For an example of the effect of tolerances, consider an absolute tolerance of $\epsilon = \frac{1}{2}$ applied to the above primal-dual pair. The solution $x_1 = 1.5, x_2 = 0, y = -3$ has zero duality gap and infeasibilities all less than or equal to $\epsilon$, hence a solver might declare this solution "optimal". Yet, its objective value (-3) differs by 1 from the true optimal objective value of -2. Typical default values of $\epsilon$ are between $10^{-6}$ and $10^{-8}$, which makes such extreme examples rare but not impossible.

2.2.2 解决方案类型

Types of solutions

LP problems can have more than one optimal solution, even more so when accounting for tolerances. We briefly discuss the properties of solutions returned by the three different families of LP algorithms presented above.

LP问题可以有多个最优解, 在考虑公差时更是如此. 我们简要地讨论了上述三种不同LP算法族所返回解的性质.

Simplex algorithms always return vertices or corner points of the feasible region. These solutions are preferred in some situations because they tend to be sparser.

单纯形算法总是返回可行域的顶点或角点. 在某些情况下, 这些解决方案更受欢迎, 因为它们更稀疏.

Barrier and first-order methods do not generally return vertices. (Theory provides additional characterizations that are beyond the scope of this guide.)

屏障和一阶方法通常不返回顶点. (理论提供了额外的特性, 超出了本内容讨论的范围. )

For historical reasons and because vertex solutions have appealing properties, solvers often, by default, apply a crossover procedure to move to an optimal vertex from a solution found by a barrier algorithm. Crossover is not currently offered for solutions found by first-order methods.

由于历史原因, 以及由于顶点解具有吸引人的属性, 在默认情况下, 求解器通常应用" 交叉" 过程从a移动到最优顶点.

三. 推荐操作

Recommendations

We make the following recommendations for advanced use of LP solvers.

对于高阶的用户有如下的推荐操作.

3.1 缩放问题数据

Scaling of problem data

Solvers can experience slow convergence or failures on models because of numerical issues. Such issues can arise for many reasons; here we give one example.

求解器可能收敛非常慢或者求解失败因为数值(误差)问题. 类似问题的出现可能有多种原因, 以下是一个示例:

It is common for very small or large numerical constants to appear in LP models. Extending the example from above, if $x_1$ and $x_2$ represent the fraction of customers assigned to "provider 1" or "provider 2", and if we want to maximize benefit from serving these customers, we might write the following objective function,

$min\; -c_1 x_1 - c_2x_2$

where:

• $c_1$ is the benefit from assigning customers to provider 1
• $c_2$ is the benefit from assigning customers to provider 2

Duals satisfying the following constraints would be considered feasible with an absolute tolerance $\epsilon$:

$y \leq -c_1 + \epsilon,\\ y \leq -c_2 + \epsilon.\\$

If the benefit units of $c_1$ and $c_2$ are small fractional values that happen to be on the same scale as $\epsilon$, then the dual feasibility conditions become rather weak, hence a very suboptimal primal may be declared optimal.

If, on the other hand, the benefit units are "microdollars" (1 000 000 microdollars = 1 dollar), the resulting very large absolute values ask for very high precision in the solution, possibly unreasonably high given the limits of floating point numbers. Solvers may fail to converge if the problem is formulated in this way. As part of formulating a well-posed problem, advanced modelers should consider if the problem data are scaled in a way that's consistent with their solver's tolerances.

另一方面, 如果收益单位是" 微美元" (1 000 000微美元= 1美元), 则由此产生非常大的绝对值要求解决方案具有非常高的精度, 考虑到浮点数的限制, 可能高得不合理. 如果用这种方式表述问题, 求解器可能无法收敛. 作为表述一个适定问题的一部分, 高级建模者应该考虑问题数据是否以与求解器公差一致的方式进行缩放

In addition to avoiding numerical failures, tolerances may also be tuned for better performance. Simplex and barrier methods are not too sensitive to tolerances but occasionally might benefit from larger tolerances if progress is observed to stall at the end of the solve. On the other hand, first-order methods are typically much more sensitive. Users of first-order methods can benefit from faster solutions by relaxing tolerances, as the context allows.

除了避免数值故障外, 还可以调整公差(可以容忍的误差上限)以获得更好的性能. 单纯形法和屏障法对公差不太敏感, 但如果在求解结束时观察到进度停滞, 有时可能会受益于较大的公差. 另一方面, 一阶方法通常更敏感. 一阶方法的用户可以在上下文允许的情况下, 通过放宽公差来获得更快的解决方案.

For Glop's tolerances, see primal_feasibility_tolerance, dual_feasibility_tolerance, and solution_feasibility_tolerance in GlopParameters. Note that primal_feasibility_tolerance and dual_feasibility_tolerance are used within the algorithm, while solution_feasibility_tolerance is checked post-solve to flag numerical issues. For PDLP, see eps_optimal_absolute and eps_optimal_relative.\

关于Glop计算上的偏差, 详情见: GlopParameters.

For further reading on these types of issues, see Gurobi's Guidelines for Numerical Issues. While the guidelines are written for users of Gurobi, many of the principles apply generally.

对于上述问题, 也可以参考Gurob的文档, 该文档虽然是面向Gurobi用户的, 但是其原理是相近的.

3.2 求解器和算法

Choice of solvers and algorithms

We start off with an example of how large the impact of the choice of solvers and algorithms can be and then present a guide for choosing LP solvers.

从这个例子来看, 说明选择求解器和算法的影响有多大.

3.2.1 实践的差异

Variability in practice

We illustrate the variability in performance across LP algorithms and solvers by comparing the solve times on a selection of instances that have been used by Hans Mittelmann for benchmarking LP solvers. The instances are explicitly chosen to show the extremes of relative performance and are not necessarily representative of typical behavior.

在不同的实例下进行了基准测试, 以说明不同的算法在不同的场景下的表现差异

Glop's primal and dual simplex methods are compared with Gurobi's barrier method (with and without crossover, which finds a vertex solution) and PDLP, a first-order method, in high and low precision. The table below reports solve times in seconds, with a limit of 20 minutes (1200 seconds).

将Glop的原始单纯形法和对偶单纯形法与Gurobi的屏障法法(有交叉和无交叉, 找到一个顶点解)和PDLP的一阶方法在高低精度上进行了比较. 下表以秒为单位报告求解时间, 上限为20分钟(1200秒).

总结上述测试如下:

• The relative performance of algorithms and solvers can vary by orders of magnitude on a single instance.
• 算法和求解器的相对性能在单个实例上可能会有数量级的变化.
• No single algorithm and solver is uniformly better than others.
• 没有单一算法是普适的
• Crossover (enabled by default) increases solve time, sometimes substantially.
• 交叉求解(默认)也许会答复增加求解的时间
• PDLP can solve to low precision sometimes 10 times faster than to high precision.
• PDLP算法在低精度场景计算上的速度远胜于高精度的计算场景

3.2.2 关于选择求解器的简单指引

A brief guide for choosing LP solvers

Given that no single LP algorithm or solver is the best, we recommend the following steps for discovering what is best for your use case. Start with the first step and proceed to the next if performance is not sufficient.

考虑到没有一种线性规划求解算法是普适的, 可以根据求解的情况来选择合适的求解器.

1. Try Glop.Why: Glop is Google's in-house implementation of the primal and dual simplex methods. Glop is open source and trusted for Google's production workloads.

   先使用Google家的算法. 这是Google出品的原始和对偶求解算法.

   • If the default configuration (primal simplex) doesn't perform well, try switching to dual simplex using use_dual_simplex: true.

     默认是原始单纯形算法, 假如效果不好切换到对偶单纯形算法/

2. If a license is available, try a commercial solver (CPLEX, Gurobi, or Xpress). Experiment with simplex and barrier methods.Why: These solvers are industry standard and highly optimized. Also, barrier methods complement the simplex algorithms offered by Glop.

   商业授权许可, CPLEX, Gurobi, or Xpress, 好处是符合行业的标准, 高度优化. 对GOLP补充了屏障法的支持.

   • If using barrier, disable "crossover" if you do not need a vertex solution.

3. Try PDLP. Tune the convergence tolerances to your application. Why: PDLP is designed for the largest problems, where simplex and barrier methods hit memory limits or are too slow. PDLP performs best when an approximate but quick solution is preferred to an exact but slow solution.

   PLDL算法是设计用于大规模求解问题的, 当单纯形法和屏障法将可能遭遇内存瓶颈和计算速度过慢. 当近似但快速的解决方案优于精确但缓慢的解决方案时, PDLP表现最佳.

4. If you have made it this far, you are now an advanced LP user! Please see OR-Tools support options for further help.

   恭喜读完本内容, 你已经是高阶PL用户了.

1. It is often more complex than this. Solvers typically check these conditions on a transformed/simplified version of the problem, called the presolved problem. In some cases, a solution to the presolved problem may be far away from a solution to the input problem. This situation can lead to unusual statuses like CPLEX's OptimalInfeas or Glop's IMPRECISE. ↩

四. 参考

• 运筹学, 清华大学, 第三版