CPSAT presolve makes hint infeasible

Hi,

It seems presolving can break a hint to CPSAT; see below.

Starting CP-SAT solver v9.13.4784
Parameters: log_search_progress: true

...

Starting presolve at 0.00s
The solution hint is complete and is feasible. Its objective value is 75235.

...

Preloading model.
#Bound   0.01s best:-inf  next:[-364008,315384] initial_domain
The solution hint is complete, but it is infeasible! we will try to repair it.
#Model   0.01s var:26/27 constraints:11/11

Is there anything I can do about this?

please attach the model

prize_collecting_proto.txt

Thanks. We will look at it.

[CP-SAT] improve precedences; fix #4693; tweak shared tree workers

Fixed on main.

Thanks

@lperron

@lperron I'm getting the same issue. I've got a big list of variables, if I truncate it to a small value, it works as expected.

Logs and models attached - it's a multi-stage solve, and happens on stages 2 and 3.

solve_2.txt
solve_3.txt
before_stage_2_clean.txt
before_stage_3_clean.txt

If I set solver.parameters.keep_all_feasible_solutions_in_presolve = True from #4373 it works, but I'm worried it might be slowing the solve down.

Can you explain to me what works and what does not work ? Laurent Perron | Operations Research | ***@***.*** | (33) 1 42 68 53 00 Le lun. 11 août 2025 à 12:36, Max Reynolds ***@***.***> a écrit :

…

*MarcelloTheArcane* left a comment (google/or-tools#4693) <#4693 (comment)> @lperron <https://github.com/lperron> I'm getting the same issue. I've got a big list of variables, if I truncate it to a small value, it works as expected. Logs and models attached - it's a multi-stage solve, and happens on stages 2 and 3. solve_2.txt <https://github.com/user-attachments/files/21721829/solve_2.txt> solve_3.txt <https://github.com/user-attachments/files/21721830/solve_3.txt> before_stage_2_clean.txt <https://github.com/user-attachments/files/21721831/before_stage_2_clean.txt> before_stage_3_clean.txt <https://github.com/user-attachments/files/21721828/before_stage_3_clean.txt> — Reply to this email directly, view it on GitHub <#4693 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACUPL3MXAUDOUZ5FMHC2RG33NDWD5AVCNFSM6AAAAAB7SRWMGOVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZTCNZWGYYTKMJWGM> . You are receiving this because you were mentioned.Message ID: <google/or-tools/issues/4693/3176615163 ***@***.***>

This is what I get on main:

Presolved optimization model 'before_stage_2_clean': (model_fingerprint: 0x87bca2315ef6884c)
#Variables: 2'679 (#bools: 152 in objective) (2'255 primary variables)
  - 2'679 Booleans in [0,1]
#kAtMostOne: 947 (#literals: 3'072)
#kBoolAnd: 1'001 (#enforced: 1'001) (#literals: 3'894)
#kBoolOr: 1 (#literals: 56)
#kExactlyOne: 424 (#literals: 2'019)
#kLinearN: 29 (#enforced: 1 #multi: 1) (#terms: 2'897)
[Symmetry] Graph for symmetry has 10'994 nodes and 20'780 arcs.
[Symmetry] Symmetry computation done. time: 0.003059 dtime: 0.00849814
[Symmetry] #generators: 73, average support size: 42.9863
[Symmetry] 398 orbits on 1967 variables with sizes: 24,24,24,24,24,24,24,24,24,10,...
[Symmetry] Found orbitope of size 35 x 10

Preloading model.
#Bound   0.32s best:inf   next:[140,292]  initial_domain
#1       0.32s best:219   next:[140,218]  complete_hint
#Model   0.32s var:2679/2679 constraints:2402/2402

and

Presolved optimization model 'before_stage_3_clean': (model_fingerprint: 0x7d9e50ce457992db)
#Variables: 2'967 (#bools: 512 in objective) (2'537 primary variables)
  - 2'967 Booleans in [0,1]
#kAtMostOne: 1'155 (#literals: 3'751)
#kBoolAnd: 992 (#enforced: 992) (#literals: 3'896)
#kBoolOr: 124 (#literals: 425)
#kExactlyOne: 430 (#literals: 2'038)
#kLinearN: 30 (#terms: 3'124)
[Symmetry] Graph for symmetry has 11'879 nodes and 22'320 arcs.
[Symmetry] Symmetry computation done. time: 0.003463 dtime: 0.00980875
[Symmetry] #generators: 87, average support size: 50.5977
[Symmetry] 451 orbits on 2652 variables with sizes: 24,24,24,24,24,24,24,24,24,16,...
[Symmetry] Found orbitope of size 36 x 16

Preloading model.
#Bound   0.33s best:inf   next:[227,851]  initial_domain
#1       0.33s best:608   next:[227,607]  complete_hint
#Model   0.34s var:2967/2967 constraints:2731/2731

Both the examples above don't work for me on v9.14.6206, they are two different solve stages.

Here are some more complete examples:

Small model, `keep_all_feasible_solutions_in_presolve = False`

Small model, `keep_all_feasible_solutions_in_presolve = True`

Large model, `keep_all_feasible_solutions_in_presolve = False`

Large model, `keep_all_feasible_solutions_in_presolve = True`

fixed on main Presolved optimization model 'model.-.large.model.keep.false': (model_fingerprint: 0x644205106ca6f127) #Variables: 37'618 (#bools: 3'258 in objective) (35'742 primary variables) - 37'618 Booleans in [0,1] #kAtMostOne: 17'449 (#literals: 56'422) #kBoolAnd: 14'536 (#enforced: 14'536) (#literals: 47'483) #kBoolOr: 9 (#literals: 319) #kExactlyOne: 1'876 (#literals: 21'494) #kLinearN: 220 (#terms: 41'377) [Symmetry] Graph for symmetry has 154'731 nodes and 283'065 arcs. [Symmetry] Symmetry computation done. time: 0.031788 dtime: 0.089752 [Symmetry] #generators: 111, average support size: 178.432 [Symmetry] 5417 orbits on 15320 variables with sizes: 12,12,12,12,12,12,12,12,12,12,... [Symmetry] Found orbitope of size 90 x 12 Preloading model. #Bound 1.45s best:inf next:[94,3352] initial_domain #1 1.45s best:661 next:[94,660] complete_hint #Model 1.46s var:37618/37618 constraints:34090/34090 Starting search at 1.46s with 12 workers. Laurent Perron | Operations Research | ***@***.*** | (33) 1 42 68 53 00 Le lun. 11 août 2025 à 23:53, Max Reynolds ***@***.***> a écrit :

…

*MarcelloTheArcane* left a comment (google/or-tools#4693) <#4693 (comment)> Both the examples above don't work, they are two different solve stages. Here are some more complete examples: Small model, keep_all_feasible_solutions_in_presolve = False - model - small model, keep false.txt <https://github.com/user-attachments/files/21728595/model.-.small.model.keep.false.txt> - log - small model, keep false.txt <https://github.com/user-attachments/files/21728500/log.-.small.model.keep.false.txt> - Result: Feasible after presolve Small model, keep_all_feasible_solutions_in_presolve = True - model - small model, keep true.txt <https://github.com/user-attachments/files/21728592/model.-.small.model.keep.true.txt> - log - small model, keep true.txt <https://github.com/user-attachments/files/21728495/log.-.small.model.keep.true.txt> - Result: Feasible after presolve Large model, keep_all_feasible_solutions_in_presolve = False - model - large model, keep false.txt <https://github.com/user-attachments/files/21728593/model.-.large.model.keep.false.txt> - log - large model, keep false.txt <https://github.com/user-attachments/files/21728497/log.-.large.model.keep.false.txt> - Result: Infeasible after presolve Large model, keep_all_feasible_solutions_in_presolve = True - model - large model, keep true.txt <https://github.com/user-attachments/files/21728594/model.-.large.model.keep.true.txt> - log - large model, keep true.txt <https://github.com/user-attachments/files/21728499/log.-.large.model.keep.true.txt> - Result: Feasible after presolve — Reply to this email directly, view it on GitHub <#4693 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACUPL3K76LBTX3IB6TLPEET3NGFQLAVCNFSM6AAAAAB7SRWMGOVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZTCNZXHE2DKOJTGU> . You are receiving this because you were mentioned.Message ID: <google/or-tools/issues/4693/3177945935 ***@***.***>

@lperron

Thanks @lperron!

How long will it be before this gets to pip, or do I need to build from source?

Navigation Menu

Repository navigation

CPSAT presolve makes hint infeasible #4693

Small model, `keep_all_feasible_solutions_in_presolve = False`

Small model, `keep_all_feasible_solutions_in_presolve = True`

Large model, `keep_all_feasible_solutions_in_presolve = False`

Large model, `keep_all_feasible_solutions_in_presolve = True`

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

CPSAT presolve makes hint infeasible #4693

Description

Activity

lperron commented on Jun 18, 2025

sghb commented on Jun 18, 2025

lperron commented on Jun 18, 2025

lperron commented on Jun 23, 2025

MarcelloTheArcane commented on Aug 11, 2025

lperron commented on Aug 11, 2025

lperron commented on Aug 11, 2025

MarcelloTheArcane commented on Aug 12, 2025

Small model, keep_all_feasible_solutions_in_presolve = False

Small model, keep_all_feasible_solutions_in_presolve = True

Large model, keep_all_feasible_solutions_in_presolve = False

Large model, keep_all_feasible_solutions_in_presolve = True

lperron commented on Aug 12, 2025

MarcelloTheArcane commented on Aug 13, 2025

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions

Small model, `keep_all_feasible_solutions_in_presolve = False`

Small model, `keep_all_feasible_solutions_in_presolve = True`

Large model, `keep_all_feasible_solutions_in_presolve = False`

Large model, `keep_all_feasible_solutions_in_presolve = True`