Assumptions

[Igor Proshkin]

I tried to use Assumptions in CP-SAT in python. I assumed that SufficientAssumptionsForInfeasibility will give the SMALLEST list of assumptions that make the model infeasible, but the list I got is not always the smallest possible.

This is my code:

from ortools.sat.python import cp_model

import random

n = 5

upper_bound = 100

model = cp_model.CpModel()

start_vars = [model.NewIntVar(0, upper_bound, f"start_{i}") for i in range(n)]

end_vars = [model.NewIntVar(0, upper_bound, f"end_{i}") for i in range(n)]

duration_vars = [model.NewIntVar(0, upper_bound , f"duration_{i}") for i in range(n)]

#durations = [random.randint(1, 50) for i in range(n)]

durations = [19, 30, 32, 49, 28]

for i in range(n):

    model.Add(duration_vars[i] == durations[i])

is_present_vars = [model.NewBoolVar(f"is_present_{i}") for i in range(n)]

interval_vars = [model.NewOptionalIntervalVar(start_vars[i], duration_vars[i], end_vars[i], is_present_vars[i], f"interval_{i}") for i in range(n)]

model.AddNoOverlap(interval_vars)

model.AddAssumptions(is_present_vars)

obj_var = model.NewIntVar(0, n, 'obj')

model.Add(obj_var == sum(is_present_vars))

#model.Maximize(obj_var)

solver = cp_model.CpSolver()

print(f"DURATIONS: {durations}")

status = solver.Solve(model)

status_name = solver.StatusName(status)

print(f"STATUS: {status_name}")

infeasibles = solver.SufficientAssumptionsForInfeasibility()

print("Infeasible variables:")

for i in infeasibles:

    print(model.GetBoolVarFromProtoIndex(i))

if status_name != 'INFEASIBLE':

    print("Intervals:")

    for i in range(n):

        print(solver.Value(start_vars[i]), solver.Value(end_vars[i]) )

It returns:

DURATIONS: [19, 30, 32, 49, 28] 

STATUS: INFEASIBLE 

Infeasible variables: 

is_present_1 

is_present_2 

is_present_3

If I try to add an objective (uncomment #model.Maximize(obj_var) lime) then the ALL assumptions are in the list:

DURATIONS: [19, 30, 32, 49, 28] 

STATUS: INFEASIBLE 

Infeasible variables: 

is_present_0 

is_present_1 

is_present_2 

is_present_3 

is_present_4

If I remove the assumptions but leave the objective to maximize the number of intervals then I got the correct result: 

DURATIONS: [19, 30, 32, 49, 28] 

STATUS: OPTIMAL 

Infeasible variables: 

Intervals: 

0 19 

0 0 

0 0 

19 68 

68 96

Is it expected behavior?

[Laurent Perron]

Yes, it is documented that it is reduced by heuristics, and not necessary minimal. 

If you want a minimal set of assumptions, do not use this API, just define the objective as the sum of literals. 

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/df67c82e-624b-49ee-9a27-51dd287a8e20n%40googlegroups.com.

[Frederic Didier]

Note that  SufficientAssumptionsForInfeasibility will eventually give a "small" set of assumptions in case of infeasibility, but it is not fully implemented yet...

Currently, it will minimize the set only in a single thread and without an objective. Otherwise you basically get all of the assumptions.

And yes, to really minimize the subset, you need to do like Laurent said.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CABcmEeaC1Yg7Qbhe7mNEuJe-aqhqq5FMPbVCdzvc0a7g5FoEtg%40mail.gmail.com.

[Igor Proshkin]

Are Assumptions broken?
 I tried the same example but with ten variables and got a very strange result:

from ortools.sat.python import cp_model
import random

n = 10

upper_bound = 100

model = cp_model.CpModel()

start_vars = [model.NewIntVar(0, upper_bound, f"start_{i}") for i in range(n)]
end_vars = [model.NewIntVar(0, upper_bound, f"end_{i}") for i in range(n)]

duration_vars = [model.NewIntVar(0, upper_bound, f"duration_{i}") for i in range(n)]

durations = [13, 31, 28, 15, 20, 43, 42, 17, 47, 43]

for i in range(n):
    model.Add(duration_vars[i] == durations[i])

is_present_vars = [model.NewBoolVar(f"is_present_{i}") for i in range(n)]

interval_vars = [model.NewOptionalIntervalVar(start_vars[i], duration_vars[i], end_vars[i], is_present_vars[i], f"interval_{i}") for i in range(n)]

model.AddNoOverlap(interval_vars)
model.AddAssumptions(is_present_vars)

solver = cp_model.CpSolver()

infeasibles = solver.SufficientAssumptionsForInfeasibility()

print("Infeasible variables:")

for i in infeasible:
    print(model.GetBoolVarFromProtoIndex(i))

I got:

Infeasible variables:
is_present_0
is_present_1
is_present_2
is_present_3
is_present_4

It is obviously incorrect. The remaining 4 durations (42, 17, 47, 43) still cannot be fitted into the (0,100) bound.

If I remove these 5 first variables from the assumption, I got:
Infeasible variables:
is_present_5
is_present_6
is_present_7

It can't be expected behavior, can it?

[Laurent Perron]

The contract is that assumptions are sufficient conditions for infeasibility ?

Is the contract valid ?

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/5fd84870-c171-46fa-91a6-fe67378e3028n%40googlegroups.com.

[Igor Proshkin]

Got it. Thank you.

I thought I'd get a feasible solution by excluding "Infeasible" variables.

I have a problem with many thousand intervals. I got an optimal solution, but then the model changed slightly and make the model infeasible. I am trying to find the smallest subset of is_present lits. I can maximize the sum(is_present), but I thought that it would be faster if I get a smaller subset of assumptions quickly and then minimize it.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CABcmEebBiMPbU1fZvxZwoxJRf2LEmeyGoj_LGDtrTYdMBKQ2%2BA%40mail.gmail.com.

[Laurent Perron]

it is.

Note that they can be multiple independent subset of variables, all disjoint. 

You will need to iterate to find all of them.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CAA%3D%3D6MHkW2YwYzHGs-JrbAM6q%2BdXpStmjqyF%3DC%2B9Gd3n7%3DAaGQ%40mail.gmail.com.

--

--Laurent