[Scip] Problem solving a large problems with many binary variables

[michael.winkler at zib.de]

Hi Alan,

> Hi,
>
> I have a large problem to solve:
>
> original problem has 3646 variables (503 bin, 0 int, 0 impl, 3143 cont)
> and
> 7619 constraints
>
> I know this problem has a solution because gurobi solve it very fast and
> scip says me it is infeasible.
>

This does not necessary mean that the problem is feasible (nor that it is
infeasible). Probably your model is numerically not well-conditioned or
there is a bug. Maybe you can send the model to me directly and I can have
a look.

Most of your changed parameters do not influence the result of SCIPs run.

> For now i am using this sets of configurations:
>
> # maximal time in seconds to run
> # [type: real, range: [0,1.79769313486232e+308], default: 1e+20]
> limits/time = 1000
>
> # solving stops, if the absolute gap = |primalbound - dualbound| is below
> the given value
> # [type: real, range: [0,1.79769313486232e+308], default: 0]
> limits/absgap = 1e-5
>
> # solving stops, if the relative gap = |primal -
> dual|/MIN(|dual|,|primal|)
> is below the given value
> # [type: real, range: [0,1.79769313486232e+308], default: 0]
> limits/gap = 0.0001
>
> # maximal number of nodes to process (-1: no limit)
> # [type: longint, range: [-1,9223372036854775807], default: -1]
> limits/nodes = 40000
>
> # maximal number of total nodes (incl. restarts) to process (-1: no limit)
> # [type: longint, range: [-1,9223372036854775807], default: -1]
> limits/totalnodes = 200000
>

All the above only lead to an early termination of the optimization
process. (Also the totalnodes of 200000 are certainly not reached because
the nodelimit of 40000 per run will be enough.)

> # maximal memory usage in MB; reported memory usage is lower than real
> memory usage!
> # [type: real, range: [0,1.79769313486232e+308], default: 1e+20]
> limits/memory = 250
>

This can change the solution path in the B&B tree, but will most likely
also lead to a early termination.

> # feasibility tolerance for constraints
> # [type: real, range: [1e-17,0.001], default: 1e-06]
> numerics/feastol = 1e-8
>

By decreasing the feasibility tolerance values above, you force SCIP to
solve your model "more correctly". Maybe you want to relax the feasibility
tolerance to allow slightly violated solutions?

> What other configurations i can set to try to make my problem feasible? Or
> what changes can I make to its set of configurations?
>

If you send us/me the model, maybe we/I can say more.

> In the gurobi solution there are many small negative values, how do i
> allow
> this kind of things in scip?
>

Does this mean, that these values are slighty outside the bounds? Then
maybe decreasing the feasibility tolerance can help, but actually there is
no guarantee to find such a solution.

You should also check if Gurobis solution is feasible by copying the
solution into a .sol file and reading it into SCIP (after the problem was
read). Then start optimizing, and the solution will then be checked.

Best, Michael

> Thanks.
>
> --
> Até.
>
> Alan Porto Bontempo
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
>