Solve a MIP problem with CP-SAT solver

[SW.P]

I have a MPS file with almost all coefficients integer. It is too difficult to solve by SCIP and I want to give the CP-SAT solver a try. 

I tried with `solve` command, but it gives:
```

Solver : SAT_INTEGER_PROGRAMMING

Parameters : max_time_in_seconds:600, num_search_workers:48

Dimension : 279839 x 1784147

Invalid model/parameters in sat_solve_proto.

Invalid CP-SAT parameters: Do not specify both num_search_workers and num_workers

CpSolverResponse summary:

status: MODEL_INVALID

objective: 0

best_bound: 0

integers: 0

booleans: 0

conflicts: 0

branches: 0

propagations: 0

integer_propagations: 0

restarts: 0

lp_iterations: 0

walltime: 0

usertime: 0

deterministic_time: 0

gap_integral: 0

Nodes : 0

Status : MPSOLVER_MODEL_INVALID

Objective : 0.000000000000000e+00

BestBound : 0.000000000000000e+00

StatusString:

Time : 7.241 s

```

Could anyone help on how to accomplish this?

[SW.P]

And I use the command `solve --solver=sat --input=filename`.
The MPS problem has binary variable and continuous variables, which I want to treat them as integer variables.

[SW.P]

Here is the full output :
```
>> solve --solver=sat --input=/home/data/presolved/2024-3-1.mps
File        : '/home/data/presolved/2024-3-1.mps'
Solver      : SAT_INTEGER_PROGRAMMING
Parameters  :
Dimension   : 279839 x 1784147

Running basic LP presolve, initial problem dimensions: 279839 rows, 1784147 columns, 2437490 entries with magnitude in [9.090909e-05, 7.527273e+02]
glop::FixedVariablePreprocessor                        279839 rows, 277029 columns, 2437490 entries with magnitude in [9.090909e-05, 7.527273e+02]
glop::SingletonPreprocessor                            279839 rows, 276261 columns, 2436722 entries with magnitude in [9.090909e-05, 7.527273e+02]
glop::ForcingAndImpliedFreeConstraintPreprocessor      279839 rows, 276261 columns, 2436722 entries with magnitude in [9.090909e-05, 7.527273e+02]
glop::FreeConstraintPreprocessor                       279744 rows, 276261 columns, 2436532 entries with magnitude in [9.090909e-05, 7.527273e+02]
glop::UnconstrainedVariablePreprocessor                279744 rows, 276261 columns, 2436532 entries with magnitude in [9.090909e-05, 7.527273e+02]

Scaling to pure integer problem.
Num integers: 41819/276261 (implied: 7807 in_inequalities: 0 max_scaling: 50) [MIP]
Changed 97 bounds of integer variables to integer values
Warning: 4492 bounds were truncated to 10000000.
Warning: 171945 continuous variable domain with fewer than 1000 values.
Maximum constraint coefficient relative error: 3.19822e-07
Maximum constraint worst-case activity error: 4.94125e-06
Maximum constraint scaling factor: 6.87195e+10

Starting CP-SAT solver v9.6.9999
Parameters: log_search_progress: true num_workers: 1
Invalid model: Invalid domain in constraint : name: "R0003840" linear { vars: 42147 vars: 72792 vars: 238849 vars: 256185 coeffs: 1 coeffs: -1 coeffs: 1 coeffs: -1 domain: -144 domain: -145 }

CpSolverResponse summary:
status: MODEL_INVALID
objective: 0
best_bound: 0
integers: 0
booleans: 0
conflicts: 0
branches: 0
propagations: 0
integer_propagations: 0
restarts: 0
lp_iterations: 0

walltime: 0.117477
usertime: 0.117477

deterministic_time: 0
gap_integral: 0

Nodes       : 0
Status      : MPSOLVER_MODEL_INVALID
Objective   : 0.000000000000000e+00
BestBound   : 0.000000000000000e+00
StatusString:

Time        : 11.74  s
```

[Frederic Didier]

By default the solver does not scale your continuous variables, and the message you get likely indicates that the problem with no scaling (assuming continuous variables are integers) is not feasible.

You can look at the constraint with name: "R0003840" in your original model to understand why assuming its variables are integers may cause an issue.

You can try to multiply all your continuous variables via the parameters "mip_scale_large_domain:true,mip_var_scaling:100" and see what happens.

But usually the best is to scale your model yourself.

--
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/46a8dea8-4396-46fe-93b3-2b357cdfb0ban%40googlegroups.com.

[Frederic Didier]

If you make it works, please also try with num_workers:8 or more, CP-SAT works a lot better in multithread.

[SW.P]

Thanks for quick response.

I checked this constraint is `x1 + x2 >= -135.5`. I think we should scale the constraint instead of the variables right?

[Frederic Didier]

On Tue, Jun 11, 2024 at 1:00 PM SW.P <cn1571...@gmail.com> wrote:

Thanks for quick response.

I checked this constraint is `x1 + x2 >= -135.5`. I think we should scale the constraint instead of the variables right?

Hmm, maybe it was merged with something else, but it looks like an equality in the log,

if it is x1 + x2 = 135.5  then you must scale the variables for it to be feasible.

We can scale the constraint automatically, but not the variables.

 

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/9d695fbb-b49d-4bff-b800-ac71f3a3da82n%40googlegroups.com.

[SW.P]

I don't quite understand why I should scale the variable, let's say `x1` and `x2` are integer variables, then `2x1+2x2=271` should be the scaled constraint, right?
And these variables are indeed continuous in the original model, and I don't care about their values because after solving I will fix the original binary variables and solve the LP problem to get the values for all continuous variables. I only want to treat it as a integer variables in the CP-SAT solver.

[Laurent Perron]

it only scales continuous variables.

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/bacc8cd3-1f2b-4a88-bea3-9f376883b014n%40googlegroups.com.

[christoph...@gmail.com]

2x1+2x2=271 cannot be fulfilled, because the product has to be an even number, but 271 is odd.

[Frederic Didier]

CP-SAT is an exact solver, there is no solution to  `2x1+2x2=271` with x1 and x2 integers since the lhs will always be even and the rhs is odd.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CABcmEeb%2BAPzGA23M-bMJV3j8CuFUbwq%2Bhg8sZofbG74jxPqrZA%40mail.gmail.com.

[SW.P]

Sorry, I mean a new pair of `y1,y2` integer and `y1+y2=271(y1=2x1,y2=2x2)`, where `x1,x2` are indeed continuous variables.

Could you explain what `mip_var_scaling` does?

[SW.P]

Besides, because I treat these continuous variables as integer variables, could I specify the branching order of the variables? I think it would be meaningless to branching on these `integer` variables.