关于算法:运筹优化工具ortools解读与实践ortools求解CP问题

44次阅读

共计 7402 个字符,预计需要花费 19 分钟才能阅读完成。

1. 前言

如前文所说,束缚布局(CP)指求解满足各项束缚的 可行解 的问题。与线性规划、整数布局不同,束缚布局更加关注可行解,没有明确的优化指标。典型的场景包含员工排班问题、N 皇后问题。CP 问题尽管没有指标函数,但能够通过指标增加到束缚的形式放大到更易于治理的子集,变相解决整数布局问题。

ortools 提供了 CP-SAT 求解器,其应用办法与 MPSolver 相似。接下来,咱们看看 CP-SAT 是如何解决 CP 问题以及 MIP 问题的。

2. 求解 CP 问题

问题如下:

有变量 x, y,z, 取值范畴均为为 0, 1, 2,
约束条件: x ≠ y,
求满足条件的 x,y,z 组合。

代码及解说如下,这里采纳硬编码方式。

# 引入 cp_model,便于后续构建 CP-SAT 求解器对应模型
from ortools.sat.python import cp_model


#回调类,每失去一个后果均执行 on_solution_callback 函数
class VarArraySolutionPrinter(cp_model.CpSolverSolutionCallback):
    """Print intermediate solutions."""

    def __init__(self, variables):
        cp_model.CpSolverSolutionCallback.__init__(self)
        self.__variables = variables
        self.__solution_count = 0

    def on_solution_callback(self):
        self.__solution_count += 1
        for v in self.__variables:
            print('%s=%i' % (v, self.Value(v)), end=' ')
        print()

    def solution_count(self):
        return self.__solution_count


def SearchForAllSolutionsSampleSat():
    """Showcases calling the solver to search for all solutions."""
    # 创立模型
    model = cp_model.CpModel()

    # 创立变量
    num_vals = 3
    x = model.NewIntVar(0, num_vals - 1, 'x')
    y = model.NewIntVar(0, num_vals - 1, 'y')
    z = model.NewIntVar(0, num_vals - 1, 'z')

    # 创立束缚.
    model.Add(x != y)

    # 创立求解器并求解.
    solver = cp_model.CpSolver()
    # 定义回调对象
    solution_printer = VarArraySolutionPrinter([x, y, z])
    # 批改求解器参数:枚举所有后果
    solver.parameters.enumerate_all_solutions = True
    # 求解过程
    status = solver.Solve(model, solution_printer)

    print('Status = %s' % solver.StatusName(status))
    print('Number of solutions found: %i' % solution_printer.solution_count())

SearchForAllSolutionsSampleSat()

3. 求解 MIP 问题

问题如下:

最大化 2x + 2y + 3z,同时满足以下束缚:
x + 7⁄2 y + 3⁄2 z ≤ 25
3x – 5y + 7z ≤ 45
5x + 2y – 6z ≤ 37
x, y, z ≥ 0
x, y, z 为整数

代码及解说如下。须要留神的是:为了进步求解速度,CP-SAT 求解器要求所有束缚的元素都为整数。理论利用中遇到浮点数时须要对约束条件进行转换,例如,不等式两边别离乘以一个较大的数。

from ortools.sat.python import cp_model


def main():
    model = cp_model.CpModel()

    var_upper_bound = max(50, 45, 37)
    x = model.NewIntVar(0, var_upper_bound, 'x')
    y = model.NewIntVar(0, var_upper_bound, 'y')
    z = model.NewIntVar(0, var_upper_bound, 'z')

    # Creates the constraints.
    model.Add(2 * x + 7 * y + 3 * z <= 50)
    model.Add(3 * x - 5 * y + 7 * z <= 45)
    model.Add(5 * x + 2 * y - 6 * z <= 37)

    model.Maximize(2 * x + 2 * y + 3 * z)

    # Creates a solver and solves the model.
    solver = cp_model.CpSolver()
    status = solver.Solve(model)

    if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
        print(f'Maximum of objective function: {solver.ObjectiveValue()}\n')
        print(f'x = {solver.Value(x)}')
        print(f'y = {solver.Value(y)}')
        print(f'z = {solver.Value(z)}')
    else:
        print('No solution found.')

    # Statistics.
    print('\nStatistics')
    print(f'status   : {solver.StatusName(status)}')
    print(f'conflicts: {solver.NumConflicts()}')
    print(f'branches : {solver.NumBranches()}')
    print(f'wall time: {solver.WallTime()} s')


if __name__ == '__main__':
    main()

应用 CP-SAT 能够解决 MIP 问题,前文提到应用 MPSolver 及整数布局求解器同样能够解决 MIP 问题,另外,后续咱们还会提到应用网络流解决 MIP 问题。应用过程中如何做选型呢?

  • MPSolver:求解问题比拟偏差于规范的线性规划问题,局部变量有整数束缚
  • CP-SAT:适宜变量为 0 - 1 取值的状况
  • 网络流办法:问题能够转化为网络关系,进而利用网络关系升高问题求解难度

三种办法有所偏重,但选型上并不相对。很多问题也都是能够从不同的角度转化为不同类型的问题,进而应用不同的求解器进行求解的。

4.CP-SAT 要害因素

建模过程中须要将数学模型转化为代码,其中最重要的是变量和束缚的转化。接下来,咱们看一看 CP-SAT 都提供哪些变量、束缚函数和指标函数。理解了提供的性能,编程就变成了“搭积木”。

变量

  • NewIntVar(self, lb, ub, name):Create an integer variable with domain [lb, ub]
  • NewIntVarFromDomain(self, domain, name):变量取值范畴在指定的(未必间断的)域中

    Create an integer variable from a domain.

    A domain is a set of integers specified by a collection of intervals. For example, model.NewIntVarFromDomain(cp_model.Domain.FromIntervals([[1, 2], [4, 6]]), 'x')

  • NewBoolVar(self, name):Creates a 0-1 variable with the given name.
  • NewConstant(self, value):Declares a constant integer
  • NewIntervalVar(self, start, size, end, name):Creates an interval variable from start, size, and end. 区间变量,能够示意工夫区间,在 VRP 算法中应该有所应用。

    start、size、end 均能够是线性表达式或常量,但办法外部增加了 start + size == end 的束缚

  • NewFixedSizeIntervalVar(self, start, size, name): 区间变量

    start 能够是线性表达式或常量,size 必须为常量

  • NewOptionalIntervalVar(self, start, size, end, is_present, name):Creates an optional interval var from start, size, end, and is_present.

    is_present: A literal that indicates if the interval is active or not. A inactive interval is simply ignored by all constraints. NewIntervalVar 和 NewOptionalIntervalVar 的不同之处在于,是前者示意创立的区间变量在当前的束缚建设中肯定失效,而后者的办法签名中有个为 is_present 的参数示意这个区间变量是否失效。

  • NewOptionalFixedSizeIntervalVar(self, start, size, is_present, name):Creates an interval variable from start, and a fixed size.

束缚

  • AddLinearConstraint(self, linear_expr, lb, ub):Adds the constraint: lb <= linear_expr <= ub.
  • AddLinearExpressionInDomain(self, linear_expr, domain):Adds the constraint: linear_expr in domain.
  • Add(self, ct):Adds a BoundedLinearExpression to the model.

    示例:
    model.Add(5 x + 2 y – 6 * z <= 37)

  • AddAllDifferent(self, *expressions):This constraint forces all expressions to have different values.

    Adds AllDifferent(expressions).
    This constraint forces all expressions to have different values.
    Args:
    expressions: simple expressions of the form a var + constant.
    Returns:
    An instance of the Constraint class.
    示例:
    queens = [model.NewIntVar(0, board_size – 1, ‘x%i’ % i) for i in range(board_size)
    ]
    model.AddAllDifferent(queens)

  • AddElement(self, index, variables, target): 等值束缚

    Adds the element constraint: variables[index] == target.

  • AddCircuit(self, arcs):arcs 组成的门路汇合形成哈密顿门路,TSP 束缚.
  • AddMultipleCircuit(self, arcs):Adds a multiple circuit constraint, aka the “VRP” constraint. 造成的多条链路,须要保障造成的各链路内 arc 首位连贯。揣测 ortools 的 routing 模块应用了 AddCircuit、AddMultipleCircuit 两种办法。
  • AddAllowedAssignments(self, variables, tuples_list): 固定匹配束缚

    An AllowedAssignments constraint is a constraint on an array of variables,
    which requires that when all variables are assigned values, the resulting
    array equals one of the tuples in tuple_list.

  • AddForbiddenAssignments(self, variables, tuples_list): 禁止束缚

    A ForbiddenAssignments constraint is a constraint on an array of variables
    where the list of impossible combinations is provided in the tuples list.

  • AddAutomaton(self, transition_variables, starting_state, final_states, transition_triples): 状态转移束缚(状态之间存在转移关系)

    transition_variables 代表了须要求解的变量,starting_state 为起始状态,final\_states 为可承受的最终状态,transition_triples 为转移关系

  • AddInverse(self, variables, inverse_variables): 关联束缚

    An inverse constraint enforces that if variables[i] is assigned a value j, then inverse_variables[j] is assigned a value i. And vice versa.

  • AddReservoirConstraint(self, times, level_changes, min_level,max_level): 储水池束缚

    sum(level_changes[i] if times[i] <= t) in [min_level, max_level]

  • AddReservoirConstraintWithActive(self, times, level_changes, actives, min_level, max_level): 工夫开关的储水池束缚,actives 示意是否动作是否失效

    sum(level_changes[i] * actives[i] if times[i] <= t) in [min_level, max_level]

  • AddMapDomain(self, var, bool_var_array, offset=0):Adds var == i + offset <=> bool_var_array[i] == true for all i.
  • AddImplication(self, a, b):Adds a => b (a implies b). 单向束缚,如果 a,则 b
  • AddBoolOr(self, *literals):Adds Or(literals) == true: Sum(literals) >= 1.
  • AddAtLeastOne(self, *literals):Same as AddBoolOr: Sum(literals) >= 1.
  • AddAtMostOne(self, *literals):Adds AtMostOne(literals): Sum(literals) <= 1.
  • AddExactlyOne(self, *literals):Adds ExactlyOne(literals): Sum(literals) == 1.
  • AddBoolAnd(self, *literals):Adds And(literals) == true.
  • AddBoolXOr(self, *literals):Adds XOr(literals) == true. 异或运算
  • AddMinEquality(self, target, exprs):Adds target == Min(exprs).
  • AddMaxEquality(self, target, exprs):Adds target == Max(exprs).
  • AddDivisionEquality(self, target, num, denom):Adds target == num // denom (integer division rounded towards 0). 取整操作,向 0 舍入。
  • AddAbsEquality(self, target, expr):Adds target == Abs(var).
  • AddModuloEquality(self, target, var, mod):Adds target = var % mod. 取余操作
  • AddMultiplicationEquality(self, target, *expressions):Adds target == expressions[0] * .. * expressions[n].
  • AddNoOverlap(self, interval_vars): 区间不重叠束缚. 例如,区间变量示意工夫距离时,AddNoOverlap 会强制所有的工夫距离变量不产生重叠, 不过它们能够应用雷同的开始 / 完结的工夫点。在 VRP 算法中会进行应用。
  • AddNoOverlap2D(self, x_intervals, y_intervals): 所有矩形不重叠束缚,x_intervals、y_intervals 别离存储了不同矩形的 x、y 坐标
  • AddCumulative(self, intervals, demands, capacity): 需求量小于能力下限的束缚,VRP 中会应用。

    for all t:
    sum(demands[i] if (start(intervals[i]) <= t < end(intervals[i])) and (intervals[i] is present)) <= capacity

指标

  • Minimize(self, obj): 最小化
  • Maximize(self, obj): 最大化

5. 结语

本篇文章次要解说了 ortools 应用 CP-SAT 求解器解决 CP、MIP 问题的办法,并具体解读了 CP 能够应用的变量、束缚函数、指标函数等信息。

正文完
 0