Mixed-Integer Programming

又称: MIP, MILP, MIQP, MICP
类别: Planning & manipulation › Trajectory optimisation
标签: optimization, integer-programming, motion-planning, task-allocation, hybrid-systems

一种优化，其中部分变量必须取整数值（通常为 0 或 1），从而让一个问题能把离散选择与连续量结合起来。

定义

混合整数规划（Mixed-integer programming，MIP）是在连续变量与被限制为整数的变量混合在一起的情况下进行的优化，其中整数变量最常见的是取值为 0 或 1 的二元变量。二元变量编码离散决策：路径经过哪个区域，下一步哪只脚落地，某个接触是否激活，哪台机器人承担哪项任务。连续变量承载其余的量，例如位置、速度和力。常见的类别按剩余问题的形式命名：混合整数线性规划（MILP）、混合整数二次规划（MIQP），以及更一般的混合整数凸规划（MICP）。

这类问题在一般情况下是 NP 难的，但现代求解器能很好地处理许多实际实例。它们使用分支定界：去掉整数要求后求解连续松弛问题，选出一个结果为分数的变量，把问题拆分为两个分别迫使该变量向下或向上取整的子问题，并剪掉任何松弛解已经比目前找到的最佳整数解更差的分支。割平面会在此过程中收紧松弛。Gurobi 和 CPLEX 等商业求解器，以及 SCIP、HiGHS 和 CBC 等开源求解器都实现了这些方法。

问题的写法与使用哪个求解器同样重要。逻辑条件常用大 M 约束（big-M constraints）来编码，它借助一个二元变量和一个很大的常数来开启或关闭某个约束；常数过大会削弱松弛并引起数值问题。松弛紧的表述求解起来快得多，这也是凸集图等结构化方法被设计成使其松弛接近真实问题的原因之一。

为何重要

许多机器人规划问题部分是离散的：从障碍物左边还是右边绕过、选择接触序列、分配任务。混合整数规划在一次优化中精确地处理这些选择，并常常给出答案距最优有多远的界，而不是依赖手工设计的启发式规则或采样。

主要应用

腿足机器人的落脚点和接触序列规划
无人机和机械臂穿越凸区域的轨迹规划
机器人群体的任务分配与调度
带有离散模式的混合模型预测控制
带有离散动作选择的任务与运动规划

实际应用

一个为人形机器人规划踏石落脚点的团队，把每块石头的可行走表面表示为一个凸多边形。对接下来的每一步，他们加入用于选择脚落在哪个多边形上的二元变量，以及只对所选多边形生效的约束，再加上表示脚的位置的连续变量，以及对步长和转向的限制。代价函数奖励朝目标的进展，并惩罚别扭的步伐。混合整数求解器返回一个步伐序列，通常在为重规划设定的时间限制之内，同时给出所找到的最佳解与最佳界之间的间隙。如果求解时间太长，团队会减少一次规划的步数，收紧大 M 值，或用上一次的计划进行热启动。

常见误解

混合整数规划对机器人来说总是太慢 — 规模小、表述良好的问题可以足够快地求解，满足在线重规划的需要
对连续松弛取整就能得到最优整数解 — 除非松弛是紧的，否则取整的结果可能不可行，或远离最优
在大 M 约束中，任何大的 M 值都可以 — 过大的值会削弱松弛并造成数值困难
到达时间限制而停止的求解器就是失败了 — 它通常会返回目前为止的最佳解，以及一个说明该解有多好的最优性间隙

谁需要了解

运动规划和落脚点规划工程师
机器人群体调度和任务分配开发者
基于优化的控制领域的研究人员
学习优化的机器人专业学生

视频

Mixed Integer Linear Programming (MILP) Tutorial: APMonitor.com

维基百科

整数规划

Open Source Robotics