[SCIP] Implementing no-good cuts that cuts off feasible solutions

[Matheus Ota]

Hi Leon and Gerald,

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).

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.

Thanks again,
Matheus

Em qui., 19 de out. de 2023 às 08:46, Gerald Gamrath <gamrath at zib.de>
escreveu:

> Hi Matheus,
>
> I think there are multiple options how to make this work.
>
> 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:
> https://www.scipopt.org/doc/html/FAQ.php#pricerandnodedata
>
> 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.
>
> I hope this helps,
>
> Gerald
> On 10/19/23 14:08, Matheus Ota wrote:
>
> Hi Leon,
>
> 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').
>
> 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:
> 1. Is it possible to update the best feasible solution "manually" inside
> the callback? Or maybe just updating the primal bound value.
> 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.
>
> Thanks again for your attention,
> Matheus
>
> Em qui., 19 de out. de 2023 às 02:10, Leon Eifler <eifler at zib.de>
> escreveu:
>
>> Hi Matheus,
>>
>> 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?
>>
>> In any case, I wanted to mention that SCIP already contains a feature to
>> count/enumerate all integer-feasible solutions:
>> https://www.scipopt.org/doc/html/COUNTER.php#COLLECTALLFEASEBLES
>>
>> I hope this helps,
>>
>> Leon
>> Am 10/18/2023 um 8:42 PM schrieb Matheus Ota:
>>
>> 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.
>>
>> Em qua., 18 de out. de 2023 às 14:32, Matheus Ota <matheusota at gmail.com>
>> escreveu:
>>
>>> Dear SCIP Team,
>>>
>>> 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:
>>> (P)     min cx
>>>           s.t.  Ax <= b
>>>                  x binary
>>>
>>> Suppose that \bar{x} is feasible for (P), then I can cut off just
>>> \bar{x} by using the "no-good cut"
>>> \sum_{i : \bar{x}_i = 0} x_i + \sum_{i : \bar{x}_i = 1} (1 - x_i) >= 1.
>>>
>>> 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:
>>> 1. Get a feasible solution \bar{x} to (P).
>>> 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.
>>> 3. Remove \bar{x} with a no-good cut.
>>>
>>> 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?
>>>
>>> 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.
>>>
>>> Sorry for the long email, and any help is appreciated.
>>>
>>> Best,
>>> Matheus
>>>
>>
>> _______________________________________________
>> Scip mailing listScip at zib.dehttps://listserv.zib.de/mailman/listinfo/scip
>>
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de
>> https://listserv.zib.de/mailman/listinfo/scip
>>
>
> _______________________________________________
> Scip mailing listScip at zib.dehttps://listserv.zib.de/mailman/listinfo/scip
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20231022/1dae885c/attachment.html>