<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body>
<p>Hi Matheus,</p>
<p>I am a bit confused: Wouldn't the pruning of nodes using the
objective value of \bar{x} in your case be invalid since you have
that nonlinear part to consider? Is adding f to the model and
solving a MINLP not an option for you?<br>
</p>
<p>In any case, I wanted to mention that SCIP already contains a
feature to count/enumerate all integer-feasible solutions:
<a class="moz-txt-link-freetext" href="https://www.scipopt.org/doc/html/COUNTER.php#COLLECTALLFEASEBLES">https://www.scipopt.org/doc/html/COUNTER.php#COLLECTALLFEASEBLES</a></p>
<p>I hope this helps,</p>
<p>Leon<br>
</p>
<div class="moz-cite-prefix">Am 10/18/2023 um 8:42 PM schrieb
Matheus Ota:<br>
</div>
<blockquote type="cite"
cite="mid:CAL0UnZ0xY2uf_t=svwGLQ8jStAUcRCqC7Z6DaU-tS-0kL8wK9g@mail.gmail.com">
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<div dir="ltr">Sorry, there is a problem in the way I phrased the
question. The objective value of solution \bar{x} is not given
by just c^T \bar{x}, but by c^T \bar{x} + f(\bar{x}), where f is
some non-linear function that I know how to compute whenever
\bar{x} is feasible. So if solving the LP relaxation returns an
integer feasible point \bar{x}, it does not necessarily mean
that \bar{x} is optimal (because of the f(.) function). This f()
function creates the need to enumerate with the no-good cuts.</div>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">Em qua., 18 de out. de 2023 às
14:32, Matheus Ota <<a href="mailto:matheusota@gmail.com"
moz-do-not-send="true" class="moz-txt-link-freetext">matheusota@gmail.com</a>>
escreveu:<br>
</div>
<blockquote class="gmail_quote"
style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div dir="ltr">Dear SCIP Team,
<div><br>
</div>
<div>I want to implement a no-good cut (that cuts off a
single integer point of the feasible region) but I don't
know how to proceed. Suppose that I want to solve the
following problem:</div>
<div>(P) min cx</div>
<div> s.t. Ax <= b</div>
<div> x binary</div>
<div><br>
</div>
<div>Suppose that \bar{x} is feasible for (P), then I can
cut off just \bar{x} by using the "no-good cut"</div>
<div>\sum_{i : \bar{x}_i = 0} x_i <a class="gmail_plusreply"
id="m_-7730717292347431225plusReplyChip-0"
moz-do-not-send="true">+</a> \sum_{i : \bar{x}_i = 1} (1
- x_i) >= 1. </div>
<div><br>
</div>
<div>Note that I'm not requesting the no-good cut to be
feasible for (P). This is because I want to essentially
use SCIP to enumerate the solutions. I want to do the
following process:</div>
<div>1. Get a feasible solution \bar{x} to (P).</div>
<div>2. Compare \bar{x} with the best feasible solution
found so far, and update the best solution found if
\bar{x} is better than the current one.</div>
<div>3. Remove \bar{x} with a no-good cut.</div>
<div><br>
</div>
<div>Since I'm always removing a feasible point, in the end
of the branch-and-bound, it should return that the problem
is infeasible. However, I don't want to simply "discard"
\bar{x}. I want to use the objective value of \bar{x} to
possibly prune more nodes of the branch-and-bound tree. Do
you have any suggestions on how to implement this?</div>
<div><br>
</div>
<div>The first idea that came to my mind was to branch
whenever I find a feasible solution \bar{x}. Then in the
left branch node I only have { \bar{x} } as the feasible
region and in the right branch node I add the no-good cut
that cuts off \bar{x}. The problem with this approach is
that, if I'm on the left branch node, once I get a
solution \bar{x} in the CONSCHECK method, I don't know how
to differentiate if this is the first time that I've found
\bar{x} (in which case I should branch) or if this is the
second time that I've found it (in which case I'm on the
left branch node, and I should just return that the
solution is feasible). Also, I'm not totally sure that
this is the "correct" approach to use.</div>
<div><br>
</div>
<div>Sorry for the long email, and any help is appreciated.</div>
<div><br>
</div>
<div>Best,</div>
<div>Matheus </div>
</div>
</blockquote>
</div>
<br>
<fieldset class="moz-mime-attachment-header"></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>