Debugging the model

[Shesha Sreenivasamurthy]

Hi All,

   I am new to CP and I using CP-SAT solver. I get an infeasible solution. How to debug ?

Using params.set_log_search_progress(true); prints a bunch of log which I have no clue how to interpret. Any help is appreciated.

Thanks,

Shesha.

[Shesha Sreenivasamurthy]

Is there any way to say, the solution is infeasible due to this/these constraints ?

Sure, I can keep commenting out the constraints to identify, but is there a better way ? I am using C++ bindings.

[Laurent Perron]

https://github.com/google/or-tools/blob/stable/ortools/sat/docs/troubleshooting.md

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

--
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 visit https://groups.google.com/d/msgid/or-tools-discuss/2c115e8a-a196-4370-aeb3-6c6b7bdbeb8bn%40googlegroups.com.

[Shesha Sreenivasamurthy]

Thank you. Will look into it.

[Shesha Sreenivasamurthy]

I followed the sample code as follows. Am I doing it right ?

In this Z is a boolean array which will be 1 if there is a split of a field.

const BoolVar a = model.NewBoolVar().WithName("a");

for (int i = 0; i < NVARS; ++i) {

LinearExpr num_splits_per_field = 0;

for (int j = 0; j < NCONTAINERS; ++j)

num_splits_per_field += (Z[i][j]);

model.AddLessOrEqual(num_splits_per_field, MAXSPLITS).OnlyEnforceIf(a);

}

model.AddAssumptions({a});

It printed index 108. How to interpret what this is number ?

No solution found.
CpSolverResponse summary:
status: INFEASIBLE
objective: NA
best_bound: NA
integers: 272
booleans: 106
conflicts: 1
branches: 227
propagations: 711
integer_propagations: 6162
restarts: 212
lp_iterations: 123
walltime: 0.0393375
usertime: 0.0393376
deterministic_time: 0.00297725
gap_integral: 0

[Shesha Sreenivasamurthy]

Hello,

   If someone can tell me how to make sense out of the index 108, i.e., how to tie this 108 to constraint/assumption I sincerely appreciate it. Just this index is not proving any use to me.

Thanks,

Shesha.

[Shesha Sreenivasamurthy]

Hello,

   If someone can please let me know how to make sense of the index and how to tie that to the constraints, I sincerely appreciate it.

Thanks,

Shesha

On Mar 11, 2025, at 9:45 AM, Shesha Sreenivasamurthy <she...@gmail.com> wrote:

Hello,

To view this discussion visit https://groups.google.com/d/msgid/or-tools-discuss/a08d03d7-841c-4a70-8f14-aca5cc7e3934n%40googlegroups.com.

[blind.line]

First, I must admit I have barely skimmed your messages. 

With that caveat, what I would suggest is to dump the model pre-solve in pbtxt format. There are plenty of examples of that in this forum. 

Then go through and find the constraint that is failing. 

When I need to do that, I pop the protobuf nto a spreadsheet, create a new column for the variable number, restart that counter at the start of the constraints. Then I use the auto filter feature to limit the variables and constraints to just what so care about. 

Sometimes the number of the failing constraint given is off from the output complaint, so look around. But the text description of the failing constraint is accurate. 

Once you know what is failing, you can make more progress figuring out why. 

Regards,

James

To view this discussion visit https://groups.google.com/d/msgid/or-tools-discuss/9E7F04E2-2D6F-4D63-9A8B-CE02AB284465%40gmail.com.

[Issoufou Abdou]

Hello,

It is possible to add name to constraints, it can help you to identify. Please see this link https://or.stackexchange.com/questions/11035/or-tools-cp-sat-solver-is-it-possible-to-name-a-constraint-like-in-gurobi

Thanks

To view this discussion visit https://groups.google.com/d/msgid/or-tools-discuss/9E7F04E2-2D6F-4D63-9A8B-CE02AB284465%40gmail.com.

[Priidik Vilumaa]

I only tried it once, but I did have luck with chatgpt or some other LLM finding the source of infeasibility from the CP-SAT model proto. It did lead me into the right direction at least.

Best,

Priidik

[Shesha Sreenivasamurthy]

Hello Issoufou,

   I can definitely add it. But how does it help me.  When I set 

params.set_log_search_progress(true);

It does not print any names.

I have not yet tried the suggestion of blind.line. The suggestion is daunting, It is very difficult to debug than I expected. Ideally, it should just print the name or index of the constraints that fails. If it is an index, then there must be some way to do a reverse lookup of the index.

To view this discussion visit https://groups.google.com/d/msgid/or-tools-discuss/CAOhPq2NaoD9XiQs0g4kCEhYD4rpQ2HxbSQBrJ8yu89b2Q3ZUYg%40mail.gmail.com.

[Laurent Perron]

you should either disable presolve, or keep names, or both.

parameters:

cp_model_presolve: set to false

ignore_names: set to false

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

To view this discussion visit https://groups.google.com/d/msgid/or-tools-discuss/CABL7MgF_ct97czzBfAy4hQ83RAhHBT88YHoYd%2BpxqC6xsKZbXA%40mail.gmail.com.

[Shesha Sreenivasamurthy]

I have captured the logs with the set parameters. I could not make out the failing constraints from those logs. What should I be looking for?

I dumped the presolved model using a function as shown below. It has so many control characters. Not sure if this is the right way to serialize.

void DumpPresolvedModelToPbtxt(const CpModelProto& model, const char *filename) {

// Open the file to write the pbtxt.

std::ofstream outfile(filename, std::ios::out);

if (!outfile.is_open()) {

std::cerr << "Failed to open file for writing: " << filename << std::endl;

return;

}

// Serialize the CpModelProto object to pbtxt.

model.SerializeToOstream(&outfile);

outfile.close();

std::cout << "Model has been dumped to " << filename << std::endl;

}

To view this discussion visit https://groups.google.com/d/msgid/or-tools-discuss/CABcmEeaheKedKkbd5jcW_%2BdV%2BXihRgnj9frxXNCXutcpnAFNRw%40mail.gmail.com.

[Shesha Sreenivasamurthy]

When I execute the sample  ortools/sat/samples/assumptions_sample_sat.cc, 

I get the following output.What does the output 3, 4, 5 mean here ?

I0000 00:00:1743038957.524412   14505 assumptions_sample_sat.cc:64] 3
I0000 00:00:1743038957.524454   14505 assumptions_sample_sat.cc:64] 4
I0000 00:00:1743038957.524457   14505 assumptions_sample_sat.cc:64] 5

[Laurent Perron]

3rd, 4th and 5th literals passed as assumptions I believe

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

To view this discussion visit https://groups.google.com/d/msgid/or-tools-discuss/e8d0d115-1eec-4577-97a5-4a624d29131en%40googlegroups.com.

[Shesha Sreenivasamurthy]

If they are assumption index, the program has only 3. How come their index is 3, 4, 5. How to map that index to the assumptions or the constraints is the main issue.

[Shesha Sreenivasamurthy]

Hello,

I made some progress, but still not out of the woods. I was able to print the protobuf as described in https://groups.google.com/g/or-tools-discuss/c/MLY_u4CjZ9k

Then, when I print the assumptions as below, indices that it prints can be mapped to constraints['enforcement_literal'] in the pb text dump. If a constraint is given a name, then the constraints['name'] will be present and we can easily map the assumption index to constraint.

for (const int index :

response.sufficient_assumptions_for_infeasibility()) {

std::cout << "INDEX " << index << std::endl;

}

However, if the solution is infeasible, sufficient_assumptions_for_infeasibility contains all assumptions, which is not useful.

I also saw this note in the source -

"Warning: solving with assumptions was requested in a non-fully "

"supported setting.\nWe will assumes these assumptions true while "

"solving, but if the model is infeasible, you will not get a useful "

"'sufficient_assumptions_for_infeasibility' field in the response, it "

"will include all assumptions.");

Is there a way to get a list of assumptions that contributed to the infeasibility ?

On Wed, Mar 26, 2025 at 11:39 PM Shesha Sreenivasamurthy <she...@gmail.com> wrote:

If they are assumption index, the program has only 3. How come their index is 3, 4, 5. How to map that index to the assumptions or the constraints is the main issue.

--
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 visit https://groups.google.com/d/msgid/or-tools-discuss/df65889f-7527-4e88-8606-d17f13b5098bn%40googlegroups.com.

[Laurent Perron]

Have you enabled the log ?

--Laurent

To view this discussion visit https://groups.google.com/d/msgid/or-tools-discuss/CABL7MgF2AxQW1L1XM1jUtPHo_%3DypMAy%2ByhMX3kG6eafji5DT2A%40mail.gmail.com.

[Laurent Perron]

So to have meaningful assumptions, you need to remove the objective, and run with one worker

--Laurent

[Shesha Sreenivasamurthy]

Hello,

I have enabled log by setting param 

params.set_interleave_search(true);

Is there a different way ? I had not pasted the output in my earlier post.

I did not know that I need to remove objective, which I have now (Thank you) and for consistency of the solution, I have only one worker. if there is a better way to have consistency with multiple workers, please let me know.

Coming back to the debugging,

With the above changes, in my program (not the sample program), I was able to reduce it to 50 plausible constraints compared to 250 that I have. However, I faced an issue.

When I add assumption to overlap constraints, the model validation fails (return code 1). Can we not have assumptions in OVERLAP constraints ? This is how I am adding it.

OVERLAPS[g].push_back(intervalVar);

snprintf(constrname, MAX_VARLEN, "OVERLAP_%02d", g);

Constraint c = model.AddNoOverlap(OVERLAPS[g]).WithName(constrname);

ABOOL3_1D[g] = model.NewBoolVar();

c.OnlyEnforceIf(ABOOL3_1D[g]);

model.AddAssumptions({ABOOL3_1D[g]});

Where, OVERLAPS is a vector of IntervalVar.

Thanks,

Shesha.

[Laurent Perron]

This is not the param: log_search_progress=True

The interleave search will actually disable assumptions the same way multiple workers do

--Laurent

To view this discussion visit https://groups.google.com/d/msgid/or-tools-discuss/1be44806-edc3-42de-8cfb-4457dd179c5bn%40googlegroups.com.