ORTOOLS - CPSAT - Objective to minimize a value by intervals

Question

I my model in ORTools CPSAT, I am computing a variable called salary_var (among others). I need to minimize an objective. Let’s call it « taxes ».

to compute the taxes, the formula is not linear but organised this way:

if salary_var below 10084, taxes corresponds to 0%
between 10085 and 25710, taxes corresponds to 11%
between 25711 and 73516, taxes corresponds to 30%
and 41% for above

For example, if salary_var is 30000 then, taxes are:

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

My question: how can I efficiently code my « taxes » objective?

Thanks for your help Seb

Answer 1

This task looks rather strange, there is not much context and some parts of the task might touch some not-so-nice areas of finite-domain based solvers (large domains or scaling / divisions during solving).

Therefore: consider this as an idea / template!

Code

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])))

Output

[15625, 4289, 0, 300545]

Remarks

As implemented:

• uses scaled solving
• produces scaled solution (300545)
• no fiddling with non-integral / ratio / rounding stuff BUT large domains

Alternative:

• Maybe something around AddDivisionEquality

Edit in regards to Laurents comments

In some scenarios, solving the scaled problem but being able to reason about the real unscaled values easier might make sense.

If i interpret the comment correctly, the following would be a demo (which i was not aware of and it's cool!):

Updated Demo Code (partial)

# 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

Output (excerpt)

...
...
#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