对整数问题的介绍及解决方法之一
介绍
整数规划(IP)是线性规划(LP)的一种特殊情况,其中决策变量受限于整数值。也就是说,诸如2.5或4.2之类的值不可能是这些问题的解。
这个要求被视为LP的附加约束,从而使得寻找最优解的过程更具挑战性。
在现实生活中,我们面临的许多问题都采用IP的形式。例如,资本预算和分配,我们决定要进行哪些投资,需要决策变量是二进制的,并且只能取值为0
和1
。房地产中的选址问题,车辆路径以及调度问题很可能也属于这一类。
在本文中,我们将探讨一种用于解决整数问题(IP)的算法,即分支界限算法。
我将借鉴Cornuejols和Tütüncü的书《金融优化方法》中的例子,但加入了我自己的直观解释和当然,这些算法的Python实现。
分支界限算法
分支界限算法是解决IP问题的最流行方法之一。该算法将主问题分解为较小的子问题(分支),通过这样做,能够尝试其中一些解,并随后消除其中一些解集(剪枝/修剪),当这些解集不比当前/最初的解更好时。
这可能有些难以理解,但通过一个例子会更容易。
问题0
是我们的原始整数问题。请注意,它是一个带有附加约束的简单线性规划问题。