CP-SAT returns UNKNOWN for production scheduling model despite presolve and feasible sub-models – looking for modeling advice

[Jikku Markose]

Hi everyone,

I'm working on a fairly large production scheduling application using Google OR-Tools CP-SAT in C# (.NET 8),
and I'd appreciate some advice on improving the model.

Application
The application runs on Azure Container Apps (ACA) having 16vCPU and generates production schedules, with 10min of execution time

The scheduler plans approximately 24–48 hours ahead using configurable time slots (typically 30 minutes).Current model
Decision variables mainly represent

Production quantity per (slot, mix)
Delivery quantity
storage inventory
QC state
Various helper variables for changeover logic
The model contains roughly

Presolved model

#Variables: 17,657

12,302 primary variables
7,515 Boolean variables
Constraints

BoolOr: 6,935
BoolAnd: 3,794
ExactlyOne: 1,761
AtMostOne: 1,354
LinearN: 4,552
Symmetry graph

76,182 nodes
154,725 arcs

Solver Parameters:
max_time_in_seconds:600
num_search_workers:16
random_seed:1234
randomize_search:true
interleave_search:true
search_branching:PORTFOLIO_SEARCH
cp_model_presolve:true
linearization_level:1
symmetry_level:2
presolve_bve_threshold:500
log_search_progress:true
relative_gap_limit:0.01Solver behavior
For some demand sets the solver finds an optimal solution quickly.

Or-Tool nuget version: 9.15.6755

However, for certain combinations of demands, the solver returns

UNKNOWN

instead of FEASIBLE or OPTIMAL.

The same datasets become feasible if certain constraint groups are removed.

This suggests the model is not fundamentally infeasible.

Things already verified
I've already spent significant time isolating constraint groups.

Some observations:

Individual constraint groups solve correctly.
Most combinations solve correctly.
UNKNOWN only appears when all business rules are enabled.
Presolve succeeds.
No obvious infeasible core remains.
Objectives are currently disabled during debugging, and UNKNOWN still occurs.
changed slot time from 30min to 1hr worked the schedule with all constraints (but this cannot be
done now due to business complexity)
Current suspicion
I suspect this is no longer an infeasibility problem but rather a search/modeling issue.

The current model is quite SAT-heavy.

The changeover constraint currently introduces many helper BoolVars using

OnlyEnforceIf
BoolAnd
BoolOr
implications
to determine inter-slot changeovers.

After reviewing the model, I'm considering redesigning the changeover logic to
reduce the number of Boolean helper variables significantly.

Questions
Looking only at the presolved statistics, do these numbers suggest a SAT-heavy model likely to produce UNKNOWN?

Are there particular constraint patterns that typically cause CP-SAT to stall in scheduling models?

Is there a recommended way to model changeovers between production slots without introducing large implication networks?

Would you generally prefer:

more integer state variables with fewer BoolVars
or the opposite?
Are there any common modeling anti-patterns that stand out from the statistics above?

Would enabling LNS or changing search parameters likely help here, or is this more likely a modeling issue?

Any suggestions on improving the model formulation would be greatly appreciated.

Thanks!

[Laurent Perron]

I believe this has been solved on the main branch.

You will need to build from source to test it though.

Can you send us the proto of a failing model ?

--Laurent

--
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/86175bfe-113f-41cf-a9ef-1ef3592da4ddn%40googlegroups.com.

[stanly markose]

Thanks, Laurent!  

 I'm currently using OR-Tools 9.15.6755 through the .NET NuGet package. I'll try building the latest main branch and verify whether the issue still exists. 

PFA failing CpModelProto. 

You received this message because you are subscribed to a topic in the Google Groups "or-tools-discuss" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/or-tools-discuss/6PkKORudHa0/unsubscribe.
To unsubscribe from this group and all its topics, send an email to or-tools-discu...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/or-tools-discuss/CAPyyUTuWegWwEMnDL_UFECJiXHopWCwryqbYZq2-PH0F5UQALQ%40mail.gmail.com.

[Laurent Perron]

You have a constraint var(5900 with domain [0, 0]) >= 2

This fails instantly during model copy

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/CAFD8WNpd01pCCYMM-UWsOjO1YUdk-Pwy6skQuqw07bJ8dc_nZA%40mail.gmail.com.

[stanly markose]

My apologies!, shared the wrong file.

PFA CpModelProto causing UNKNOWN

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

[Laurent Perron]

your conclusions are wrong. You add constraints, therefore you remove solutions. These could become very sparse and hard to find.

I ran it on my laptop with 16 workers, 

CpSolverResponse summary:

status: OPTIMAL

objective: NA

best_bound: NA

integers: 13011

booleans: 17298

conflicts: 20535

branches: 248875

propagations: 23969210

integer_propagations: 72146468

restarts: 90

lp_iterations: 0

walltime: 68.8439

usertime: 68.8439

deterministic_time: 321.356

gap_integral: 0

solution_fingerprint: 0x616fb2298dee7494

To answer the questions:

  - CP-SAT prefers more boolean variables and less integer variables

  - LNS only triggers after one solution is found

about parameters:

Solver Parameters:
max_time_in_seconds:600 <- OK
num_search_workers:16   <- good
random_seed:1234 <- useless, remove
randomize_search:true <- useless remove
interleave_search:true <- make the search deterministic, but way slower. I would remove
search_branching:PORTFOLIO_SEARCH <- The slows down most of the workers, remove
cp_model_presolve:true
linearization_level:1 <- interfere with the portfolio, remove
symmetry_level:2 <- this is the default, remove
presolve_bve_threshold:500 <- you cannot predict the effect, remove
log_search_progress:true
relative_gap_limit:0.01

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

--

[stanly markose]

Thank you again for investigating my model and for sharing the results.

I reran the model using the same solver parameters you suggested (keeping only the recommended parameters such as num_search_workers, max_time_in_seconds, and log_search_progress). However, I'm still observing a significantly different behavior from what you reported.

Below is a comparison of the results:

Metric	Your Result	My Result
Solver Version	----------------	OR-Tools 9.15
Status	OPTIMAL	UNKNOWN
Solve Time	~69 seconds	~603 seconds
Workers	16	16
Conflicts	~20,000	196
Restarts	~90	0
LP Iterations	0	~49,933

The most interesting differences are the very low number of conflicts and the absence of restarts on my side, whereas your run appears to make much more progress through the search.

To verify whether this difference is entirely due to changes on the main branch, I'm planning to build OR-Tools from source locally and rerun the same exported .pb model.

As an alternative, would it be possible to share a prebuilt Windows DLL/NuGet package (or point me to a build corresponding to the commit you tested)? That would allow me to quickly validate the behavior within my existing C# application before setting up the full build environment.

If that's not practical, no problem—I will continue with building the latest main branch locally.

Thank you again for your help and for taking the time to investigate this issue.

You received this message because you are subscribed to a topic in the Google Groups "or-tools-discuss" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/or-tools-discuss/6PkKORudHa0/unsubscribe.
To unsubscribe from this group and all its topics, send an email to or-tools-discu...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/or-tools-discuss/CABcmEebZKB47x_-OZmRPuyJHdZyDoegTTVn6VhGB84AbSwT0%2BA%40mail.gmail.com.

[Laurent Perron]

Final reporting is unreliable. It depends on the solver that closes the search I believe.

You should look at the stats displayed at the end of the log

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/CAFD8WNoSBRANQ2BNs6r2CJXd_VEpX0kunj%2BJjt29zuUCXODs%3DQ%40mail.gmail.com.

[stanly markose]

Attaching the solver log generated from the latest main branch build.

The run was executed using the same new_model_pb.pb that I had shared previously. I rebuilt OR-Tools from the latest main branch, executed the model using sat_runner, and captured the complete solver log.

Despite running on the latest main, the solver still returns UNKNOWN on my machine (I've also tried with num_search_workers=1, which produces the same result).

Could you please take a look at the attached log and let me know if you notice anything unusual or if there's any difference compared to the run on your machine? If possible, could you also share the commit hash and the exact command/parameters you used for your successful run so I can verify that I'm testing under the same conditions?

Thanks again for your help!

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

[Laurent Perron]

Main is lagging w.r.t. my version.

Tou can try the lperron-dev branch 

--Laurent

[stanly markose]

Thanks! I tested the lperron-dev branch, and it successfully solves our model.

Is this improvement expected to be merged into main and included in an upcoming OR-Tools release/NuGet package? If so, do you have an approximate timeline?

If not, would you recommend using a build from the lperron-dev branch for now, or is there a specific commit you would suggest using as a stable baseline?

Thanks again for your help!

[Laurent Perron]

Yes, should be merged soon 

--Laurent

[stanly markose]

I then tried building the full .NET wrapper from source on Windows so that we could use it directly in our C# application, but I ran into what appears to be a build-system issue rather than a problem with our environment.

Commands used:

cmake -S . -B build_dotnet -G "Ninja" -DBUILD_DOTNET=ON -DCMAKE_BUILD_TYPE=Release
cmake --build build_dotnet --config Release --target install -j 4

Environment:

• Windows 11

• Visual Studio 2022 Professional (MSVC 14.44.35207)

• CMake + Ninja

Issue:
The build consistently fails while compiling the ortools_proto target. Every generated .pb.cc file fails with C2491 (definition of dllimport static data member not allowed).

Looking at the compiler command, OR_PROTO_DLL appears to be defined twice with conflicting values:

-DOR_PROTO_DLL=__declspec(dllexport)
-DOR_PROTO_DLL=__declspec(dllimport)

This happens consistently across all of the generated protobuf sources that fail (e.g., bop_parameters.pb.cc, boolean_problem.pb.cc, search_limit.pb.cc, assignment.pb.cc, and likely others later in the build).

I've attached the full CMake configuration log and the complete build log for reference.

Is this a known issue on the current lperron-dev branch, or is there an additional CMake option or build step required to build the .NET wrapper successfully on Windows?

[Laurent Perron]

--Laurent

[stanly markose]

Just following up on this thread in case anyone has had a chance to look into it.

We're currently blocked from validating the solver fix in our .NET application because we're unable to build the .NET wrapper successfully on Windows. While the sat_runner from the lperron-dev branch works correctly with our model, we can't integrate or validate the fix in our production application until we're able to build the .NET package.

This is currently blocking validation for a production issue, so we'd really appreciate any guidance whenever someone has a chance.

Thanks in advance!