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_countdef 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_modeldef 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
indomain
. 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 theConstraint
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 intuple_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 valuej
, theninverse_variables[j]
is assigned a valuei
. 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
impliesb
).单向束缚,如果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能够应用的变量、束缚函数、指标函数等信息。