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

[Leon Eifler]

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 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/be7e55d0/attachment.html>