google / google/or-tools

CP-SAT solver takes way too long to shut down or does not stop at all despite given time limit

Open
#4,882 1 comment 0 reactions 1 assignee Claimed by @vitor1001 View on GitHub
Solver: CP-SAT Solver
Dominant language
C++
Stars
14.1k
Forks
2.5k
Avg merge
8h 39m
Merged PRs (30d)
72

Description

**Note, edit:** model thousands of no_overlap, each with thousands of intervals.

**What version of OR-Tools and what language are you using?**
Version: v9.10.4067 and v9.14
Language: Python

**Which solver are you using (e.g. CP-SAT, Routing Solver, GLOP, BOP, Gurobi)**
CP-SAT

**What operating system (Linux, Windows, ...) and version?**
Appears on multiple operating systems: Linux Manjaro, Windows 11 and Debian GNU/Linux 11 (bullseye)

**What did you do?**
I want to use v9.14, but it still has a pretty severe issue for me (problem 2 from this [post](https://groups.google.com/g/or-tools-discuss/c/T5OY3cEqbws))
The time limit I give is not respected.

I am using a CP-SAT solver with the following parameters:
random_seed: 2
use_optimization_hints: true
max_time_in_seconds: 540
log_search_progress: true
cp_model_probing_level: 1 (or 0, it does not matter)
max_presolve_iterations: 1
merge_no_overlap_work_limit: 1e9 (or 1e8, it does not matter)
hint_conflict_limit: 75000
log_subsolver_statistics: false
fix_variables_to_their_hinted_value: false
num_workers: 128
probing_deterministic_time_limit: 0.3

Here is a model for testing purposes:
model: [test model](https://github.com/Username159/productionplanning/blob/9d4f326b951ef655c47dcd66f7384971dbc27c77/proto_model_9-14_202579_727.zip)

With 2 models similar to the testing model, I encountered the problem that the solver does not stop AT ALL. It runs until I get a memory overload and the whole process is killed.
(Output of on example where the solver does not stop at all: [output](https://github.com/Username159/productionplanning/blob/b2c7722e7bd913244b558663f886431febe1896d/output_crash.txt)

(Similar but slightly less complex models do not have this problem, or not as bad. They take maybe 10-30 seconds longer to stop if max_time_in_seconds = 300 s.)

In general I have the feeling that the v9.14 needs a lot more memory than v9.10, which I am currently using.

I encountered the same problem but far less severe with v9.10.
For example: I start the solver with a solution callback that ends the solver after the first found solution. The first solution is found after 15.43 seconds, but the solver has a user/wall time of 182.827 seconds.
The parameters in this case were:
Starting CP-SAT solver v9.10.4067
Parameters:
random_seed: 2
random_branches_ratio: 0.04
use_optimization_hints: true
max_time_in_seconds: 900
log_search_progress: true
search_branching: AUTOMATIC_SEARCH
cp_model_presolve: false
cp_model_probing_level: 1
max_presolve_iterations: 1
merge_no_overlap_work_limit: 1000000000
hint_conflict_limit: 75000
log_subsolver_statistics: false
fix_variables_to_their_hinted_value: true
num_workers: 12
probing_deterministic_time_limit: 0.3

**What did you expect to see**
I expect the solver to stop at the given time limit.

**What did you see instead?**
Solver takes a lot longer to stop or does not stop at all.

Make sure you include information that can help us debug (full error message, model Proto).

**Anything else we should know about your project / environment**
(Also see my post in the forum: [post](https://groups.google.com/g/or-tools-discuss/c/r8lZFZ4k43o))

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.