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

[Matheus Ota]

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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20231019/1ef58abf/attachment.html>