[SCIP] What SCIP does when objective function equal to zero

[Leon Eifler]

Hello Vladimir,

I do not think there is a clear, general answer to your problem. It is 
true that MIP solvers will usually perform better for optimization 
problems than for pure feasibility problems of similar size, since a lot 
of solving techniques use the objective function (e.g. pseudo-costs). 
These techniques will not help if you do not have an objective function.

However, just keeping the same feasibility formulation and adding 
penalty-constraints to the objective might not help, since then SCIP 
will (broadly speaking) focus on the feasibility of those constraints 
more during branching, which is not really your true objective (finding 
any feasible solution or proving infeasibility).

What kind of constraints did you penalize, how did you select them and 
how did your formulate your artificial objective function?

Sometimes it is possible to reformulate a feasibility problem to a 
"real" optimization problem that you know to be feasible. As a simple, 
abstract example consider a feasibility problem that models the 
question: "Does there exist a set with less than n elements, that has a 
certain property?". By instead solving the optimization problem "Find 
the smallest set that has a certain property" and then just checking the 
size of your optimal solution you have a "real" optimization problem.

I have found that for these kind of problems, SCIP will usually perform 
better on the optimization variant.

Another thing that might help is to disable time-consuming heuristics, 
if you assume that your instance is probably infeasible.

Best,
Leon

What kind of constraints did you bring into the objective function and 
how did you formulate the penalty?

On 27.12.19 22:56, Vladimir V. Voloshinov wrote:
> Dear SCIP team,
> Merry Christmas! and Happy New Year!
>
> But still we have a question: how SCIP (and ParaSCIP) treat the 
> problem where objective function is absent, i.e. equal to zero?
> That is the problem  is actually a satisfiability problem, the search 
> of a feasible solution for a set of constraints given.
>
> My colleagues ask me to run ParaSCIP with some rather hard problem 
> with binary variables of the above type, which took about 170 CPU*hour 
> to be solved on rather power cluster.
> In attempt to reduce solving time I have recommended them to 
> reformulate the problem, i.e. to bring some constraints to the 
> criterium via penalty function... But as a result we got much more 
> hard problem with dozens more solving time (I even had to kill 
> ParaSCIP after 1000 CPU*hours of calculating with gap around 20%).
> The same effect was for variants of the same problems of smaller 
> dimensions (solved by SCIP): converting some constraints to the 
> penalty made the problem much more hader (for SCIP).
>
> Can you tell a few words about SCIP's approach to the problem with 
> constant goal function? May be there are some papers on the subject?
>
> Sincerely yours,
> Vladimir.
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20191230/41b400e8/attachment.html>