<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body>
<p>Hello Vladimir,</p>
<p>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.<br>
</p>
<p>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).</p>
<p>What kind of constraints did you penalize, how did you select
them and how did your formulate your artificial objective
function?<br>
</p>
<p>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.</p>
<p>I have found that for these kind of problems, SCIP will usually
perform better on the optimization variant.</p>
<p>Another thing that might help is to disable time-consuming
heuristics, if you assume that your instance is probably
infeasible. <br>
</p>
<p>Best,<br>
Leon<br>
</p>
<p>What kind of constraints did you bring into the objective
function and how did you formulate the penalty? <br>
</p>
<div class="moz-cite-prefix">On 27.12.19 22:56, Vladimir V.
Voloshinov wrote:<br>
</div>
<blockquote type="cite"
cite="mid:CAH87KpuuipX87ApQci_J1rTa=XbJove6i5dWtzBuHwkG6s5LjA@mail.gmail.com">
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<div dir="ltr">
<div>Dear SCIP team,</div>
<div><span class="gmail-tlid-translation gmail-translation"
lang="en"><span title="" class="gmail-">Merry Christmas!</span></span>
and Happy New Year!</div>
<div><br>
</div>
<div>But still we have a question: how SCIP (and ParaSCIP) treat
the problem where objective function is absent, i.e. equal to
zero? <br>
</div>
<div>That is the problem is actually a satisfiability problem,
the search of a feasible solution for a set of constraints
given.</div>
<div><br>
</div>
<div>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.</div>
<div>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%).</div>
<div>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).</div>
<div><br>
</div>
<div>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?</div>
<div><br>
</div>
<div>Sincerely yours,</div>
<div>Vladimir.<br>
</div>
</div>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<pre class="moz-quote-pre" wrap="">_______________________________________________
Scip mailing list
<a class="moz-txt-link-abbreviated" href="mailto:Scip@zib.de">Scip@zib.de</a>
<a class="moz-txt-link-freetext" href="https://listserv.zib.de/mailman/listinfo/scip">https://listserv.zib.de/mailman/listinfo/scip</a>
</pre>
</blockquote>
</body>
</html>