<div dir="ltr">Hi Leon and Gerald,<div><br></div><div>Thank you very much for the replies. In the end, I managed to make the branching rule idea work: my branching rule creates two childs, say child1 and child2. Child1 correspond to a single solution, while child2 has the no-good cuts. To avoid going into the CONSCHECK of my own constraint handler in child1 I simply delete (using SCIPdelConsNode()) the corresponding constraint from child1 node. This is working fine with the depth-first search node selection rule. However, if I don't use depth-first search, child1 might just be explored later (which is not desired, since I want to update the primal bound as soon as possible).</div><div><br></div><div>So I actually have another question: After I create a child node, is it possible for me to force it to be the next explored node in the branch-and-bound tree? I'm creating child1 with `nodeselprio` as 1e6, but it's still exploring some other nodes before child1.</div><div><br></div><div>Thanks again,</div><div>Matheus </div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">Em qui., 19 de out. de 2023 às 08:46, Gerald Gamrath <<a href="mailto:gamrath@zib.de">gamrath@zib.de</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>
<p>Hi Matheus,</p>
<p>I think there are multiple options how to make this work.</p>
<p>First, if you want to store data at a node, you need to write a
constraint handler and add constraints to the nodes. Please have a
look at this FAQ about branch-and-price, where something similar
is done:
<a href="https://www.scipopt.org/doc/html/FAQ.php#pricerandnodedata" target="_blank">https://www.scipopt.org/doc/html/FAQ.php#pricerandnodedata</a></p>
<p>On the other hand, I would argue that there may be a more
SCIP-ish way to achieve what you want. Recall that the CIP concept
asks for a linear objective, but allows for (almost) arbitrary
constraints. So my suggestion would be to introduce an auxiliary
variable z, change your objective to c^T x + z and add a new
constraint handler, which is responsible for ensuring that z =
f(x). Now, this constraint handler can always check if that
relation is fulfilled and, if not, reject a given solution
candidate. When doing that, it could compute the correct z value
and add this updated solution. I guess it should not add it
directly to SCIP, since this would then result in some recursive
call of the solution checking, but you can pass it to heur_trysol,
which will then try to add that solution at the next-possible
time. If you would be able to compute bounds on z based on the
partial fixings of x columns at the current node, your constraint
handler could even tighten the bound of z, leading to better dual
bounds.</p>
<p>I hope this helps,</p>
<p>Gerald<br>
</p>
<div>On 10/19/23 14:08, Matheus Ota wrote:<br>
</div>
<blockquote type="cite">
<div dir="ltr">Hi Leon,
<div><br>
</div>
<div>Thanks for the email. You are right, this is another part
of the context that I forgot to mention: the function f(.) is
non-negative. Thus, if x' is an LP solution obtained at a node
of the branch-and-bound tree, \bar{x} is the best (integer)
solution found so far, and c^T x' >= c^T \bar{x} +
f(\bar{x}), then we can prune the node of x' (since c^T x' +
f(x') >= c^T x'). </div>
<div><br>
</div>
<div>I don't want to count/enumerate all integer feasible
points, what I'm trying to do is to solve an optimization
problem with a "strange" f(.) function that I just know how to
compute for integer points. After thinking a while about how
to do this in SCIP, I think my question boils down to these
two points:</div>
<div>1. Is it possible to update the best feasible solution
"manually" inside the callback? Or maybe just updating the
primal bound value.</div>
<div>2. Alternatively, when branching, is it possible for me to
create some type of "node data"? If so, I guess I can create a
flag for the nodes that correspond to a single feasible point.
I think this may be possible, but I don't know where to look
for an example. I have a custom branching rule already, so
maybe when creating the child nodes, I can flag some nodes as
"special", and then when checking feasibility in the callback,
I know that "special" nodes actually correspond to a single
feasible solution.</div>
<div><br>
</div>
<div>Thanks again for your attention,</div>
<div>Matheus</div>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">Em qui., 19 de out. de 2023 às
02:10, Leon Eifler <<a href="mailto:eifler@zib.de" target="_blank">eifler@zib.de</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>
<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 href="https://www.scipopt.org/doc/html/COUNTER.php#COLLECTALLFEASEBLES" target="_blank">https://www.scipopt.org/doc/html/COUNTER.php#COLLECTALLFEASEBLES</a></p>
<p>I hope this helps,</p>
<p>Leon<br>
</p>
<div>Am 10/18/2023 um 8:42 PM schrieb Matheus Ota:<br>
</div>
<blockquote type="cite">
<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" target="_blank">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_8019691181715410067m_6446074943444206797m_-7730717292347431225plusReplyChip-0">+</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></fieldset>
<pre>_______________________________________________
Scip mailing list
<a href="mailto:Scip@zib.de" target="_blank">Scip@zib.de</a>
<a href="https://listserv.zib.de/mailman/listinfo/scip" target="_blank">https://listserv.zib.de/mailman/listinfo/scip</a>
</pre>
</blockquote>
</div>
_______________________________________________<br>
Scip mailing list<br>
<a href="mailto:Scip@zib.de" target="_blank">Scip@zib.de</a><br>
<a href="https://listserv.zib.de/mailman/listinfo/scip" rel="noreferrer" target="_blank">https://listserv.zib.de/mailman/listinfo/scip</a><br>
</blockquote>
</div>
<br>
<fieldset></fieldset>
<pre>_______________________________________________
Scip mailing list
<a href="mailto:Scip@zib.de" target="_blank">Scip@zib.de</a>
<a href="https://listserv.zib.de/mailman/listinfo/scip" target="_blank">https://listserv.zib.de/mailman/listinfo/scip</a>
</pre>
</blockquote>
</div>
</blockquote></div>