CP-SAT: Infeasibility Subsolvers

[Stuart Rogers]

I want to solve a large MILP (i.e., to big for Gurobi) that I strongly believe is infeasible. Are there particular solve executable parameters (e.g., subsolvers) that force CP-SAT to focus solely on showing infeasibility?

To be specific, let z be the integer-valued objective function to be minimized. I have what I believe is the optimal solution with objective value U, and I also have a fairly sharp lower bound L. My strategy to show that U is the optimal value is to add the constraint L <= z <= U-1 to the MILP and use CP-SAT to show infeasibility.

[Laurent Perron]

Core, max_lp, probing*, lb_tree_search, *costs, maybe a no_lp too.

Le mar. 30 mai 2023, 04:49, Stuart Rogers <stum...@gmail.com> a écrit :

I want to solve a large MILP (i.e., to big for Gurobi) that I strongly believe is infeasible. Are there particular solve executable parameters (e.g., subsolvers) that force CP-SAT to focus solely on showing infeasibility?

To be specific, let z be the integer-valued objective function to be minimized. I have what I believe is the optimal solution with objective value U, and I also have a fairly sharp lower bound L. My strategy to show that U is the optimal value is to add the constraint L <= z <= U-1 to the MILP and use CP-SAT to show infeasibility.

--
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/696a55ab-39b0-4ea9-8993-3d2784568dbcn%40googlegroups.com.

[Stuart Rogers]

Is this the correct way to specify the sat subsolvers using solve?

~/or-tools_main_2_17_2023/or-tools/bazel-bin/ortools/linear_solver/solve --solver=sat --stderrthreshold=0 --linear_solver_enable_verbose_output --input=input.mps --sol_file=out.sol --params subsolvers:\"core\",subsolvers:\"max_lp\",subsolvers:\"probing*\",subsolvers:\"lb_tree_search\",subsolvers:\"*costs\",cp_model_presolve:true --num_threads=8

....

Starting search at 145.30s with 8 workers.
7 full problem subsolvers: [default_lp, less_encoding, no_lp, max_lp, quick_restart, quick_restart_no_lp, probing]
3 incomplete subsolvers: [feasibility_pump, rins_lns_default, rens_lns_default]
2 helper subsolvers: [synchronization_agent, neighborhood_helper]

[Laurent Perron]

when I put *, it has to be expanded to the real names.

See https://github.com/google/or-tools/blob/stable/ortools/sat/cp_model_search.cc#L619 and around.

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/9860d4b2-0dc9-4d9c-8fb4-51b13551e786n%40googlegroups.com.

[Stuart Rogers]

Doees *costs stand for reduced_costs and pseudo_costs? Does probing* stand for probing and probing_max_lp?

~/or-tools_main_2_17_2023/or-tools/bazel-bin/ortools/linear_solver/solve --solver=sat --stderrthreshold=0 --linear_solver_enable_verbose_output --input=input.mps --sol_file=output.sol --params subsolvers:\"core\",subsolvers:\"max_lp\",subsolvers:\"probing\",subsolvers:\"probing_max_lp\",subsolvers:\"lb_tree_search\",subsolvers:\"reduced_costs\",subsolvers:\"pseudo_costs\",cp_model_presolve:true --num_threads=8

...

Starting search at 146.03s with 8 workers.

7 full problem subsolvers: [default_lp, less_encoding, no_lp, max_lp, quick_restart, quick_restart_no_lp, probing]
3 incomplete subsolvers: [feasibility_pump, rins_lns_default, rens_lns_default]
2 helper subsolvers: [synchronization_agent, neighborhood_helper]

#Model 151.04s var:52392/55218 constraints:104831/110481

[Ryan Henszey]

Just out of curiosity have you solved the LP relaxation? If not you could throw the LP relaxation in to PDLP for awhile just to make sure its feasible.

[Stuart Rogers]

I solved the LP relaxation of the original problem without the constraint L <= z <= U-1. L is quite a bit larger than the lower bound provided by the LP relaxation. I haven't tried to solve the LP relaxation with the extra bound constraints on z.

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/Tz8ovW6cZtY/unsubscribe.
To unsubscribe from this group and all its topics, 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/344ac89c-1949-4304-b5d6-e9e1fc33e1b3n%40googlegroups.com.