0

我在 ORTools CPSAT 中的模型，我正在计算一个名为salary_var 的变量（等等）。我需要最小化一个目标。我们称之为“税收”。

为了计算税收，公式不是线性的，而是这样组织的：

如果salary_var 低于10084，则税款对应于10085 和25710 之间的0% ，税款对应于 25711 和73516 之间
的11% ，税款对应于 以上的30% 和41%


例如，如果salary_var 为30000，则税为：

(25710-10085) * 0.11 + (30000-25711) * 0.3 = 1718 + 1286 = 3005

我的问题：如何有效地编码我的“税收”目标？

感谢您的帮助

4

1 回答 1

3

这个任务看起来很奇怪，没有太多的上下文，任务的某些部分可能会涉及基于有限域的求解器的一些不太好的区域（求解过程中的大域或缩放/划分）。

因此：将其视为一个想法/模板！

代码

from ortools.sat.python import cp_model

# Data
INPUT = 30000
INPUT_UB = 1000000
TAX_A = 11
TAX_B = 30
TAX_C = 41

# Helpers

# new variable which is constrained to be equal to: given input-var MINUS constant
# can get negative / wrap-around
def aux_var_offset(model, var, offset):
    aux_var = model.NewIntVar(-INPUT_UB, INPUT_UB, "")
    model.Add(aux_var == var - offset)
    return aux_var

# new variable which is equal to the given input-var IFF >= 0; else 0
def aux_var_nonnegative(model, var):
    aux_var = model.NewIntVar(0, INPUT_UB, "")
    model.AddMaxEquality(aux_var, [var, model.NewConstant(0)])
    return aux_var


# Model
model = cp_model.CpModel()

# vars
salary_var = model.NewIntVar(0, INPUT_UB, "salary")
tax_component_a = model.NewIntVar(0, INPUT_UB, "tax_11")
tax_component_b = model.NewIntVar(0, INPUT_UB, "tax_30")
tax_component_c = model.NewIntVar(0, INPUT_UB, "tax_41")

# constraints
model.AddMinEquality(tax_component_a, [
    aux_var_nonnegative(model, aux_var_offset(model, salary_var, 10085)),
    model.NewConstant(25710 - 10085)])

model.AddMinEquality(tax_component_b, [
    aux_var_nonnegative(model, aux_var_offset(model, salary_var, 25711)),
    model.NewConstant(73516 - 25711)])

model.Add(tax_component_c == aux_var_nonnegative(model,
                                aux_var_offset(model, salary_var, 73516)))

tax_full_scaled = tax_component_a * TAX_A + tax_component_b * TAX_B + tax_component_c * TAX_C

# Demo
model.Add(salary_var == INPUT)

solver = cp_model.CpSolver()
status = solver.Solve(model)
print(list(map(lambda x: solver.Value(x), [tax_component_a, tax_component_b, tax_component_c, tax_full_scaled])))

输出

[15625, 4289, 0, 300545]

评论

如实施：

  • 使用缩放求解
  • 生成缩放解决方案 (300545)
  • 不摆弄非整数/比率/舍入的东西但是大域

选择：

  • 也许周围的东西AddDivisionEquality

编辑关于 Laurents 的评论

在某些情况下，解决缩放问题但能够更容易地推断出真正的未缩放值可能是有意义的。

如果我正确解释了评论，以下将是一个演示（我不知道它很酷！）：

更新的演示代码（部分）

# Demo -> Attempt of demonstrating the objective-scaling suggestion
model.Add(salary_var >= 30000)
model.Add(salary_var <= 40000)

model.Minimize(salary_var)

model.Proto().objective.scaling_factor = 0.001   # DEFINE INVERSE SCALING

solver = cp_model.CpSolver()
solver.parameters.log_search_progress = True     # SCALED BACK OBJECTIVE PROGRESS

status = solver.Solve(model)
print(list(map(lambda x: solver.Value(x), [tax_component_a, tax_component_b, tax_component_c, tax_full_scaled])))
print(solver.ObjectiveValue())                   # SCALED BACK OBJECTIVE

输出（摘录）

...
...
#1       0.00s best:30    next:[30,29.999]  fixed_bools:0/1
#Done    0.00s  

CpSolverResponse summary:
status: OPTIMAL
objective: 30
best_bound: 30
booleans: 1
conflicts: 0
branches: 1
propagations: 0
integer_propagations: 2
restarts: 1
lp_iterations: 0
walltime: 0.0039022
usertime: 0.0039023
deterministic_time: 8e-08
primal_integral: 1.91832e-07

[15625, 4289, 0, 300545]
30.0
于 2021-08-11T23:53:29.120 回答